计算二叉搜索树的高度

约翰

给出以下代码:

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);

它如何递归计算树的高度?如果一棵树看起来像这样:

     4
    / \
   /   \
  1     9
   \   /
    \ 8
     2
      \
       \
        3

这两行如何计算呢?在地球上,递归如何增加1

我的看法是:

int leftHeight = getHeight(root.leftChild);前往节点1并在此处停止。

int rightHeight = getHeight(root.rightChild);前往节点9并在此处停止。

我只是不明白它是如何遍历整个事情的。

详细的解释会很棒!谢谢!

五十香

让我们首先总结一下我们拥有的元素。

停止条件

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

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

int leftHeight = getHeight(root.leftChild);

root.leftChild将等于null。所以我们必须返回0,因为这个孩子不存在。

递归性

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

对于树中的每个元素,您想要获取其左侧和右侧之前的元素数量。因此,您要调用相同的函数,并在参数中输入左子项或右子项。如果该元素不存在,则输入stop条件,并返回0。如果有一个元素,我们要检查相同的事物,并以相同的方式继续。这就解释了为什么您不仅可以停在“ 1”和“ 9”,而且可以继续直到遇到一片叶子。

高度计算

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

我们要计算树的高度。我们之前曾解释过,leftHeight将在其左侧的实际元素下方包含元素数量,而在其右侧则包含rightHeight。如果左侧有更多元素,则意味着左侧的高度大于右侧的高度。然后,我们返回此计算出的高度,并将其加1。我们加1是因为我们所在的元素也是该高度的一部分:我们要告诉父元素,其下的高度是其子级(1),加上其子级下的所有元素。

例子

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

该函数将在“ 4”元素上调用,然后一直到达树的底部。让我们从“ 3”元素开始。因为它的左边或右边没有子元素,所以leftHeight和rightHeight等于0。这意味着该元素下的高度为0。然后我们只返回1,对应于“ 3”元素。

        3

然后我们到达“ 2”。“ 2”在其左侧没有子代,因此leftHeight将等于0。但是rightChild将等于1,因为“ 3”元素返回了此信息。1> 0,因此我们将返回rightChild(1)的值,并为“ 2”元素添加一个。

     2
      \
       \
        3

然后,我们到达“ 1”元素。同样的概念:左边没有孩子,右边是1。leftHeight等于0,rightHeight等于2,因为“ 2”元素返回了此信息。2> 0,因此我们将返回rightChild(2)的值,并为“ 1”元素添加一个。

  1
   \ 
    \
     2
      \
       \
        3

现在让我们走到另一边。我们有“ 8”元素。它没有子元素,其作用类似于“ 3”元素。然后,它将自己返回0 +1。

  1 
   \ 
    \ 8
     2
      \
       \
        3

“ 8”的父元素是“ 9”。此元素在右侧没有子元素,因此rightHeight将为0。但是在左侧有一个子元素“ 8”,该子元素返回他1。1> 0,因此我们将返回leftChild(1)的值,并且加9。

  1     9
   \   /
    \ 8
     2
      \
       \
        3

然后,我们得出最后一个元素“ 4”。它的右边有一个孩子“ 9”,左边有一个孩子“ 1”。rightHeight将在那里为2,因为“ 9”返回了该值。leftHeight将为3,因为“ 1”返回了该值。3> 2,因此我们将返回leftHeight(3)的值,并为“ 4”元素添加一个。

     4
    / \
   /   \
  1     9
   \   /
    \ 8
     2
      \
       \
        3

“ 4”是树的根元素,首次在其上调用了函数。最后,我们知道您的树的高度为4。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章