C语言 如何获得二叉树高度的算法工作?

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。

所以，如果你有一个单节点树，分支都报告0，加上1，使其高度为1。如果单节点树有父节点，那么父节点的分支将报告1，而另一个分支可能报告其他内容(假设为0)高度为1或2。以此类推，直到最终得到树的高度。

Answer 2

我猜你在这里纠结的是递归函数是如何工作的。需要注意的重要一点是，GetHeight返回一个int。

如果您检查一个非空的树节点，则评估if(BT)条件，并且您跟随Left和Right指针再次进入GetHeight(添加堆栈帧)。现在,如果Left或Right空你就点击返回0else条件。想象一个叶节点(左右都是null)，HL和HR都是0，因此MaxH将为0,GetHeight将返回1。如果对GetHeight的调用是在递归函数调用中，则该1被传递回调用函数，并且HL或HR现在为1，并且该调用将返回MaxH + 1，直到最终返回到初始调用。通过这种方式，您可以递归地累积答案。