NOIP 普及组初赛 · NOIP 2015 普及组初赛试题 第 17 题

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

这题就是考完全二叉树高度公式。拿到61这个数，脑子里先闪一下2的幂次方：32、64。61夹在中间，说明层数得是6。别急，把公式套进去算一遍，再回头验证下5层能不能装下61个节点，这样心里就踏实了。

最容易栽跟头的就是死记硬背公式却忘了根高度定义。有的同学看到n=61，直接算log2(61)≈5.9，然后四舍五入或者想当然地以为高度是5，结果选错。还有的同学不去验证，光凭感觉觉得61接近64就选6，万一题目给的是31呢？31也是接近32，但高度是5。所以必须用不等式验证：2^(h-1)-1 < n ≤ 2^h-1，这是判断高度的金标准。

考点直击

这道题考查的是完全二叉树的高度计算，核心知识点就一个公式：若根节点高度定义为1，则高度 h = ⌊log₂ n⌋ + 1。

概念拆解

什么是完全二叉树？简单说，就是除了最后一层，其他层都排满了，最后一层也是从左往右排，没有空缺。这种结构最紧凑，所以高度公式很整齐。