在一棵完全二叉树中，含有 n0 个叶结点，当度为1的结点数为1时，该树的高度是多少？当度为1的结点数为0时，该树的高度是多少？

[tag_link]

参考答案

当n1=1时，n=2n0，h=floor(log2 n0)+2；当n1=0时，n=2n0−1，h=ceil(log2 n0)+1。

推导过程

由n2=n0−1及n=2n0+n1−1，分别代入完全二叉树的层容量边界得到两种高度。

评分要点

写出n2=n0−1；分别代入n1=1/0；说明取整与层次从1开始。

易错点

把树高、深度和边数口径混用。