考研 408 · 树核心知识点
考研 408 · 树核心知识点
树是 408 数据结构大题高发区：性质 → 遍历 → BST/AVL → 哈夫曼 → 并查集。
1. 二叉树基本性质
① 第 i 层至多 2^(i−1) 个结点
② 深度为 k 的二叉树至多 2^k − 1 个结点
③ 叶子数 n₀ = 度为 2 结点数 n₂ + 1
④ 完全二叉树 n 个结点：深度 = ⌊log₂n⌋ + 1
⑤ 顺序存储（完全二叉树）：i 的左孩子 2i、右孩子 2i+1、父 ⌊i/2⌋二叉树的形态数
n 个结点的不同二叉树形态数 = 卡特兰数 C(n) = C(2n,n)/(n+1)2. 遍历
递归序（先/中/后）
先序：根 → 左 → 右 DLR
中序：左 → 根 → 右 LDR
后序：左 → 右 → 根 LRD
层序：逐层从左到右图示
1
/ \
2 3
/ \ \
4 5 6
先序: 1 2 4 5 3 6
中序: 4 2 5 1 3 6
后序: 4 5 2 6 3 1
层序: 1 2 3 4 5 6由遍历序列确定二叉树
必须知道中序 + （先序 或 后序 之一）
先序/后序确定根，中序划分左右子树
层序 + 中序亦可非递归遍历要点
// 先序非递归：栈
push(root);
while (!stack.empty()) {
node = pop(); visit(node);
if (node->right) push(node->right);
if (node->left) push(node->left);
}
// 层序：队列
enqueue(root);
while (!queue.empty()) {
node = dequeue(); visit(node);
if (node->left) enqueue(node->left);
if (node->right) enqueue(node->right);
}3. 线索二叉树
利用空指针域：
ltag = 0 左孩子 / 1 前驱；rtag = 0 右孩子 / 1 后继中序线索化后，可快速找某结点的中序前驱/后继，遍历不需要栈。
4. 二叉排序树 BST
左子树 < 根 < 右子树| 操作 | 平均复杂度 |
|---|---|
| 查找 / 插入 / 删除 | O(log n)（树高） |
| 最坏（退化为链） | O(n) |
删除三种情况：叶子直接删；单孩子提升；双孩子用前驱或后继替换。
5. 平衡二叉树 AVL
平衡因子 = 左子树高 − 右子树高，绝对值 ≤ 1。
插入后失衡四种调整：
LL：右旋 RR：左旋
LR：先左旋再右旋 RL：先右旋再左旋图示（LL 右旋）
3 2
/ 右旋 / \
2 ─────▶ 1 3
/
1最小失衡子树调整后，整棵树恢复平衡；AVL 查找/插入/删除均 O(log n)。
6. 红黑树（408 要求掌握性质与插入过程）
① 结点非红即黑
② 根是黑色
③ 叶子（外部空结点）黑色
④ 红结点的两个孩子必为黑（无连续红）
⑤ 任一结点到其所有后代叶子的路径含相同数目的黑结点（黑高相等）插入调整：先染红新结点，再按叔结点颜色分情况 变色 / 旋转；根始终染黑。
红黑树高度 ≤ 2·log₂(n+1)，保证 O(log n) 平衡查找。
7. 哈夫曼树与编码
构造
每次取权值最小的两棵树合并，新根权 = 两者之和，重复至一棵树。性质
WPL = Σ(叶权 × 路径长度) 最小
只有度为 0 和 2 的结点：n 个叶子 ⇒ 2n−1 个结点示例（权 7 5 2 4）
18
/ \
7 11
/ \
5 6
/ \
2 4
编码（左 0 右 1）：
7 → 0 5 → 10
2 → 110 4 → 111
WPL = 7×1 + 5×2 + 2×3 + 4×3 = 35哈夫曼编码是最优前缀编码（任一编码不是另一编码的前缀）。
8. 树 / 森林 ↔ 二叉树
孩子兄弟表示法：
左孩子指针 = 第一个孩子；右孩子指针 = 下一个兄弟
森林转二叉树：各树根依次作为右子树连接树的先序 = 对应二叉树的先序；树的后序 = 对应二叉树的中序。
9. 并查集
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
void unionSet(int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) parent[ra] = rb; // 可加按秩合并
}用途：判断连通分量、Kruskal 判环、集合合并。路径压缩 + 按秩合并后近似 O(α(n))。
10. 堆
大根堆：parent ≥ children；小根堆：parent ≤ children
存储：完全二叉树顺序存储，下标 1 开始| 操作 | 复杂度 |
|---|---|
| 建堆 | O(n) |
| 插入 / 删除堆顶 | O(log n) |
| 堆排序 | O(n log n) |
11. 常考题型
- 由先序+中序还原二叉树并求后序；
- 完全二叉树结点编号与父子关系；
- AVL 插入旋转过程；
- 哈夫曼树构造与 WPL、编码；
- 树转二叉树后的遍历关系；
- 并查集查找次数与路径压缩；
- 判断是否为 BST / AVL / 堆。