二叉树¶

方法速览¶

任务	方法	口诀
结点关系	$n_0 = n_2 + 1$（叶 = 度2 + 1）	叶多一
高度 h 的结点数	最少 $h$（链形），最多 $2^h - 1$（满）	最少链、最多满
完全二叉树知 n 求高	$h = \lfloor \log_2 n \rfloor + 1$	对数取整加一
顺序存储（根=1）	父 $\lfloor i/2 \rfloor$、左孩子 $2i$、右孩子 $2i+1$	除二找爹、乘二找儿
遍历互推	前序/后序定根，中序分左右	前后给根、中序切半
哈夫曼 WPL	每次合并最小两个；WPL = 所有内部结点权值和	合并和就是 WPL

基本推论¶

设 $n_0, n_1, n_2$ 为度 0/½ 的结点数：

$n_0 = n_2 + 1$。证明（数边）：结点数 $n = n_0+n_1+n_2$；边数 = 孩子数总和 = $n_1 + 2n_2$；树中边数 = $n - 1$。联立：$n_0+n_1+n_2 - 1 = n_1 + 2n_2 \Rightarrow n_0 = n_2 + 1$。

其余推论：

高度 $h$ 的二叉树：最少 $h$ 个结点（每层一个的链），最多 $2^h-1$ 个（满）；
反过来：$n$ 个结点的二叉树高度最大 $n$（链）、最小 $\lceil \log_2(n+1) \rceil$（尽量满）；
第 $i$ 层最多 $2^{i-1}$ 个结点；
边数恒为 $n-1$（每个非根结点贡献一条连向父亲的边）。

例：$n_2 = 5$、$n_1 = 3$，则 $n = n_0 + n_1 + n_2 = (5+1) + 3 + 5 = 14$。

完全二叉树¶

完全二叉树：只在最后一层允许缺结点，且缺失的必须在右边（层序填满靠左）。$n_1 \in \{0, 1\}$（度为 1 的结点至多一个，且它只有左孩子）。

量	公式（根编号 = 1）	例（n = 20）
高度	$h = \lfloor \log_2 n \rfloor + 1$	$\lfloor 4.32 \rfloor + 1 = 5$
结点 i 的父亲	$\lfloor i/2 \rfloor$	9 的父亲 = 4
左孩子 / 右孩子	$2i$ / $2i+1$	9 的孩子 = 18、19
叶子数	$n - \lfloor n/2 \rfloor = \lceil n/2 \rceil$	$20 - 10 = 10$
最后一个非叶	$\lfloor n/2 \rfloor$	10

堆式编号（根 = 0）：左孩子 $2i+1$、右孩子 $2i+2$、父 $\lfloor (i-1)/2 \rfloor$——竞赛代码常用（数组下标天然从 0 开始）。

判断某结点是否叶子：$i > \lfloor n/2 \rfloor$。

满二叉树¶

每一层都全满：高度 $h$ 的满二叉树恰 $2^h - 1$ 个结点、第 $i$ 层恰 $2^{i-1}$ 个。满二叉树是特殊的完全二叉树。

例：$h = 5$：结点 $2^5 - 1 = 31$，第 5 层 $2^4 = 16$ 个（占一半多）。

二叉搜索树¶

BST：左子树所有键 < 根 < 右子树所有键（每棵子树都要满足）。

中序遍历递增——判 BST 的标准手法；
查找/插入从根出发，比目标小走左、大走右，$O(h)$；
删除叶子直接删；删除只有一个孩子的结点让孩子顶上；删除两个孩子的用中序前驱/后继替换。

反例（考点）：根 6，右孩子 8，8 的左孩子 2。“6 < 8、8 > 2、6 > 2”逐对看似乎没问题，但这不是 BST：右子树里的 2 比 6 还小——判断必须整棵子树比根大/小，不是相邻两两比较。

哈夫曼树¶

$n$ 个带权叶子的带权路径长度（WPL, Weighted Path Length）最小的二叉树。构建（贪心）：

每次取出权值最小的两个结点合并成新结点（权 = 两者之和）放回；
重复直到只剩一棵树。

WPL $= \sum \text{叶子权} \times \text{深度} = $ 所有内部结点权值之和（含根）——速算时就等于每次“合并和”的累加。

例：权 $\{10, 12, 15, 20, 25\}$：

合并次序	取出	合并和
1	10 + 12	22
2	15 + 20	35
3	22 + 25	47
4	35 + 47	82

WPL $= 22 + 35 + 47 + 82 = 186$。

三条性质：

