学习目标
掌握定义、公式与定理条件；能使用原讲义中的真值表、矩阵、图表、分布和统计推断题完成练习。
第 8 章：树
无根树是连通且无回路的简单无向图。指定一个顶点为根，边按从根到叶的层次理解，得到根树；无子女的顶点是叶（叶节点），其他顶点是内部节点。
1. 本章复习目标
2. 知识框架
概念与性质
先厘清定义、条件和性质的联系。
公式与应用
再用题型模板、例题和练习完成方法迁移。
3. 核心知识点
原讲义内容
1. 树与根树
无根树是连通且无回路的简单无向图。指定一个顶点为根，边按从根到叶的层次理解，得到根树；无子女的顶点是叶（叶节点），其他顶点是内部节点。
对有 \(n\) 个顶点的图，以下命题等价：
① 它是树；② 连通且有 \(n-1\) 条边；③ 无回路且有 \(n-1\) 条边；④ 任意两点之间存在且仅存在一条简单路径。
① 它是树；② 连通且有 \(n-1\) 条边；③ 无回路且有 \(n-1\) 条边；④ 任意两点之间存在且仅存在一条简单路径。
为什么树有 \(n-1\) 条边？
从单个顶点开始有 \(0\) 条边。每次加入一个新顶点并保持连通且无回路，只能用一条边把它接到已有部分；加入 \(n-1\) 次后共有 \(n\) 个顶点和 \(n-1\) 条边。反过来，若连通图边多于 \(n-1\)，沿着边必会形成回路。
| 重要性质 | 使用方式 |
|---|---|
| 任意两点间路径唯一 ⭐⭐⭐ | 若有两条不同简单路径，合起来会产生回路；常用于证明与路径计数。 |
| 删去任一条边，树变为两个分支 ⭐⭐⭐ | 树中边都是桥；可用于割边、最小生成树的交换论证。 |
| 加入一条不在树中的边，恰产生一个回路 ⭐⭐⭐ | 是 Kruskal “不成环再选边”的结构依据。 |
| 至少有两个叶（\(n\ge2\)） ⭐⭐ | 可从最长简单路径的两端证明；端点若还能延伸，就与“最长”矛盾。 |
练习 5：证明：树中任意两点之间至多存在一条简单路径。
思路：用反证法，把“两条不同简单路径”转化为“存在回路”。
过程：假设顶点 \(u,v\) 间有两条不同的简单路径。从 \(u\) 沿两条路径走，在第一次分叉后又在某点相遇；这两段不同的路径首尾相同，合在一起构成回路。这与树无回路矛盾。
答案：\(\boxed{\text{树中两点间简单路径唯一}}\)。连通性同时保证“至少有一条”，故为“存在且仅存在一条”。
2. 生成树与最小生成树
连通图 \(G\) 的生成树是包含 \(G\) 全部顶点的树：在保持连通的前提下删去足够的边，直到只剩 \(n-1\) 条。加权连通图的最小生成树（MST）是在所有生成树中边权总和最小的一棵。
Prim 算法 ⭐⭐⭐
生长一棵树。任选起点，每步选一条连接“已选顶点集合”和“未选顶点集合”的最轻边，直到覆盖所有顶点。
适合从一个顶点逐步扩张；每一步都必须跨越当前割，不能只选全图最小边。
Kruskal 算法 ⭐⭐⭐
合并若干分量。把全图边按权从小到大扫描；若一条边连接两个不同分量，就选它；若会成回路，就跳过。
适合边少或已排序边表；结束时恰选 \(n-1\) 条边。
绿色粗边构成最小生成树：\(AB,BC,CD,DE\)，总权为 \(1+2+1+2=6\)。
练习 6：对上图从 \(A\) 运行 Prim，逐步写出所选边与总权。
思路：每一步只比较“已在树内”与“树外”之间的候选边。
过程：起点 \(A\)：选 \(AB(1)\)；候选 \(AC(4),BC(2),BD(5)\)，选 \(BC(2)\)；候选 \(BD(5),CD(1),CE(3)\)，选 \(CD(1)\)；候选 \(CE(3),DE(2)\)，选 \(DE(2)\)。已覆盖五个顶点。
答案：\(\boxed{\{AB,BC,CD,DE\}}\)，最小总权 \(\boxed{6}\)。
易错点：第三步不能在所有未选边中任选最小，而必须选连接当前树与外部的边。
练习 7：对上图用 Kruskal，为什么 \(CE(3)\) 不选？
思路：按权排序，并在每步判断端点是否已通过已选边连通。
过程：依次选 \(AB(1),CD(1),BC(2),DE(2)\)。此时已选 \(4=n-1\) 条边，所有顶点连通，算法结束。若提前考察 \(CE(3)\)，在 \(BC,CD,DE\) 已选后，\(C\) 与 \(E\) 已连通，加入它会构成回路 \(C-D-E-C\)。
答案：\(\boxed{CE(3)\text{ 不选，因为会成回路}}\)。
3. 二叉树与 Huffman 树（课程扩展）
二叉树、完全二叉树 ⭐⭐
二叉树中每个结点至多两个子女，区分左、右子树。满二叉树中每个内部结点恰有两个子女，此时叶数 \(n_0=n_2+1\)。完全二叉树的各层从上到下填满，仅最后一层可不满且从左到右连续。
Huffman 树 ⭐⭐
反复合并权值最小的两个结点，合并权为二者之和，直至只剩根。它给出带权路径长度最小的前缀编码树；频率高的符号倾向于离根更近。
练习 8：权值 \(5,7,10,15\) 构造 Huffman 树，求最小带权路径长度。
思路：每轮合并当前最小的两个权值；每次合并产生的新权重新参与比较。
过程：\(5+7=12\)，再 \(10+12=22\)，最后 \(15+22=37\)。对应深度为：\(15\) 的深度 \(1\)，\(10\) 的深度 \(2\)，\(5,7\) 的深度 \(3\)。
答案：\(\boxed{5\cdot3+7\cdot3+10\cdot2+15\cdot1=71}\)。
4. 常见题型
方法选择
原讲义中的判断方法、真值表、矩阵、图示、分布或统计计算流程均已完整保留在“核心知识点”区。
5. 典型例题
例题使用方式
先独立作答，再核对原讲义中的关键推导、公式条件与答案。
6. 练习题
练习与解析
原有折叠练习、完整解析与易错提示均保留在“核心知识点”区。
7. 易错点
8. 公式速查
| 复习顺序 | 使用要求 | 检查项 |
|---|---|---|
| 定义与定理 | 确认适用条件 | 对象、范围、已知条件 |
| 公式与计算 | 代入前保持符号一致 | 量词、集合符号、矩阵维数或概率参数 |
| 结论 | 说明结论范围 | 结果、逻辑方向与单位 |
9. 本章总结
必须记忆
核心定义、公式和定理条件。
必须理解
概念间的区别与方法选择依据。
必须会做
原讲义中的例题、练习与综合题型。
容易丢分
忽略前提、符号不严谨、混淆相近概念或跳过关键步骤。