0

我试图在我的程序中找到二叉搜索树的高度，并继续使用这个递归解决方案来找到高度：

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。

4

3 回答 3

2

该算法是这样工作的：如果我正在查看的树不存在，则树的长度为 0。

否则，树的长度是我拥有的两个子树的最大高度加 1（需要加 1 才能包括您当前正在查看的节点）。

例如，如果我有一棵没有树枝的树（即树桩），那么我的高度为 1，因为我有两个高度为 0 的子树，并且这些高度加 1 的最大值为 1。

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

A - B - C - D
    |   |
    E   F

（其中 a 是根）

那么，高度不为 0，因为 A 不为空

高度 = 最大值（高度（左），高度（右）） + 1。

在 A 的左边高度为 0，因为 A 没有左分支。

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

为了计算 B 的高度，我们将 B 视为一棵全新的树：

B - C - D
|   |
E   F

现在高度=最大（高度（左），高度（右））+ 1。

为了计算左的高度，我们将 E 视为一棵全新的树：

E

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

但是，它的两个分支不存在，所以它的高度为 1（每个分支的高度为 0）

再次回到父树：

B - C - D
|   |
E   F

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

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

那么，权利的高度是多少？

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

C - D
|
F

问题和之前一样 height = max(height(left), height(right)) + 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。

因此，height(a) = Max(height(null), Max(height(B)) = Max( 0 , 3 ) + 1 = 3+1 =4

完毕。A的高度是4。

于 2013-11-14T00:43:52.700 回答
0

如果二叉树为空，该函数仅返回 0。这是有道理的，因为如果树为空，则没有要计算的节点，因此高度为 0。

如果不为空，则该函数会将 1（当前节点的高度）添加到左侧或右侧子子树的高度，以较大者为准。

它如何知道子子树的高度？通过调用自身递归地传入左孩子或右孩子，以便下一次递归在树的下一层开始。

当您第一次调用该函数并传入树的根时会发生什么？该函数首先调用自身递归地沿着最左边的子节点向下移动，直到找到叶节点。它再次调用自己一次，传入叶节点的左子节点，该子节点为空。最后一次调用不再递归，只返回 0。然后该函数递归到也返回 0 的叶子的右子节点。然后它为自己的高度加 1 并返回。

我们现在位于最左边叶子的父节点，并且像以前一样它将递归到右孩子（叶子的兄弟）。那个可能不存在（返回 0）、是叶子（返回 1）或有孩子（返回 >1）。无论返回值是什么，它将与最左边的叶子（高度 1）进行比较，取较大者将递增（总是加上当前节点的高度）并作为以当前为根的子树的高度返回节点。

请注意，递归将在返回到根时继续“展开”，但在每个级别，它将首先递归到右子子树的下方。这就是所谓的深度优先搜索。最终，整个树将被访问，并一直计算到根的最大高度。

于 2013-11-14T00:51:30.543 回答
0

您的代码对内存不友好。例如，当您运行此方法时，height_leftand height_rightvars 仍将保存在内存中。那么，如果你运行这个函数数十亿次呢？例如，我建议不带变量返回

return max(maxHeight(p->left), maxHeight(p->right));
于 2017-02-17T23:00:12.847 回答