大纲对照
- 一树的基本概念→ 01
二叉排序树、平衡二叉树、红黑树、B 树在大纲里属于“查找”一章,见 DS·7 查找。
后序线索树找后继的细节 · 三叉链表 · 并查集的反阿克曼复杂度证明。
树的基本概念与性质
验证性质 1:Σ度 = 3 + 2 + 3 = 8,n = 8 + 1 = 9。
一棵树中度为 4 的结点 20 个、度为 3 的 10 个、度为 2 的 1 个、度为 1 的 10 个,叶子有几个?
这类题永远只用两个等式:n = Σ 度 + 1,n = n0 + n1 + … + nm。
- “度为 3 的树”至少有一个结点度为 3;“3 叉树”只是规定每个结点最多 3 个孩子,可以一个度为 3 的都没有,甚至可以为空。
- 高度/深度的层数默认从 1 开始数(根在第 1 层),个别题目从 0 开始,先看题。
二叉树:主要特征与存储结构
一、必背性质
中图:⌊10/2⌋ = 5,所以 6~10 都是叶子(绿色);n = 10 为偶数,恰有 1 个度为 1 的结点(橙色的 5)。右图缺了 6 号位置(虚线)却有 7 号,编号不连续。
完全二叉树有 768 个结点,叶子有几个?
完全二叉树第 6 层有 8 个叶子,该树最多有多少个结点?
二、存储结构
| 方式 | 做法 | 适合 |
|---|---|---|
| 顺序存储 | 按完全二叉树编号放进数组,下标 i 的孩子在 2i、2i+1;空位要留着 | 完全二叉树、堆;一般树会浪费大量空间(最坏高 h 的单支树要 2h − 1 个单元) |
| 二叉链表 | lchild | data | rchild | 一般二叉树;n 个结点有 n + 1 个空指针 |
三叉链表
再加一个 parent 指针,便于向上找父亲(例如后序线索树找后继)。大纲只要求顺序存储和二叉链表。
二叉树的遍历
小技巧:把图中结点垂直“压扁”到一条水平线上,从左往右读出来的恰好是中序序列 D B E A F C。
由遍历序列还原二叉树
先序 A B D E C F,中序 D B E A F C,求后序。
D B E 是左子树,右边 F C 是右子树。左子树:先序
B D E → 根 B,中序 D | B | E → D 左、E 右。右子树:先序 C F → 根 C,中序 F C → F 是 C 的左孩子。后序:D E B F C A。
几个常考结论
- 先序和中序相同 → 所有结点没有左孩子(右单支);中序和后序相同 → 没有右孩子;先序和后序相反 → 树高等于结点数(每层一个结点)。
- n 个结点能构成的不同二叉树个数 = 卡特兰数 C(2n, n) / (n + 1);也是“给定先序序列,可能的二叉树个数”。n = 3 时为 5。
- 非递归遍历用栈:后序非递归时,栈中保存的恰是当前结点的所有祖先(用于求根到某结点的路径、最近公共祖先)。
线索二叉树
叶子 E 的左线索指向前驱 B、右线索指向后继 A;D 是第一个结点没有前驱,C 是最后一个没有后继,线索为 NULL。
- 构造:按选定的遍历次序遍历一次,用一个 pre 指针记住“上一个访问的结点”。访问 p 时:p 左空 → p.lchild = pre;pre 右空 → pre.rchild = p。
- 中序线索树找后继:rtag = 1 → 直接是 rchild;否则 → 右子树里最左下的结点。找前驱对称(左子树最右下)。
- 先序线索树找后继容易(有左孩子就是左孩子,否则是右指针所指);找前驱需要父指针。
中序 D B E A F C 的二叉树中序线索化后,E 的左、右线索分别指向谁?
- 线索化之后仍然是二叉链表结构,属于物理结构(存储结构)层面的概念。
- 后序线索树找后继仍然可能需要栈或父指针,不是所有情况都能靠线索解决。
后序线索树找后继的分类讨论
结点是根 → 无后继;是父亲的右孩子,或是左孩子且父亲无右子树 → 后继是父亲;是左孩子且父亲有右子树 → 后继是父亲右子树中后序第一个结点。需要三叉链表,考试只要求知道“后序线索树找后继不方便”。
树、森林的存储、转换与遍历
一、树的三种存储
| 方式 | 做法 | 找父亲 | 找孩子 |
|---|---|---|---|
| 双亲表示法 | 数组,每个结点记 parent 下标(根为 −1) | 快 | 要遍历整个数组 |
| 孩子表示法 | 每个结点挂一条孩子链表 | 要遍历 | 快 |
| 孩子兄弟表示法 | 二叉链表:firstchild | data | nextsibling | 麻烦 | 较快;可直接转成二叉树 |
二、树 / 森林 ⇄ 二叉树:“左孩子,右兄弟”
对照遍历:森林先序 A B C D E F G H = 二叉树先序;森林中序 B C A E D G H F = 二叉树中序。
三、遍历的对应关系(必背表)
| 树 | 森林 | 对应的二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历(有的书叫后序) | 中序遍历 |
- 树的后根遍历对应二叉树的中序,不是后序——最常见的陷阱。
- 树没有“中根遍历”(孩子数不定,不知道根放在第几个孩子中间)。
四、常考计数
- 森林有 n 个结点、m 条边 → 有 n − m 棵树。
- 森林中叶子数 = 对应二叉树中左指针为空的结点数(没有第一个孩子的就是叶子)。
- 树中非终端结点数为 k → 对应二叉树中右指针为空的结点数为 k + 1(每个结点的最后一个孩子右指针为空,再加上根)。
哈夫曼树与哈夫曼编码
权值 {2, 3, 4, 7, 8},求哈夫曼树的 WPL。
WPL = 5 + 9 + 15 + 24 = 53。验证:2、3 深度 3,4、7、8 深度 2 → 15 + 8 + 14 + 16 = 53。
哈夫曼编码
- 左分支记 0、右分支记 1,从根到叶子的 0/1 串就是该字符的编码。
- 它是前缀编码:任何一个编码都不是另一个编码的前缀 → 解码不会有歧义。判断一组编码是否为前缀码:把它们画成二叉树,看是否所有编码都落在叶子上。
- 与定长编码比:总码长 = WPL(权值为出现次数时)。
并查集及其应用
两个优化
- 小树并入大树(按大小/秩合并):根存 −(结点数),合并时让小的挂到大的下面 → 树高 ≤ ⌊log2n⌋ + 1,Find 为 O(log n)。
- 路径压缩:Find 时把沿途所有结点直接挂到根上。两者结合后单次操作几乎是常数。
应用
- 判断图的连通分量个数:每条边 Union 两端点,最后数根的个数。
- Kruskal 算法判断加边是否成环:两端点 Find 结果相同 → 成环,舍弃。
- 判断无向图是否有环、等价类划分。
复杂度 O(α(n))
同时使用按秩合并和路径压缩,m 次操作总时间 O(m·α(n)),α 是反阿克曼函数,实际中不超过 4。证明不要求。
堆及其应用
三个操作
| 操作 | 做法 | 时间 |
|---|---|---|
| 建堆 | 从最后一个非叶结点 ⌊n/2⌋ 开始,到 1 为止,依次做下沉(和较大的孩子比,小于它就交换,继续往下) | O(n) |
| 插入 | 放到末尾,上浮(比父亲大就交换) | O(log n) |
| 删除堆顶 | 用最后一个元素替换堆顶,再下沉 | O(log n) |
把 53 17 78 09 45 65 87 32 建成大根堆。
i=4(09)与孩子 32 交换;i=3(78)与较大孩子 87 交换;i=2(17)与较大孩子 45 交换;i=1(53)与 87 交换,下沉到位置 3 后再与 78 交换。
结果:87 45 78 32 17 65 53 09。
- 下沉时和两个孩子中较大的比(大根堆),比较次数每层最多 2 次。
- 建堆是 O(n) 不是 O(n log n);堆排序整体才是 O(n log n)。
- 在大根堆中,最小元素一定在叶子上,但不确定是哪个叶子。
应用
- 优先队列:每次取最大(最小)元素,如进程按优先级调度、Dijkstra 中取最近顶点。
- 堆排序:见 DS·8 排序。
- Top-K:从 n 个数中找最小的 k 个 → 维护一个大小为 k 的大根堆,新元素比堆顶小就替换堆顶并下沉,时间 O(n log k)。
- 多路归并:k 个有序表合并时用小根堆每次挑最小者。
自测与考前速览
1. 二叉树有 50 个叶子、30 个度为 1 的结点,共多少结点?
n2 = n0 − 1 = 49,n = 50 + 30 + 49 = 129。
2. 哪两种遍历序列组合不能唯一确定二叉树?
先序 + 后序(以及任何不含中序的组合)。
3. 树的后根遍历序列等于对应二叉树的哪种遍历?
中序遍历。
4. 有 n 个叶子的哈夫曼树共有多少结点?
2n − 1。
5. 编码 {0, 10, 110, 111} 和 {0, 01, 11} 哪个是前缀码?
第一组是;第二组中 0 是 01 的前缀,不是。
6. 往大根堆 [87 45 78 32 17 65 53 09] 插入 80,结果?
80 放在位置 9,父亲 32 → 交换;位置 4 的父亲 45 → 交换;位置 2 的父亲 87 → 停。结果:87 80 78 45 17 65 53 09 32。
7. 用并查集求无向图连通分量个数,思路?
初始每个顶点一个集合;对每条边 (u, v),若 Find(u) ≠ Find(v) 则 Union;最后根的个数(S[i] < 0 的个数)就是连通分量数。
n = Σ度 + 1,二叉树 n0 = n2 + 1。
还原二叉树必须有中序。
左孩子右兄弟;树的后根 = 二叉树中序。
哈夫曼 WPL = 所有合并和之和。
建堆从 ⌊n/2⌋ 倒着下沉,O(n)。
① 度为 3 的树 ≠ 3 叉树。
② 完全二叉树 n 为偶数时 n1 = 1。
③ 二叉链表空指针 n + 1 个。
④ 哈夫曼树不唯一,WPL 唯一。
⑤ 堆中兄弟无序,不是 BST。