CSP-J 入门级 · CSP 2020 入门级第一轮 第 12 题

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

拿到完全二叉树的节点数，别急着套公式，先想满二叉树的节点数规律。完全二叉树的高度只比同高度的满二叉树少一点点，所以只要找到61落在哪个满二叉树的节点数区间里，高度就定下来了。

最容易掉进的坑是死记硬背"高度h的完全二叉树节点数在2^(h-1)到2^h-1之间"这个结论，却不理解为什么。很多学生会把"高度"和"深度"搞混，或者把完全二叉树当成满二叉树去算，导致区间判断错误。还有一种情况是看到61接近64，直觉上觉得高度是7，却忘了完全二叉树最后一层可以不满，所以61完全可以放在高度为6的树里（只要前5层满共31个，第6层放30个就够了）。

这道题考查的是二叉树基础里的完全二叉树高度计算。核心概念很简单：独根树高度为1，高度为h的满二叉树节点数正好是2^h-1；而高度为h的完全二叉树，节点数最少是2^(h-1)（前h-1层满，第h层只有1个），最多就是2^h-1（全满）。命题人喜欢挖的坑就是让你直接套用区间公式，但如果你没理解区间是怎么来的，很容易在边界上出错。

拿到题先想什么？想满二叉树的节点数规律。2^1-1=1，2^2-1=3，2^3-1=7，2^4-1=15，2^5-1=31，2^6-1=63，2^7-1=127。现在题目给了61个节点，我们看它落在哪个区间：61比31大，所以高度至少是6；61比63小，所以高度不会超过6。因此高度就是6。

具体怎么算？列个表更清楚。h=5时，范围[16,31]，61不在；h=6时，范围[32,63]，61正好在里面；h=7时，范围[64,127]，61也不在。所以选D（6）。验算一下：2^5=32≤61≤63=2^6-1，完全吻合。

避坑提醒：别把完全二叉树当成满二叉树去算，也别因为61接近64就误判高度为7。完全二叉树的特点是除了最后一层外其他层都满，最后一层从左到右连续排列，所以节点数可以少到2^(h-1)。考频方面，二叉树基础在题库里共考过220题，覆盖8个级别，其中CSP入门级就考了8次，说明这类纯概念计算题在入门级很常见。趋势上看，2023年突然暴增20题，2024年60题，2025年67题，虽然2026年回落28题，但整体热度极高，命题人明显喜欢用这种区间判断来挖坑。预测未来，这类题大概率还会以选择题形式出现，偶尔可能会结合层序遍历或节点编号来考，但核心的区间判断思路不会变。