CSP-S 提高级 · CSP 2021 提高级第一轮 第 8 题

令根结点的高度为 $1$，则一棵含有 $2021$ 个结点的二叉树的高度至少为（ ）。

这题就是考完全二叉树的性质。要让高度最小，就得让树尽量‘满’。直接背公式：高度为h时，结点最少要2^(h-1)个，最多能装2^h-1个。把2021夹在中间，算个2的幂次就出来了。

最容易掉进两个坑：一是把根高度记成0，那样公式全乱套；二是分不清‘至少’和‘至多’，题目问的是‘至少多高’，意味着你要构造最紧凑的树（完全二叉树），而不是最松散的（单链）。还有很多人死算2021的二进制位数，其实只要知道2^10=1024、2^11=2048，一眼就能看出2021落在1024到2048之间，高度自然就是11。

这道题考查的是树形结构中完全二叉树的性质，核心就是结点数量与高度之间的对应关系。命题人特别喜欢在这种单选题里挖坑，要么混淆根节点高度的定义（本题明确根高度为1），要么让你分不清‘至少’和‘至多’的语境，或者干脆让你把2021当成二进制位数去数。要避开这些坑，就得先搞清楚概念：一棵高度为h的二叉树，最‘满’的时候（即完全二叉树）能容纳的结点数是2^h - 1；而最‘扁’的时候（即退化成单链），至少要有h个结点才能撑起高度h。所以，对于任意给定的结点数n，如果我们要找它的最小高度h，就必须满足：2^(h-1) ≤ n < 2^h。这个不等式其实就是把n夹在两个2的幂之间，左边是h-1次方的最小值，右边是h次方的最大值。现在把n=2021代进去，我们只需要熟记几个2的幂：2^10 = 1024，2^11 = 2048。一眼就能看出1024 ≤ 2021 < 2048，所以h-1=10，即h=11。如果算错了，比如把根高度当成0，那公式就变成2^h ≤ n < 2^(h+1)，结果就会变成12，这就是典型的定义陷阱。另外，题目问的是‘至少’，意味着我们要让树尽可能紧凑，完全二叉树就是最紧凑的形态；如果问‘至多’，那答案就是2021（单链）。考频方面，树形结构在题库里出现频率很高，26道题覆盖所有级别，而二叉树基础更是重灾区，220道题里2024年和2025年分别考过60题和67题，说明这两年命题人特别喜欢考这类基础但易错的概念。基于这个趋势，未来考试很可能继续以这种‘给数求高度’或‘给高度求范围’的形式出现，甚至可能会结合完全二叉树的层序遍历或数组下标计算来综合考察。总之，记住2的幂次和根高度的定义，这道题就能秒杀。