考频地图
树是数据结构的重中之重:选择题 3–4 道(性质计算、遍历、线索树、树与森林转换、哈夫曼),算法题也常出在二叉树上(2014 WPL、2017 表达式树、2022 判断二叉排序树)。
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 树的性质(结点数、度数) | ★★★★☆ | “度为 4 的树中……叶结点个数是” |
| 二叉树性质、完全二叉树 | ★★★★★ | “768 个结点的完全二叉树叶子数” |
| 遍历与还原 | ★★★★★ | “先序与中序相同的二叉树”“由序列还原” |
| 线索二叉树 | ★★★☆☆ | “某结点的后继线索指向” |
| 树、森林与二叉树转换 | ★★★★☆ | “森林 F 的叶结点数等于 T 中……的结点数” |
| 哈夫曼树与编码 | ★★★★☆ | “WPL”“前缀编码” |
| 并查集 | ★★★☆☆ | “合并与查找后的数组” |
树的基本概念与性质
结点的度 = 孩子个数;树的度 = 结点度的最大值;度为 0 的是叶结点。结点的深度从根往下数,高度从叶往上数;树的高度(深度)= 最大层数。
二叉树的性质与存储
存储结构
顺序存储:按完全二叉树编号放进数组,适合完全二叉树(一般二叉树会浪费大量空位,最坏高 h 的单支树要 2ʰ − 1 个单元)。二叉链表:每个结点 lchild、data、rchild;n 个结点共 2n 个指针,其中只有 n − 1 个指向孩子,空指针 n + 1 个。
- n₀ = n₂ + 1 对任意二叉树成立,与 n₁ 无关。
- “完全二叉树”≠“满二叉树”;满二叉树一定是完全二叉树。
- 具有 n 个结点的不同形态二叉树有 C(2n, n)/(n + 1) 种(卡特兰数)。
遍历与还原
void PreOrder(BiTree T) { if (T) { visit(T); // 先序:根在前 PreOrder(T->lchild); PreOrder(T->rchild); } } // 中序:visit 放中间;后序:放最后
InitQueue(Q); EnQueue(Q, T); while (!IsEmpty(Q)) { DeQueue(Q, p); visit(p); if (p->lchild) EnQueue(Q, p->lchild); if (p->rchild) EnQueue(Q, p->rchild); }
三种递归遍历时间都是 O(n),空间是递归栈深度 O(h)。非递归遍历用栈模拟:中序“一路向左压栈,弹出访问再转向右子树”;后序需要记录“右子树是否已访问”。
由遍历序列还原二叉树
先序 + 中序、后序 + 中序、层序 + 中序都能唯一确定一棵二叉树;先序 + 后序不能(无法区分只有一个孩子时是左还是右)。
形态判断题:“先序序列与中序序列相同的二叉树”→ 根-左-右 = 左-根-右,说明每个结点都没有左子树(只有右单支)。“先序与后序相反”→ 每层只有一个结点(高度 = 结点数)。“前序和后序相同”→ 只有根结点。
线索二叉树
结点结构:lchild | ltag | data | rtag | rchild;tag = 0 表示指向孩子,tag = 1 表示线索。在中序线索树中找后继:若 rtag = 1 直接取;否则后继是右子树最左下的结点。后序线索树找后继仍可能需要知道双亲(要用三叉链表或栈),所以后序线索化后遍历仍不方便。
树、森林与二叉树
树的三种存储:双亲表示法(数组,每个结点记双亲下标,找双亲 O(1)、找孩子要遍历)、孩子表示法(每个结点的孩子串成链表)、孩子兄弟表示法(二叉链表:左指针指第一个孩子,右指针指下一个兄弟)——这就是树与二叉树相互转换的依据。
| 树 | 森林 | 对应二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历(有的教材称后序) | 中序遍历 |
- 树转二叉树后,二叉树根结点没有右孩子;森林转二叉树后根结点可以有右孩子。
- 森林 F 中叶结点个数 = 对应二叉树中左指针为空的结点个数(没有第一个孩子 ⇔ 叶子)。
- 森林的二叉树中,根的右链上结点数 = 森林中树的棵数。
哈夫曼树与编码
带权路径长度 WPL = Σ(叶子权值 × 叶子到根的路径长度)。WPL 最小的二叉树叫哈夫曼树(最优二叉树)。构造:每次选两棵根权值最小的树合并,直到只剩一棵。
- 哈夫曼树中没有度为 1 的结点;n 个叶子共 2n − 1 个结点。权值越大离根越近。
- 哈夫曼树不唯一(左右可交换、权值相同时选择不同),但 WPL 唯一且最小。
- 前缀编码:没有一个编码是另一个编码的前缀,解码不会有歧义。哈夫曼编码是前缀编码,且平均码长最短。判断“是否前缀编码”的方法:把编码画成二叉树,所有编码都应在叶子上。
- k 叉哈夫曼树:若 (n − 1) % (k − 1) ≠ 0,先补 k − 1 − (n − 1) % (k − 1) 个权为 0 的虚结点(用于最佳归并树,第 8 章)。
并查集
并查集用双亲表示法的数组存储一组不相交集合:parent[i] 是 i 的双亲,根结点存负数(其绝对值为集合大小)。两个操作:Find(x) 找 x 所在树的根;Union(a, b) 把一个根挂到另一个根下。
int Find(int S[], int x) { int root = x; while (S[root] >= 0) root = S[root]; // 找根 while (x != root) { int t = S[x]; S[x] = root; x = t; } // 路径压缩 return root; } void Union(int S[], int r1, int r2) { // r1、r2 是根 if (S[r2] > S[r1]) { S[r1] += S[r2]; S[r2] = r1; } // r2 更小,挂到 r1 下 else { S[r2] += S[r1]; S[r1] = r2; } }
不优化时 Find 最坏 O(n);按大小合并后树高 ≤ ⌊log₂n⌋ + 1,Find 为 O(log n);再加路径压缩,均摊接近 O(1)(O(α(n)))。并查集用于 Kruskal 判环、判断图的连通分量。
真题与自测
一、真题问法
问法 1:“若一棵完全二叉树有 768 个结点,则叶结点个数是?”→ 384。
问法 2:“将森林 F 转换为对应的二叉树 T,F 中叶结点的个数等于?”→ T 中左孩子指针为空的结点个数。
问法 3(2014 算法题):“求二叉树的 WPL(叶结点 weight 已知)”→ 先序或层序遍历,记录深度,遇到叶子累加 weight × depth。
问法 4(2017 算法题):“把表达式树转换为带括号的中缀表达式”→ 中序遍历,非叶子且非根结点时在左右两边加括号。
二、折叠自测
1. 二叉树有 10 个度为 2 的结点、5 个度为 1 的结点,叶结点几个?
n₀ = n₂ + 1 = 11。
2. 完全二叉树有 1001 个结点,叶子几个?
⌈1001/2⌉ = 501(n 为奇数,没有度为 1 的结点)。
3. n 个结点的二叉链表中有几个空指针?
n + 1 个。
4. 先序为 ABDECF、中序为 DBEAFC,后序是?
DEBFCA。
5. 权值 7、5、2、4 的哈夫曼树 WPL?
35(2 和 4 合并为 6,5 和 6 合并为 11,7 和 11 合并为 18;6 + 11 + 18 = 35)。
6. 哪两种遍历序列组合不能唯一确定二叉树?
先序 + 后序。
三、考前速览
n = 度数和 + 1。
n₀ = n₂ + 1。
完全二叉树叶子 = ⌈n/2⌉。
树先根 = 二叉树先序,后根 = 中序。
① 先序 + 后序不能确定二叉树。
② 哈夫曼树没有度为 1 的结点。
③ 后序线索树找后继仍需双亲信息。