05 树与二叉树
线性结构之外，树是一对多的层级结构——文件目录、组织架构、HTML DOM、数据库索引全是树。二叉树是它的极简形态：每个结点最多两个孩子，"左右有序"。本章把性质推导、遍历互推、哈夫曼三大块一次讲透——这些都是 408 选择题的题库。
一、树的逻辑与术语速览
- 根/叶子/度：结点的孩子数 = 度；树的度 = 结点最大度
- 有序树 vs 无序树：兄弟间有无左右之分
- 森林：m（≥0）棵互不相交的树的集合——树 + 删根 = 森林（后面转换要用）
- 结点层次从 1 起算；树高 = 最大层次
- 结点数关系总闸门：结点数 = 总度数 + 1（每条边贡献 1 个度，n 个结点 n−1 条边）
二、二叉树：五个必背性质（带推导）
-
第 i 层最多 2^(i−1) 个结点（每层翻倍，归纳可证）
-
高 h 的二叉树最多 2^h − 1 个（满二叉树；求和 1+2+4+…+2^(h−1)）
-
叶子数 n₀ = 度为 2 的结点数 n₂ + 1 ⭐
推导（考场要会写）：总度数 = n₁ + 2n₂；结点数 = n₀ + n₁ + n₂；由"结点数 = 总度数 + 1"： n₀ + n₁ + n₂ = n₁ + 2n₂ + 1 → n₀ = n₂ + 1
-
完全二叉树（只允许最后一层缺右侧）高 = ⌈log₂(n+1)⌉ 或 ⌊log₂n⌋ + 1
-
完全二叉树顺序存储的编号性质（1-based）：结点 i 的左孩子 2i、右孩子 2i+1、双亲 ⌊i/2⌋；若 2i > n 则 i 是叶子——堆（排序）全靠这条性质
⚠️ 满二叉树（每层都满）⊂ 完全二叉树（最后一层可缺右）。中文教材口径：满二叉树是完全二叉树的特例。
手算例题
某完全二叉树有 100 个结点：高度 = ⌊log₂100⌋+1 = 7；第 7 层结点数 = 100 − 63 = 37（前 6 层满共 63）；叶结点 = ⌈100/2⌉ = 50（编号 > ⌊100/2⌋=50 的都无孩子，即 51~100 共 50 个）。
三、二叉树的存储
- 顺序存储：按完全二叉树编号存数组。缺点：非完全二叉树要补"虚结点"，最坏（单斜树）空间 2^n 级浪费——只适合完全/满二叉树（堆）
- 链式存储：
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode;
// n 个结点的二叉链表共 2n 个指针域，用了 n−1 条边 → 必有 n+1 个空指针
💡 n+1 个空指针是线索二叉树的原材料：把空指针利用起来存遍历前驱/后继，"链"回顺序感。
四、遍历：三种序列与互推
递归遍历三行代码
void traverse(BiTNode *t) {
if (!t) return;
// visit(t); ← 先序：根左右
traverse(t->lchild);
// visit(t); ← 中序：左根右
traverse(t->rchild);
// visit(t); ← 后序：左右根
}
- 记忆："先中后"说的是根的位置；左永远在右前
- 中序遍历 BST（二叉排序树）得到升序序列——查找 里要用
非递归（408 上机/面试常问）
- 先序：栈 + 先压右后压左
- 中序：一路向左入栈 → 弹出访问 → 转向右子树
- 后序：最麻烦，用一个
prev记录上一个访问的结点判断右子树是否完成；或"根右左"遍历再整体反转 - 层序遍历用队列：出队访问、左右孩子依次入队——树形的 BFS
互推规则（408 必考）
- 先序 + 中序 → 唯一确定二叉树：先序第一个是根，中序里根左边是左子树、右边是右子树，递归切分
- 后序 + 中序同理（后序最后一个是根）
- ⚠️ 先序 + 后序不能唯一确定（无法区分左右：先序 ab、后序 ba 既可以是"根 a 左孩子 b"也可以是"根 a 右孩子 b"）
- 手算例题：先序 ABC、中序 BAC → 根 A，中序 B|C → 左子树 B、右子树 C → 树：A(左 B, 右 C)，后序 = BCA
五、线索二叉树
把 n+1 个空指针利用起来：
- 中序线索：
lchild空时指前驱，rchild空时指后继（按中序序列） - 需要两个标志位
ltag/rtag（0=孩子，1=线索） - 好处：不递归、不用栈就能按中序遍历——适合"频繁找前驱后继"的场景
- ⚠️ 手算题：给中序序列画线索——记住"前驱=中序序列里它前面那个；后继=后面那个"，指向的可能是祖先也可能跨子树
六、树、森林与二叉树的转换
孩子兄弟表示法是转换的桥梁：结点存 firstchild + nextsibling 两个指针：
- 树 → 二叉树：左指针 = 第一个孩子，右指针 = 右兄弟 → 根的右子树永远为空
- 森林 → 二叉树：每棵树转完，第二棵树作为第一棵根的右兄弟接上
- ⚠️ 反向：二叉树右链 = 森林里树的根序列；手算题常问"转换后根的右子树有几个结点"= 后面所有树的总结点数
树/森林的遍历对应（容易混，背）
| 原结构遍历 | 对应二叉树遍历 |
|---|---|
| 树的先根遍历 | 二叉树的先序 |
| 树的后根遍历 | 二叉树的中序 |
| 森林先序遍历 | 二叉树先序 |
| 森林中序（后根）遍历 | 二叉树中序 |
💡 树没有"中根"（孩子多于 2 个没法切左右）。
七、哈夫曼树与哈夫曼编码
带权路径长度 WPL
哈夫曼树 = WPL 最小的二叉树。构造贪心：每次取权值最小的两棵合并，重复至只剩一棵。
手算例题：权 {1, 2, 3, 4} →
- 取 1,2 合并成 3 → 集合 {3(新), 3, 4}
- 取 3,3 合并成 6 → {4, 6}
- 取 4,6 合并成 10 → 根
WPL = 1×3 + 2×3 + 3×2 + 4×1 = 3+6+6+4 = 19；或（更好算的）非叶结点权值和 = 3 + 6 + 10 = 19 ✅（两条路殊途同归，后者考场更快）
哈夫曼编码
- 树上左 0 右 1，叶子到根的路径即编码——前缀码（任何编码不是另一个的前缀，因为字符都在叶子上，解码无歧义）
- 频率高的字符离根近 → 编码短 → 压缩
- ⚠️ 性质：哈夫曼树没有度为 1 的结点（每次都是二合一）→ n 个叶子的哈夫曼树共 2n − 1 个结点
- 💡 连回04-浮点数的浮点二进制：哈夫曼是"变长编码"，UTF-8 也是变长设计——一个省存储，一个保自同步，05-字符编码的"三大金性质"同源
八、盲点自测
- n₀ = n₂ + 1 怎么证？（结点数 = 总度数 + 1，代入消元）
- 完全二叉树 200 结点，叶子几个？（⌈200/2⌉ = 100）
- 先序+后序为什么不能唯一重建？（无法区分独生子是左还是右）
- 中序线索树里，某结点 rchild 为空，rchild 指什么？（中序后继）
- 森林转二叉树后，根的右子树是什么？（其余树构成的森林）
- 哈夫曼树共 201 个结点，叶子几个？（2n−1=201 → n=101）
- 树的后根遍历对应二叉树哪种遍历？（中序）
九、动手玩
# 手算哈夫曼 WPL 的程序版
import heapq
def huffman_wpl(weights):
h = list(weights)
heapq.heapify(h)
total = 0
while len(h) > 1:
a, b = heapq.heappop(h), heapq.heappop(h)
total += a + b # 非叶结点权值累加 = WPL
heapq.heappush(h, a + b)
return total
print(huffman_wpl([1, 2, 3, 4])) # 19，与手算一致
# 层序遍历（BFS 用队列）
from collections import deque
def level_order(root):
if not root: return []
out, q = [], deque([root])
while q:
node = q.popleft()
out.append(node.data)
if node.lchild: q.append(node.lchild)
if node.rchild: q.append(node.rchild)
return out
💬 评论