根的权值 = 所有叶子权值之和（上例 $10+12+15+20+25 = 82$，恰等于根的权值）；
形态不唯一：同权合并顺序不同/左右孩子互换（镜像），但 WPL 唯一；
应用：哈夫曼编码（网络传输压缩）——频率高的字符编码短，任何编码不是其他的前缀。

前中后序、层序遍历与互推¶

遍历	顺序	根的位置
前序（先序）	根 → 左 → 右	第一个
中序	左 → 根 → 右	中间
后序	左 → 右 → 根	最后
层序	一层一层（队列）	—

互推核心口诀：前序/后序找根，中序切左右。

例（前 + 中 → 后）：前序 ABDECFG、中序 DEBAFCG 求后序：

步骤	根	中序切分	结构
1	A（前序首位）	`DEB` \| A \| `FCG`	分出左右子树
2（左）	B（前序 `BDE` 首位）	`DEB` 中 B 在末尾：`DE` \| B \| 空	D、E 全在 B 的左子树
3（左·左）	D（前序 `DE` 首位）	`DE` 中 D 在开头：空 \| D \| `E`	D 只有右孩子 E
4（右）	C	`FCG`：F \| C \| G	C(F, G)

左子树结构是 B(D(右 E), 无右)：后序先 E 后 D 再 B = EDB（不是 DEB——DEB 是中序）；右子树后序 FGC。后序 = EDB + FGC + A = EDBFGCA。

前 + 后不能唯一确定：两个结点 A、B，前序 AB、后序 BA——B 可以是 A 的左孩子也可以是右孩子，两棵树同前后序；
层序：队列实现——根入队，出队访问，左右孩子依次入队。

练习题目¶

练习 1 · n0 与 n2 的关系¶

题目

一棵二叉树中度为 2 的结点有 7 个，则叶子结点有（）个。

A. $6$
B. $7$
C. $8$
D. $9$

答案与解析

答案：C

$n_0 = n_2 + 1 = 8$，与 $n_1$ 无关。

练习 2 · 反用 n0=n2+1¶

题目

某二叉树有 10 个叶子、$n_1 = 4$ 个度为 1 的结点，总结点数为（）

A. $23$
B. $22$
C. $24$
D. $14$

答案与解析

答案：A

$n_2 = n_0 - 1 = 9$；$n = 10 + 4 + 9 = 23$。

练习 3 · 高度 h 的结点范围¶

题目

高度为 5 的二叉树最多有（）个结点。

A. $16$
B. $31$
C. $32$
D. $63$

答案与解析

答案：B

最多 $2^5 - 1 = 31$（满二叉树）。

干扰项思路：C 是 $2^h$，忘了减 1（把“满”多算了一个结点）。

练习 4 · 高度 h 的最少结点¶

题目

高度为 6 的二叉树最少有（）个结点。

A. $32$
B. $7$
C. $11$
D. $6$

答案与解析

答案：D

每层恰好一个结点的“链”最少：$h$ 个。

练习 5 · 第 i 层上限¶

题目

二叉树第 6 层（根为第 1 层）最多有（）个结点。

A. $32$
B. $64$
C. $16$
D. $63$

答案与解析

答案：A

第 $i$ 层最多 $2^{i-1}$：$2^5 = 32$。

练习 6 · 完全二叉树的概念¶

题目

关于完全二叉树，说法错误的是（）

A. 只允许最后一层缺结点，且缺在右边
B. 度为 1 的结点至多一个
C. n 个结点的完全二叉树高度为 $\lfloor \log_2 n \rfloor + 1$
D. 完全二叉树一定是满二叉树

答案与解析

答案：D

满反过来是特殊的完全（全满），完全不一定是满。

练习 7 · 知 n 求高¶

题目

100 个结点的完全二叉树高度为（）

A. $6$
B. $8$
C. $7$
D. $5$

答案与解析

答案：C

$\lfloor \log_2 100 \rfloor + 1 = 6 + 1 = 7$（$2^6 = 64 \le 100 < 128 = 2^7$）。

练习 8 · 顺序存储找父亲¶

题目

根存下标 1，则下标 23 的结点的父亲是（）

A. $11$
B. $12$
C. $10$
D. $46$

答案与解析

答案：A

$\lfloor 23/2 \rfloor = 11$。

练习 9 · 顺序存储找孩子¶

题目

根存下标 1，下标 11 的左右孩子分别是（）

A. $12$、$13$
B. $23$、$24$
C. $22$、$23$
D. $22$、$22$

答案与解析

答案：C

左 $2i = 22$、右 $2i+1 = 23$。

练习 10 · 根 0 编号¶

