NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 8 题

如果根的高度为 $1$，具有 $61$ 个结点的完全二叉树的高度为（ ）。

这题考完全二叉树高度与结点数的关系。拿到题先想高度为h的树最多能装多少叶子，用2的幂次去夹逼61这个数，找到它落在哪一层区间里。

很多学生容易把根高度当成0，或者记反了区间端点，把61当成2^6-1=63就以为高度是6，却忘了63是最大容量，61其实已经跨过了2^5-1=31，所以高度必须是6。还有人会直接拿61开对数得到5.93就四舍五入成6，忽略了完全二叉树最后一层必须填满到左边的特性，导致在边界值上判断失误。

考点概念：完全二叉树的高度

完全二叉树的高度定义是根节点所在层为第1层。对于高度为h的完全二叉树，它的结点数有一个非常漂亮的范围：最少要有2^(h-1)个结点（即前h-1层是满的，第h层只有1个结点），最多可以有2^h-1个结点（即前h层全部填满）。这个范围就是[2^(h-1), 2^h-1]。

命题视角：为什么考这个？

命题人喜欢在这种纯计算题里挖坑，通常有两个地方： 1. 高度定义陷阱：有的题目会把根高度定为0，有的定为1，这里明确说是1，但很多学生习惯从0开始计数，容易算错一层。 2. 边界值陷阱：完全二叉树最后一层不一定满，所以结点总数不能简单用2^h-1去倒推，而是要看它落在哪个区间里。比如61这个数，离63很近，很容易让人误以为高度是6，但必须确认61是否真的超过了高度为5的树的最大容量。