CSP-J 入门级 · CSP 2026 入门级第一轮 第 5 题

【单选】一棵有 100 个结点的完全二叉树，其中叶子结点个数是（ ）。

完全二叉树按层序编号 1..n 后，编号 i > ⌊n/2⌋ 的结点全是叶子；也可以按"最后一个非叶结点是 ⌊n/2⌋"直接得叶子数 = n − ⌊n/2⌋。

把"满二叉树"的公式 2^(h−1) 硬套到"完全二叉树"上；或忘记 100 不是 2 的幂，最后一层没铺满。

解析

本题考查完全二叉树的性质（结点总数与叶子数的关系）。

方法一：编号法（最快）

把完全二叉树按层序从 1 开始编号，则对编号为 i 的结点：

• 左孩子编号 2i，右孩子编号 2i+1；
• 因此 i > ⌊n/2⌋ 的结点没有孩子，都是叶子。

n = 100 时，⌊100/2⌋ = 50，所以编号 51～100 共 50 个结点是叶子，选 B。

方法二：逐层计数（互相印证）

• 前 6 层是满的：1 + 2 + 4 + 8 + 16 + 32 = 63 个结点，编号 1～63；
• 剩下的 100 − 63 = 37 个结点铺在第 7 层，编号 64～100；
• 第 6 层（编号 32～63，共 32 个结点）中，谁的编号 i 满足 2i ≤ 100 谁才有孩子，即 i ≤ 50 → 编号 32～50 共 19 个结点有孩子，编号 51～63 共 13 个是叶子；
• 叶子总数 = 第 7 层的 37 + 第 6 层的 13 = 50 ✓ 与编号法一致。

结论：叶子数 = n − ⌊n/2⌋ = 100 − 50 = 50，选 B。

记忆点

• 完全二叉树：叶子数 = ⌈n/2⌉；度为 1 的结点最多 1 个；
• 高度 h = ⌊log₂n⌋ + 1，本题 h = 7（因为 2^6 − 1 = 63 < 100 ≤ 127 = 2^7 − 1）；
• 千万不要把完全二叉树当满二叉树用——2^(h−1) = 64 正是本题的经典错选 C。