对应章节：数据结构 → 树与二叉树 → 完全二叉树

结论

• 第 12 题：A. 39

• 第 16 题：B. 248

---

一、先记住两个核心性质

性质 1：完全二叉树除最后一层外，其余各层必须填满

可以理解成：

除最后一层外：全部满
最后一层：允许不满，但必须从左到右连续排列

例如：

        ○
      /   \
     ○     ○
    / \   / \
   ○  ○  ○  ○
  / \ /
 ○  ○ ○

---

性质 2：完全二叉树的叶结点数

若总结点数为 n，则叶结点数为：

ceil(n / 2)

原因是按层序编号后：

1 ~ floor(n/2)      为非叶结点
floor(n/2)+1 ~ n    为叶结点

所以：

叶结点数
= n - floor(n/2)
= ceil(n/2)

---

二、第 12 题

题目：

已知一棵完全二叉树的第 6 层（根为第 1 层）有 8 个叶结点，则完全二叉树的结点个数最少是（ ）。

选项：

A. 39
B. 52
C. 111
D. 119

答案：

A. 39

为什么？

题目问的是“最少”。

为了让总结点数最少，最省结点的办法就是：

让第 6 层直接成为最后一层

这样第 6 层的 8 个结点全部都是叶结点，而且不需要再长第 7 层。

由于完全二叉树除最后一层外必须全满，所以：

第 1 层：1 个
第 2 层：2 个
第 3 层：4 个
第 4 层：8 个
第 5 层：16 个
第 6 层：8 个

因此总结点数：

1 + 2 + 4 + 8 + 16 + 8
= 31 + 8
= 39

所以选：

A. 39

图形理解

第1层                 ○                         1

第2层             ○       ○                     2

第3层          ○   ○   ○   ○                    4

第4层        …… 共 8 个 ……                      8

第5层        …… 共 16 个 ……                    16

第6层        ○ ○ ○ ○ ○ ○ ○ ○                   8
             ↑ 最后一层，从左往右连续

考场识别信号

看到：

完全二叉树
+
第 k 层有若干叶结点
+
问总结点数最少

优先尝试：

让第 k 层直接成为最后一层

---

三、第 16 题

题目：

一棵有 124 个叶结点的完全二叉树，最多有（ ）个结点。

选项：

A. 247
B. 248
C. 249
D. 250

答案：

B. 248

方法 1：直接用叶结点公式

完全二叉树中：

叶结点数 = ceil(n / 2)

题目给：

ceil(n / 2) = 124

那么 n 可能是：

247

因为：

ceil(247 / 2)
= ceil(123.5)
= 124

也可能是：

248

因为：

ceil(248 / 2)
= 124

所以：

n = 247 或 248

题目问“最多”，所以：

n = 248

答案：

B. 248

---

四、为什么 247 和 248 都可以？

完全二叉树中最多只有一个度为 1 的结点。

二叉树还满足：

n0 = n2 + 1

其中：

n0：叶结点数
n1：度为 1 的结点数
n2：度为 2 的结点数

现在：

n0 = 124

因此：

n2 = 123

如果：

n1 = 0

则：

n = n0 + n1 + n2
  = 124 + 0 + 123
  = 247

如果：

n1 = 1

则：

n = 124 + 1 + 123
  = 248

所以完全二叉树有 124 个叶结点时，总结点数只可能是：

247 或 248

问最多：

248

---

五、两题一起记

已知某层叶结点，问总结点数最少

尽量让这一层直接成为最后一层

第 12 题：

1 + 2 + 4 + 8 + 16 + 8
= 39

---

已知叶结点数 n0，问总结点数范围

完全二叉树：

总结点数 = 2n0 - 1
或
总结点数 = 2n0

因此：

最少 = 2n0 - 1
最多 = 2n0

第 16 题：

n0 = 124

最少 = 2×124 - 1 = 247
最多 = 2×124     = 248

---

六、复盘点

复盘点 1

完全二叉树不是满二叉树。

它只要求：

除最后一层外全部填满；
最后一层从左到右连续。

复盘点 2

已知叶结点数时，总结点数通常不唯一。

对于完全二叉树：

n = 2n0 - 1
或
n = 2n0

复盘点 3

第 12 题的“最少”是核心关键词。

一看到“某层有叶结点 + 求最少”，就要想到：

能不能直接让这一层成为最后一层？