题目

根存下标 0，下标 7 的结点的左孩子与父亲是（）

A. 左 $14$、父 $3$
B. 左 $15$、父 $3$
C. 左 $14$、父 $4$
D. 左 $15$、父 $2$

答案与解析

答案：B

根 0 版：左孩子 $2i+1 = 2\times7+1 = 15$，父亲 $\lfloor (7-1)/2 \rfloor = 3$。

练习 11 · 判断叶子¶

题目

30 个结点的完全二叉树（根存下标 1），下标（）是叶子。

A. $12$
B. $15$
C. $16$
D. $10$

答案与解析

答案：C

最后一个非叶是 $\lfloor 30/2 \rfloor = 15$；$i > 15$ 全是叶子，16 是最小的叶子下标。

练习 12 · 完全二叉树叶子数¶

题目

25 个结点的完全二叉树有（）个叶子。

A. $12$
B. $11$
C. $12$ 或 $13$
D. $13$

答案与解析

答案：D

叶子 $= n - \lfloor n/2 \rfloor = 25 - 12 = 13$（即 $\lceil n/2 \rceil$）。

练习 13 · 满二叉树结点数¶

题目

高度 4 的满二叉树有（）个结点。

A. $15$
B. $16$
C. $31$
D. $8$

答案与解析

答案：A

$2^4 - 1 = 15$。

练习 14 · 满二叉树的叶¶

题目

高度 h 的满二叉树，叶子数与总结点数之比为（）

A. $\dfrac{1}{3}$
B. $\dfrac{1}{2}$
C. $\dfrac{2^{h-1}}{2^h - 1}$，略大于一半
D. $\dfrac{2^h - 1}{2^h}$

答案与解析

答案：C

叶子 $2^{h-1}$、总 $2^h-1$，叶子超过一半（h=4 时 8/15）。

练习 15 · BST 的定义¶

题目

二叉搜索树的定义是（）

A. 每个结点的键大于左孩子、小于右孩子即可
B. 每个结点左子树全部键 < 根 < 右子树全部键（所有子树递归满足）
C. 树是完全二叉树
D. 中序遍历递减

答案与解析

答案：B

A 是经典陷阱：只比相邻结点不够，要整棵子树比；D 反了，中序递增。

练习 16 · BST 的反例¶

题目

根为 6，右孩子为 8，8 的左孩子为 2。这棵树（）

A. 是 BST，因为 6 < 8 且 8 > 2
B. 不是 BST，因为右子树中出现了比根 6 小的 2
C. 是 BST，因为 2 < 8
D. 无法判断

答案与解析

答案：B

BST 要求右子树所有结点大于根；2 挂在 6 的右子树里却小于 6，违规。

练习 17 · BST 中序¶

题目

依次插入 $5, 3, 8, 1, 4, 7, 9$ 建 BST，中序遍历结果是（）

A. 5 3 8 1 4 7 9
B. 1 4 3 5 9 8 7
C. 9 8 7 5 4 3 1
D. 1 3 4 5 7 8 9

答案与解析

答案：D

BST 中序 = 升序排序——这也是“BST 中序遍历即排序”的出处。

练习 18 · BST 查找路径¶

题目

上题的 BST 中查找 4，依次比较的键是（）

A. 5 3 4
B. 5 8 4
C. 5 3 1 4
D. 3 4

答案与解析

答案：A

4 < 5 走左到 3；4 > 3 走右到 4，命中——每层一次比较。

练习 19 · BST 删除叶子¶

题目

从 BST 删除一个叶子结点，正确操作（）

A. 需要旋转整棵树
B. 直接摘除，其父亲对应孩子置空
C. 用中序后继替换再连删两次
D. 不能删除叶子

答案与解析

答案：B

叶子无孩子，摘掉不影响其余结构；删两孩子结点才需要前驱/后继替换。

练习 20 · 哈夫曼构建第一步¶

题目

权值 $\{3, 5, 8, 2, 9\}$ 构建哈夫曼树，第一次合并的是（）

A. $3$ 和 $5$
B. $2$ 和 $3$
C. $8$ 和 $9$
D. $2$ 和 $9$

答案与解析

答案：B

每次取最小两个：2 和 3 合并成 5。

练习 21 · WPL 计算¶

题目

权值 $\{1, 2, 3, 4, 5\}$ 的哈夫曼树 WPL 是（）

A. $30$
B. $33$
C. $35$
D. $40$

答案与解析

答案：B

合并序列：$1+2=3$，$3+3=6$，$4+5=9$，$6+9=15$；WPL $= 3+6+9+15 = 33$。

