获取二叉树高度的算法是如何工作的？

Question

int GetHeight(BinTree BT)
{
    int HL, HR, MaxH;

    if(BT)
    {
        HL = GetHeight(BT->Left);
        HR = GetHeight(BT->Right);
        MaxH = HL > HR ? HL : HR;
        return (MaxH + 1);
    }
    else
        return 0;
}

我无法了解该算法的详细信息。 HL 和 HR 是如何得到它们的高度的？谁能解释一下？非常感谢。

Answer 1

有两种情况。

第一种情况是树节点为NULL，即没有树节点。该高度为零，并在“else”语句中捕获。

第二种情况是当树节点不为NULL时，则树的高度为两个树枝高度中较大者加1

所以，如果你有一个单节点树，分支都报告为零，并且添加了一个，使其高度为一。如果那个单节点树有一个父节点，那么父节点的那个分支将报告一个，另一个分支可能报告其他东西（假设为零）并且高度是一加一或二。依此类推，直到最终得到树的高度。

Answer 2

我猜你在这里遇到的问题是递归函数的工作原理。需要注意的重要一点是 GetHeight return 是 int.

如果你检查一个非空的树节点，if(BT) 条件被评估，然后你按照 Left 和 Right 指针再次进入 GetHeight （添加堆栈框架）。现在，如果 Left 或 Right 为 null，您将达到 returns 0 的 else 条件。想象一个叶子节点（左右都是null），HL和HR都会是0，所以MaxH会是0，GetHeight会return 1. 如果对 GetHeight 的调用是在递归函数调用中，则 1 会传递回调用函数，并且 HL 或 HR 现在为 1，并且那个电话会 return MaxH + 1 直到你回到最初的电话。这样你递归地累积答案。

获取二叉树高度的算法是如何工作的？

How does the algorithm of getting binary tree height work?

c

recursion

binary-tree