E5 树与二叉树

对应大纲： 2.1.3-2 简单树、2.1.3-3 特殊树（完全二叉树、哈夫曼树、二叉搜索树）

⚠️ 19 套真题里有 18 套考了二叉树——这是初赛的第一大数据结构考点。 S0 说「不必现在学」的那句话，对第一轮是致命的。

一、基本概念（先统一术语）

术语	含义
根	唯一没有父亲的结点
叶子	没有孩子的结点
度	一个结点的孩子个数；树的度 = 所有结点度的最大值
深度 / 高度	从根到该结点的层数
子树	某个结点及其所有后代构成的树

⚠️ 「根的高度算 1 还是算 0」不统一！题目一定会写明，务必先找那句话。 CSP 2021 第 8 题、CSP 2020 第 12 题、CSP 2023 第 5 题都专门写了「根节点的高度为 1」——就是因为按另一种约定答案会差 1，而差 1 的那个数一定在选项里。

基本性质：

$n$ 个结点的树有 $n-1$ 条边
二叉树：每个结点最多 2 个孩子，且区分左右

二叉树的计数性质（必背）

性质	公式
第 $i$ 层最多结点数	$2^{i-1}$ （根为第 1 层）
高度 $h$ 的二叉树最多结点数	$2^h - 1$
度为 0 的结点数 $n_0$ 与度为 2 的结点数 $n_2$	$n_0 = n_2 + 1$

📝 $n_0 = n_2 + 1$ 这条经常单独出题，记住它。

二、★ 三种遍历（最高频）

遍历	顺序	结果
前序（先根）	根 → 左 → 右	`A B D E C F`
中序（中根）	左 → 根 → 右	`D B E A C F`
后序（后根）	左 → 右 → 根	`D E B F C A`

★ 由两种遍历还原第三种（每年考）

唯一的方法：

前序的第一个 / 后序的最后一个 = 根。 拿这个根去中序里切一刀，左边是左子树、右边是右子树。 然后对两半递归。

例（CSP 2024 第 12 题）：前序 ABDECFG、中序 DBEAFCG

根 = A；中序切开：左 DBE、右 FCG
左子树前序 BDE → 根 B，中序 DBE → 左 D、右 E
右子树前序 CFG → 根 C，中序 FCG → 左 F、右 G
后序 = D E B F G C A ✓

⚠️ 必须有中序！ 前序 + 后序不能唯一确定一棵二叉树。

📝 秒杀技巧：

想求	先看
后序	最后一位必是根（= 前序的第一位）
前序	第一位必是根（= 后序的最后一位）
后序的第一位	「最左下角的那个叶子」

CSP 2023 第 11 题四个选项结尾都是 A，那招不管用——就改看第一位（E），立刻砍掉两个。

⚠️ 别因为去年做过就套上一年的树形。 CSP 2024 那棵是漂亮的满二叉树，CSP 2023 那棵是歪的——每次都要老实建树。

三、完全二叉树（考得最多的特殊树）

定义：除最后一层外每层都填满，且最后一层的结点从左往右连续排列（中间不许留空）。

⚠️ 完全二叉树 ≠ 满二叉树。 满二叉树每层都填满（结点数恰为 $2^h - 1$ ）。

★ 顺序存储的三个公式（根编号为 1）

$\text{左孩子} = 2i \qquad \text{右孩子} = 2i+1 \qquad \text{父亲} = \left\lfloor \frac{i}{2} \right\rfloor$

推论：

问	答
编号 $i$ 的兄弟	$i$ 为偶数 → 兄弟是 $i+1$ ； $i$ 为奇数 → 兄弟是 $i-1$
$n$ 个结点，有孩子的结点	编号 $1 \sim \lfloor n/2 \rfloor$
叶子数	$\lceil n/2 \rceil$
高度（根为 1）	$\lfloor \log_2 n \rfloor + 1$

例题速算：

CSP 2025 第 14 题：1000 个结点 → 叶子 $= \lceil 1000/2 \rceil = \mathbf{500}$
CSP 2020 第 12 题：61 个结点 → 高度 $= \lfloor\log_2 61\rfloor + 1 = 5+1 = \mathbf{6}$ （ $2^5-1=31 < 61 \le 63$ ）
CSP 2022 第 8 题：第 9 个位置的兄弟和右孩子 → $9$ 是奇数，兄弟 $= 8$ ；右孩子 $= 2\times9+1 = \mathbf{19}$
CSP 2021 第 8 题：高度为 5 的完全二叉树有几种形态？结点数只能是 $16 \sim 31$ ，每个结点数对应唯一形态 → $\mathbf{16}$ 种

