gpt4 book ai didi

c++ - BST 递归查找高度

转载 作者:行者123 更新时间:2023-11-28 03:04:57 26 4
gpt4 key购买 nike

我试图在我的程序中找到二叉搜索树的高度,并不断使用这个递归解决方案来找到高度:

int maxHeight(BinaryTree *p) {
if (!p) return 0;
int left_height = maxHeight(p->left);
int right_height = maxHeight(p->right);
return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

有人可以向我解释一下这是如何工作的吗?我不明白它是如何增加高度的。看起来它应该只穿过树的每一侧并返回 0。

最佳答案

算法是这样工作的:如果我正在看的树不存在,那么树的长度就是0。

否则树的长度就是我有的两棵子树的最大高度加1(加1需要包含你当前正在看的节点)。

例如如果我有一棵没有 Twig 的树(即树桩),那么我的高度为 1,因为我有两棵高度为 0 的子树,这些高度加 1 的最大值为 1。

另一个例子:如果我有一棵树:

A - B - C - D
| |
E F

(其中 a 是根)

然后,高度不为 0,因为 A 不为空

height = max(height(left), height(right)) + 1.

A处left的高度为0,因为A没有左分支。

右分支的高度为B+1的高度。

为了计算出 B 的高度,我们将 B 视为一棵全新的树:

B - C - D
| |
E F

现在height = max(height(left), height(right)) + 1.

为了计算左边的高度,我们将 E 视为一棵全新的树:

E

这个存在所以它的高度不为0

然而,它的两个分支不存在,所以它的高度为1(每个分支的高度为0)

再次回到父树:

B - C - D
| |
E F

我们正在计算高度,发现左边分支的高度是 1。

所以 height = max(1, height(right) ) + 1

那么,右边的高度是多少?

再一次,我们将正确的分支视为它自己的树:

C - D
|
F

问题和之前一样height = max(高度(左), 高度(右)) + 1

为了计算出高度(左),我们单独考虑 F

F

F 的高度为 1,因为它有两个空分支(即两个 0 高度加 1 的最大值)

现在向右看

D

出于同样的原因,D 的高度为 1

回到F和D的父级:

C - D
|
F

C 的高度是:

最大(高度(F),高度(D))+ 1

= 最大值 (1, 1) + 1

= 1 + 1

= 2.

所以现在我们知道了 C 的高度,我们可以回到父级:

B - C - D
| |
E F

回想一下,我们计算出 B 的左分支长度为 1,然后开始计算它的右分支高度。

我们现在知道右分支的高度为 2

Max(1, 2) 为 2。

2 + 1 = 3

因此,B的高度为3。

现在我们知道了,我们终于回到了原来的树:

A - B - C - D
| |
E F

我们已经计算出左侧分支高度为 0,然后开始处理右侧分支。

我们现在知道右分支的高度为 3。

因此, 高度(a)=最大(高度(空),最大(高度(B)) = 最大值 ( 0 , 3 ) + 1 = 3+1 =4

完成。 A的高度为4。

关于c++ - BST 递归查找高度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19967134/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com