---
title: "05-树与二叉树"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 05 树与二叉树

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 5 篇，相关系列见 [[00-基础与理论|基础与理论]]。

线性结构之外，**树是一对多的层级结构**——文件目录、组织架构、HTML DOM、数据库索引全是树。二叉树是它的极简形态：每个结点最多两个孩子，"左右有序"。本章把性质推导、遍历互推、哈夫曼三大块一次讲透——这些都是 408 选择题的题库。

## 一、树的逻辑与术语速览

- **根/叶子/度**：结点的孩子数 = 度；树的度 = 结点最大度
- **有序树 vs 无序树**：兄弟间有无左右之分
- **森林**：m（≥0）棵互不相交的树的集合——树 + 删根 = 森林（后面转换要用）
- **结点层次**从 1 起算；**树高** = 最大层次
- 结点数关系总闸门：**结点数 = 总度数 + 1**（每条边贡献 1 个度，n 个结点 n−1 条边）

## 二、二叉树：五个必背性质（带推导）

1. 第 i 层最多 **2^(i−1)** 个结点（每层翻倍，归纳可证）
2. 高 h 的二叉树最多 **2^h − 1** 个（满二叉树；求和 1+2+4+…+2^(h−1)）
3. **叶子数 n₀ = 度为 2 的结点数 n₂ + 1** ⭐
   
   推导（考场要会写）：总度数 = n₁ + 2n₂；结点数 = n₀ + n₁ + n₂；由"结点数 = 总度数 + 1"：
   n₀ + n₁ + n₂ = n₁ + 2n₂ + 1 → **n₀ = n₂ + 1**
4. 完全二叉树（只允许最后一层缺右侧）高 = ⌈log₂(n+1)⌉ 或 ⌊log₂n⌋ + 1
5. 完全二叉树顺序存储的编号性质（1-based）：结点 i 的**左孩子 2i、右孩子 2i+1、双亲 ⌊i/2⌋**；若 2i > n 则 i 是叶子——**堆**（[[08-排序|排序]]）全靠这条性质

⚠️ 满二叉树（每层都满）⊂ 完全二叉树（最后一层可缺右）。中文教材口径：满二叉树是完全二叉树的特例。

### 手算例题

某完全二叉树有 100 个结点：高度 = ⌊log₂100⌋+1 = **7**；第 7 层结点数 = 100 − 63 = **37**（前 6 层满共 63）；叶结点 = ⌈100/2⌉ = **50**（编号 > ⌊100/2⌋=50 的都无孩子，即 51~100 共 50 个）。

## 三、二叉树的存储

- **顺序存储**：按完全二叉树编号存数组。缺点：非完全二叉树要补"虚结点"，最坏（单斜树）空间 2^n 级浪费——**只适合完全/满二叉树（堆）**
- **链式存储**：

```c
typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode;
// n 个结点的二叉链表共 2n 个指针域，用了 n−1 条边 → 必有 n+1 个空指针
```

💡 **n+1 个空指针**是**线索二叉树**的原材料：把空指针利用起来存遍历前驱/后继，"链"回顺序感。

## 四、遍历：三种序列与互推

### 递归遍历三行代码

```c
void traverse(BiTNode *t) {
    if (!t) return;
    // visit(t);        ← 先序：根左右
    traverse(t->lchild);
    // visit(t);        ← 中序：左根右
    traverse(t->rchild);
    // visit(t);        ← 后序：左右根
}
```

- 记忆：**"先中后"说的是根的位置**；左永远在右前
- 中序遍历 **BST（二叉排序树）得到升序序列**——[[07-查找|查找]] 里要用

### 非递归（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 = \sum_{i} w_i \times l_i \quad (w 权值, \ l 根到该叶子的路径长)$$

**哈夫曼树 = WPL 最小的二叉树**。构造贪心：每次**取权值最小的两棵**合并，重复至只剩一棵。

**手算例题**：权 {1, 2, 3, 4} →

1. 取 1,2 合并成 3 → 集合 {3(新), 3, 4}
2. 取 3,3 合并成 6 → {4, 6}
3. 取 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-字符编码]]的"三大金性质"同源

## 八、盲点自测

1. n₀ = n₂ + 1 怎么证？（结点数 = 总度数 + 1，代入消元）
2. 完全二叉树 200 结点，叶子几个？（⌈200/2⌉ = 100）
3. 先序+后序为什么不能唯一重建？（无法区分独生子是左还是右）
4. 中序线索树里，某结点 rchild 为空，rchild 指什么？（中序后继）
5. 森林转二叉树后，根的右子树是什么？（其余树构成的森林）
6. 哈夫曼树共 201 个结点，叶子几个？（2n−1=201 → n=101）
7. 树的后根遍历对应二叉树哪种遍历？（中序）

## 九、动手玩

```python
# 手算哈夫曼 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
```

## 参考资料

- 王道《数据结构考研复习指导》第 5 章
- 《算法图解》贪心章节——哈夫曼编码的可视化讲法
- [[06-内存管理]]——Buddy 系统的伙伴树、slab 的层次结构，树在 OS 里的影子
- [[00-刷题理模型|刷题理模型]]——树题单（递归三问：边界、左右子树怎么拼、返回什么）

⬅️ [[04-串与KMP|串与KMP]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[06-图|图]]