📝 最后那条洞察很值钱：完全二叉树的「结点数 ⇄ 形状」是一一对应的。

⚠️ 顺序存储对非完全二叉树极其浪费。 CSP 2019 第 8 题：一棵只有 6 个结点、但向右下歪的树，数组要开到下标 15。这正是「只有完全二叉树才适合顺序存储」的原因。

四、哈夫曼树与哈夫曼编码

构造：每次取出权值最小的两个合并，新结点权值 = 两者之和，放回去；重复到只剩一个。

带权路径长度（WPL） = $\sum (\text{叶子权值} \times \text{叶子深度})$

★ 两个必杀技

技巧一：WPL = 所有「合并出来的新结点」权值之和。

不用画树、不用数深度，把每次合并的和累加起来就是答案。

CSP 2025 第 4 题：权值 $10,12,15,20,25$

步	合并	新权
1	$10+12$	22
2	$15+20$	35
3	$22+25$	47
4	$35+47$	82

$\text{WPL} = 22+35+47+82 = \mathbf{186}$

技巧二：给编码选项时，算各选项的加权长度，最小的那个就是哈夫曼编码。

因为哈夫曼编码的定义就是「加权路径长度最小的前缀码」。这比构树再逐个比对快得多。

更快的一步筛法：频率最高的字符，码长必须最短。 CSP 2023 第 10 题里只有选项 A 给频率 45% 的字符 1 位编码——一眼选出。

⚠️ 哈夫曼编码是前缀码：任何一个编码都不是另一个的前缀（保证解码不歧义）。

⚠️ 哈夫曼树的形状可能不唯一（权值相等时），但每个字符的码长是确定的。CSP 2022 第 7 题的选项 C「2 或 3」就是给「感觉不确定」的人准备的陷阱——必须真做一遍合并。

📝 哈夫曼本质上是贪心算法（CSP 2021 第 11 题）。

五、二叉搜索树（BST）

定义：每个结点的左子树全部小于它、右子树全部大于它。

三条必知性质

中序遍历 BST 得到的是升序序列 ← 最常考
查找 / 插入 / 删除的复杂度是 $O(h)$ ， $h$ 是树高
最坏情况会退化成一条链（按有序数据依次插入时），复杂度变 $O(n)$

📝 正因为会退化，才有了平衡树（AVL、红黑树）——那是提高级内容，初赛认识名字即可。

⚠️ 「BST 的中序遍历是有序的」这条经常被用来出反向题：给你一个中序序列问是不是 BST，或者给你一棵树问是不是 BST。判定方法就是做一遍中序遍历看是否升序。

六、其他树的常识

概念	要点
森林	若干棵不相交的树
树的孩子兄弟表示法	把多叉树转成二叉树：左指针指长子、右指针指兄弟
三叉树 / $k$ 叉树	高度 $h$ 最多 $\dfrac{k^h - 1}{k-1}$ 个结点

CSP 2023 第 5 题：2023 个结点的三叉树最小高度？

高度	最多结点 $\frac{3^h-1}{2}$
7	1093 —— 装不下
8	3280 —— 装得下 ✓

📝 「高度至少为多少」= 把树塞满看第几层够用；「高度至多为多少」= 排成一条链 = 结点数。

30 秒自测

前序 ABDECFG + 中序 DBEAFCG，后序是什么？
前序 + 后序能唯一确定一棵二叉树吗？
完全二叉树中，编号 $i$ 的左孩子、右孩子、父亲各是几号？
1000 个结点的完全二叉树有几个叶子？高度是多少？
权值 $10,12,15,20,25$ 的哈夫曼树，WPL 是多少？用什么最快算法？
哈夫曼编码为什么必须是前缀码？
二叉搜索树的中序遍历有什么性质？最坏会退化成什么？
$n_0$ 和 $n_2$ 有什么关系？

参考答案

D E B F G C A
不能，必须有中序
$2i$ / $2i+1$ / $\lfloor i/2 \rfloor$
叶子 $\lceil 1000/2 \rceil = 500$ ；高度 $\lfloor\log_2 1000\rfloor + 1 = 10$
186；把每次合并产生的新结点权值全加起来
否则解码时会有歧义（分不清一个编码在哪结束）
升序；最坏退化成一条链，复杂度变 $O(n)$
$n_0 = n_2 + 1$