验算（按深度）：$1\times3 + 2\times3 + 3\times2 + 4\times2 + 5\times2 = 33$ ✓。

练习 22 · 根的权值¶

题目

权值 $\{2, 4, 6, 8\}$ 的哈夫曼树，根的权值是（）

A. $20$
B. $10$
C. $24$
D. $16$

答案与解析

答案：A

根 = 所有叶子之和 $= 2+4+6+8 = 20$（与合并顺序无关）。

练习 23 · 形态不唯一¶

题目

关于哈夫曼树，正确的是（）

A. 形态唯一
B. 形态不唯一（如镜像），但 WPL 唯一
C. WPL 与形态都随合并顺序变化
D. 一定是一棵满二叉树

答案与解析

答案：B

同权时合并搭配/左右位置可有多种，但最优 WPL 相同。

练习 24 · 哈夫曼编码性质¶

题目

哈夫曼编码的重要性质是（）

A. 所有字符编码等长
B. 必须用三位二进制
C. 高频字符编码更长
D. 任何字符的编码都不是另一个字符编码的前缀（前缀无关）

答案与解析

答案：D

前缀无关才能无歧义解码；且高频字符编码短（C 反了）。

练习 25 · 前序定根¶

题目

前序遍历 ABDECFG 的第一个字符是（）

A. 左子树的根
B. 整棵树的根
C. 最深的叶子
D. 中序的第一个字符

答案与解析

答案：B

前序 = 根左右，首位必是根——这就是“前序定根、中序切分”还原法的起点。

练习 26 · 前+后不能唯一¶

题目

只给前序 AB 和后序 BA，能确定的二叉树有（）棵。

A. $0$
B. $1$
C. $2$
D. 无穷多

答案与解析

答案：C

B 是 A 的左孩子或右孩子，两棵都符合——没有中序就切不开左右。

练习 27 · 层序的队列¶

题目

层序遍历借助的数据结构是（）

A. 栈
B. 哈希表
C. 堆
D. 队列

答案与解析

答案：D

出队访问后左右孩子依次入队——先来先服务正是队列；栈对应深度优先（前中后序）。

练习 28 · 中+后还原前序¶

题目

已知后序遍历为 DEBFCA，中序遍历为 DBEACF，前序遍历是（）

A. ABDECF
B. ABDEFC
C. ADBECF
D. AEDBCF

答案与解析

答案：A

后序末位 A 是根；中序切分 DBE|A|CF：

子树	后序	中序	结构
左（根 B）	DEB	DBE	B(D, E)，前序 BDE
右（根 C）	FC	CF	C 只有右孩子 F，前序 CF

前序 = A + BDE + CF = ABDECF。

历年真题¶

2019 年 · 第 14 题¶

题目

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（）。

A. ABDEGJHCFI
B. ABDEGHJFIC
C. ABCDEFGHIJ
D. ABDEGHJCFI

答案与解析

答案：D

后序末位 A 是根；中序切分 DBGEHJ | A | CIF：

子树	后序	中序	结构	前序
A 的左	DGJHEB	DBGEHJ	B 的左 D；B 的右是 E(G, H(右 J))	`BDEGHJ`
A 的右	IFC	CIF	C 的右 F，F 的左 I	`CFI`

逐层定位：左子树后序末位是 B → B 为根；中序里 B 前面只有 D → D 是 B 的左孩子；剩下 GEHJ 挂 B 的右边，其后序 GJHE 末位 E 为根，中序切出 G 在左、HJ 在右……拼前序 = A + BDEGHJ + CFI = ABDEGHJCFI。

2020 年 · 第 12 题¶

题目

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

A. $7$
B. $8$
C. $5$
D. $6$

答案与解析

答案：D

$\lfloor \log_2 61 \rfloor + 1 = 5 + 1 = 6$（$2^5 = 32 \le 61 < 64 = 2^6$，即高 5 最多 31 个、高 6 最多 63 个——61 挤在第 6 层）。

2022 年 · 第 7 题¶

题目

假设字母表 {a, b, c, e, d} 在字符串出现的频率分别为 10%、15%、30%、16%、29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（）位。

A. $1$
B. $2$
C. $2$ 或 $3$
D. $3$

答案与解析

答案：B

合并过程：$10+15=25$；$25+16=41$；$29+30=59$；$41+59=100$。字母 d 的频率是 29%，在第三次合并（$29+30=59$）时并入，父结点 59 是根的孩子 → d 的深度为 2 → 编码 2 位。

2023 年 · 第 6 题¶

题目

