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

I cant get the detail of this algorithm. How does the HL and HR get their height? Can anyone explain it? Thanks a lot.

CodePudding user response：

There are two cases.

The first case is when the tree node is NULL, meaning there isn't a tree node. That height is zero, and is captured in the "else" statement.

The second case is when the tree node is not NULL, then the hieght of the tree is the larger of the heights of the two tree branches, with 1 added.

So, if you have a single node tree, the branches both report zero, and one is added, making it a height of one. If that single node tree has a parent node, then that branch of the parent node will report one, and the other branch might report something else (let's say zero) and the height is one plue one, or two. And so on, until you finally get the height of the tree.

CodePudding user response：

I'm going to guess the thing you're struggling with here is how recursive functions work. The important thing to note is that GetHeight returns an int.

If you examine a tree node which is non-null, the if(BT) condition is evaluated, and you follow the Left and Right pointers into GetHeight again (adding a stack frame). Now, if Left or Right is null you're going hit the else condition which returns 0. Imagine a leaf node (left and right both null), both HL and HR will be 0, so MaxH will be 0, and GetHeight will return 1. If the call to GetHeight were in a recursive function call, that 1 gets passed back to the calling function, and either HL or HR is now 1, and that call will return MaxH 1 until you end up back at the initial call. In this way you recursively accumulate the answer.