有人能给我解释一下这个二叉搜索树高度函数吗？

Question

所以我一直在看这个函数，它对我来说毫无意义。

int findHeight(BinaryNode<E> aNode)
{
    if(aNode ==null){
          return -1;
    }


    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if(lefth > righth)
        return lefth + 1;
    else
        return righth +1;
}

假设我有一棵由一个根组成的树，它只剩下一个孩子。所以root->leftchild。

Answer 1

这是一个递归函数（它自己叫）。要理解它是如何工作的，您首先必须可视化它的作用。

首先，将每个BinaryNode视为新子树的根。您可以对树中的任何节点调用findheight，它将返回该子树的高度。

当函数执行时，它调用自己来查找子树中每个左右节点的高度。只要该节点不是null（表示树的叶子），它就会继续沿着分支行进，直到到达一个为null的节点，此时它将返回一个值-1（因为null节点不计算为树的高度的一部分）。

然后，它将开始returning将树备份到根节点。当它从分支中的每个节点返回时，它将在返回值上加1。当它到达顶部时，返回的是最长分支中所有高度的总和（这就是if语句存在的原因）。