计算二叉搜索树的高度

Question

给定以下代码：

private int getHeight(Node root){
        if(root == null){
            return 0;
        }
        else{
            int leftHeight = getHeight(root.leftChild);
            int rightHeight = getHeight(root.rightChild);

            if(leftHeight > rightHeight){
                return leftHeight + 1;
            }
            else{
                return rightHeight + 1;
            }

        }
    }

我不明白的是这两行：

int leftHeight = getHeight(root.leftChild);
int rightHeight = getHeight(root.rightChild);

怎么递归计算树的高度？如果一棵树看起来像这样怎么办：

那两条线是怎么算出来的？？到底递归如何在遍历树时添加 1？

我的看法是：

int leftHeight = getHeight(root.leftChild); 转到 1 的节点并在那里停止。

int rightHeight = getHeight(root.rightChild); 使用 9 转到节点并在那里停止。

我只是不明白它是如何遍历整个东西的。

详细的解释就好了！谢谢！

Answer 1

我们先总结一下我们拥有的要素

停止条件

if(root == null){
        return 0;
}

这意味着我们在一个不存在的 child 上。例如，在您的树中，“2”元素确实有右 child，但没有左 child。所以你什么时候会打电话给

int leftHeight = getHeight(root.leftChild);

root.leftChild 将等于 null。所以我们要return0，因为这个child不存在

递归

int leftHeight = getHeight(root.leftChild);
int rightHeight = getHeight(root.rightChild);

对于树中的每个元素，您都希望获得其左侧和右侧的元素数量。所以你正在调用同一个函数，在参数中给出左边的 child 或右边的 child。如果这个元素不存在，我们就进入停止条件，return0。如果有元素，我们想检查同样的事情，并继续相同的方式。这就解释了为什么你不能只停在“1”和“9”，然后继续直到遇到一片叶子。

身高计算

if(leftHeight > rightHeight){
    return leftHeight + 1;
}
else{
    return rightHeight + 1;
}

我们要计算树的高度。我们之前解释过，leftHeight 将在其左侧包含实际元素下的元素数，在其右侧包含 rightHeight。如果左边有更多的元素，那就意味着左边的高度比右边的高。然后我们 return 这个计算出的高度，并向它加 1。我们加 1 因为我们所在的元素也是这个高度的一部分：我们想告诉我们的 parent 元素它下面的高度是它的 child (1)，加上它下面的所有元素 child.

例子

现在我们已经解释了所有内容，让我们尝试使用您的树示例。

该函数将在您的“4”元素上调用，然后一直到树的底部。让我们从您的“3”元素开始。因为它的左边和右边都没有 child ，所以我们将 leftHeight 和 rightHeight 设置为 0。这意味着该元素下的高度为 0。那么我们只需 return 1 ，对应“3”元素。

然后我们到达“2”。 “2”的左边没有child，所以leftHeight等于0。但是rightChild等于1，因为“3”元素return编辑了这个信息。 1 > 0，所以我们将return rightChild(1) 的值，并为“2”元素加一。

然后我们到达“1”元素。相同的概念：左边没有 child，右边有 1。 leftHeight 等于 0，rightHeight 等于 2，因为“2”元素 return 编辑了此信息。 2 > 0，所以我们将return rightChild(2) 的值，并为“1”元素加一。

我们现在去另一边吧。我们有“8”元素。它没有 child，并且将像“3”元素一样工作。然后它自己只会 return 0 + 1。

“8”的parent元素是“9”。这个元素右边没有child，所以rightHeight会是0。但是它左边有一个child，"8"，returned him 1. 1 > 0,所以我们将 return leftChild (1) 的值，并为 9.

加一

然后我们到达最后一个元素“4”。它右边有一个child，“9”，左边有一个“1”。 rightHeight 在那里将是 2，因为“9”returned 这个值。 leftHeight 将为 3，因为“1”returned 这个值。 3 > 2，所以我们将return leftHeight(3) 的值，并为“4”元素加一。

"4" 是您的树的根元素，您的函数已在其上首次被调用。最后，我们知道你的树的高度是4.

计算二叉搜索树的高度

Calculating the height of the binary search tree

tree

recursion

binary-search-tree