给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBAFCG。请问这棵树的正确后序遍历结果是什么？（）

A. EDBFGCA
B. EDBGCFA
C. DEBGFCA
D. DBEGFCA

答案与解析

答案：A

前序首位 A 为根；中序切分 DEB|A|FCG：

子树	前序	中序	结构	后序
左（根 B）	BDE	DEB	B 的左孩子 D，D 只有右孩子 E	EDB
右（根 C）	CFG	FCG	C 的左孩子 F，右孩子 G	FGC

左子树后序演算（易错点）：B(D, E·) 中 D 只有右孩子 E，先访问右再访问根——后序是 EDB，不是 DEB（DEB 是中序）。

后序 = EDB + FGC + A = EDBFGCA。

2024 年 · 第 8 题¶

题目

一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。

A. 8、18
B. 10、18
C. 8、19
D. 10、19

答案与解析

答案：C

结点 9 = $2\times4+1$，是 4 的右孩子 → 兄弟（左孩子）= 8；右孩子 = $2\times9+1 = 19$。

2024 年 · 第 12 题¶

题目

已知二叉树的前序遍历为 [A, B, D, E, C, F, G]，中序遍历为 [D, B, E, A, F, C, G]，请问该二叉树的后序遍历结果是？（）

A. [D, E, B, F, G, C, A]
B. [D, E, B, F, G, A, C]
C. [D, B, E, F, G, C, A]
D. [D, E, B, F, G, A, C]

答案与解析

答案：A

A 为根，中序切 DBE|A|FCG；左子树（前序 BDE、中序 DBE）→ B(D, E)，后序 DEB；右子树（前序 CFG、中序 FCG）→ C(F, G)，后序 FGC。合计 DEB + FGC + A。

2025 年 · 第 4 题¶

题目

用 $5$ 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？（）

A. $176$
B. $186$
C. $196$
D. $206$

答案与解析

答案：B

合并：$10+12=22$，$15+20=35$，$22+25=47$，$35+47=82$；WPL $= 22+35+47+82 = 186$（内部结点之和速算法）。

2025 年 · 第 14 题¶

题目

一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？（）

A. $499$
B. $512$
C. $500$
D. $501$

答案与解析

答案：C

叶子 $= n - \lfloor n/2 \rfloor = 1000 - 500 = 500$（$\lceil n/2 \rceil$）。

易错小结¶

$n_0 = n_2 + 1$ 与 $n_1$ 无关；$n = n_0+n_1+n_2$ 联立可解任意缺项；
高度 $h$：最少 $h$、最多 $2^h-1$；知 $n$ 求高 $\lfloor\log_2 n\rfloor + 1$（只对完全二叉树成立）；
顺序存储根 1 版：父 $\lfloor i/2\rfloor$、左 $2i$、右 $2i+1$；根 0 版：左 $2i+1$、右 $2i+2$、父 $\lfloor(i-1)/2\rfloor$——两套别混；
BST 要整棵子树比根，不是相邻两两比；中序 = 升序；
哈夫曼：WPL = 合并和累加 = 内部结点权和；根 = 叶权和；形态不唯一但 WPL 唯一；
前+中或后+中可唯一还原；前+后不行（左右切不开）；
层序用队列，前中后序是深度优先（递归/栈）。

任务	方法	口诀
结点关系	\(n_0 = n_2 + 1\)（叶 = 度2 + 1）	叶多一
高度 h 的结点数	最少 \(h\)（链形），最多 \(2^h - 1\)（满）	最少链、最多满
完全二叉树知 n 求高	\(h = \lfloor \log_2 n \rfloor + 1\)	对数取整加一
顺序存储（根=1）	父 \(\lfloor i/2 \rfloor\)、左孩子 \(2i\)、右孩子 \(2i+1\)	除二找爹、乘二找儿
遍历互推	前序/后序定根，中序分左右	前后给根、中序切半
哈夫曼 WPL	每次合并最小两个；WPL = 所有内部结点权值和	合并和就是 WPL

量	公式（根编号 = 1）	例（n = 20）
高度	\(h = \lfloor \log_2 n \rfloor + 1\)	\(\lfloor 4.32 \rfloor + 1 = 5\)
结点 i 的父亲	\(\lfloor i/2 \rfloor\)	9 的父亲 = 4
左孩子 / 右孩子	\(2i\) / \(2i+1\)	9 的孩子 = 18、19
叶子数	\(n - \lfloor n/2 \rfloor = \lceil n/2 \rceil\)	\(20 - 10 = 10\)
最后一个非叶	\(\lfloor n/2 \rfloor\)	10