1.1 树#

连通且不含回路的无向图称为无向树，通常简称为树，记作 $T$。

判断一个图是否为树时，需要同时检查两个条件：

1. 图是连通的；
2. 图中不存在简单回路。

只有“无回路”还不够。例如，若一个无向图由两条互不相连的链组成，它没有回路，但它不是树，而是森林。

1.2 森林#

每个连通分支都是树的非连通无向图，称为森林。

可以将森林理解为“若干棵互不相连的树的集合”。

1.3 平凡树#

只含一个顶点的树称为平凡树。

1.4 树叶与分支点#

在无向树中：

• 度数为 $1$ 的顶点称为树叶；
• 度数大于等于 $2$ 的顶点称为分支点。

注意：这里讨论的是无向树。后面学习根树时，“树叶”的定义会改为“出度为 $0$ 的顶点”。

2.1 为什么“任意两点之间有唯一通路”等价于树？#

• 因为图连通，所以任意两点之间至少存在一条路径；
• 如果两点之间存在两条不同路径，则两条路径合起来会形成一个回路；
• 因此，在树中两点之间的路径只能有一条。

反过来，如果任意两点之间都有唯一的路径，那么图显然连通；同时，图中不可能存在回路，否则回路上的两个顶点之间会有两条不同路径。

2.2 为什么树一定有 $n-1$ 条边？#

一棵树从一个顶点开始，每增加一个新顶点，为保持连通且不形成回路，必须恰好增加一条边。因此，当顶点数为 $n$ 时，边数恰好为 $n-1$。

2.3 为什么树中的每条边都是桥？#

桥是删除后会使连通分支数增加的边。

树中任意两点之间的路径唯一。如果删除一条边，那么这条边两端之间原本唯一的路径被切断，图一定不再连通。因此，树中的每一条边都是桥。

2.4 两个常见误区#

• 只有 $m=n-1$，不能直接推出图是树。还需要补充“连通”或“无回路”。
• 只有“连通”，也不能推出图是树，因为图中可能存在回路。

定理#

设 $T$ 是一棵 $n$ 阶非平凡无向树，则 $T$ 中至少有两片树叶。

证明思路一：使用握手定理#

设树叶数量为 $x$。树中每个树叶的度数为 $1$，其余 $n-x$ 个顶点的度数至少为 $2$。

由握手定理和树的边数公式，有：

$\sum d(v_i)=2m=2(n-1)$。

另一方面：

$\sum d(v_i)\ge x+2(n-x)$。

因此：

$2(n-1)\ge x+2(n-x)$。

整理得到：

$x\ge 2$。

证明思路二：寻找最长路径#

在树中任选一条最长路径。它的两个端点一定都是树叶。

如果某个端点的度数大于 $1$，还可以从该端点继续向外延伸路径，这与“路径已经最长”矛盾。

例题#

某棵无向树中有：

• $2$ 个 $2$ 度顶点；
• $1$ 个 $3$ 度顶点；
• $3$ 个 $4$ 度顶点。

则树叶数为：

$t=2+(3-2)\times 1+(4-2)\times 3=9$。

1.1 生成树#

如果 $T$ 是 $G$ 的生成子图，并且 $T$ 本身是一棵树，则称 $T$ 是 $G$ 的一棵生成树。

“生成子图”表示：

• $T$ 保留 $G$ 的全部顶点；
• $T$ 只保留 $G$ 的一部分边。

因此，生成树的作用是：在保留所有顶点连通关系的前提下，尽可能删去多余边。

1.2 树枝#

属于生成树 $T$ 的边称为 $T$ 的树枝。

若 $G$ 有 $n$ 个顶点，则任意生成树一定有 $n-1$ 条树枝。

1.3 弦#

属于原图 $G$ 但不属于生成树 $T$ 的边称为 $T$ 的弦。

若 $G$ 有 $n$ 个顶点、$m$ 条边，则弦的数量为：

$m-(n-1)=m-n+1$。

1.4 余树#

由所有弦导出的子图称为生成树 $T$ 的余树，通常记作 $\overline{T}$。

注意：余树不一定连通，也不一定无回路。它的名字中虽然含有“树”，但它不一定真的是树。

定理#

无向图 $G$ 存在生成树，当且仅当 $G$ 是连通图。

证明与构造方法：破圈法#

若连通图 $G$ 中没有回路，则 $G$ 本身就是一棵生成树。

若 $G$ 中存在回路，则从任意一个回路中删除一条边。删除回路中的边不会破坏连通性，因为回路中仍有另一条路径连接这条边的两个端点。

不断重复“找到回路并删除其中一条边”的过程，直到图中不再存在回路。最终得到的连通无回路生成子图就是一棵生成树。

这套方法称为破圈法。

3.1 基本回路#

向生成树 $T$ 中加入一条弦 $e=(u,v)$，一定会产生唯一一个回路。这个回路称为弦 $e$ 对应的基本回路。

原因是：

• 在树 $T$ 中，$u$ 到 $v$ 原本存在唯一一条路径；
• 再加入弦 $e=(u,v)$ 后，这条弦与原路径合起来构成一个回路；
• 因为树中的路径唯一，所以产生的回路也唯一。

3.2 求基本回路的算法#

对于每一条弦 $e=(u,v)$：

1. 在生成树 $T$ 中找到 $u$ 到 $v$ 的唯一通路；
2. 将这条通路与弦 $e$ 合并；
3. 得到弦 $e$ 对应的基本回路。

3.3 基本回路系统#

若图 $G$ 有 $n$ 个顶点、$m$ 条边，则生成树中有 $n-1$ 条树枝，弦有 $m-n+1$ 条。

每条弦对应一个基本回路，因此基本回路系统中共有：

$m-n+1$

个基本回路。

4.1 基本割集#

设 $e$ 是生成树 $T$ 中的一条树枝。

删除 $e$ 后，树 $T$ 会分裂成两个连通分支，记为 $T_1$ 和 $T_2$。

在原图 $G$ 中，所有连接 $T_1$ 与 $T_2$ 的边构成的集合，称为树枝 $e$ 对应的基本割集。

4.2 求基本割集的算法#

对于每一条树枝 $e$：

1. 从生成树 $T$ 中删除 $e$；
2. 得到两个连通分支 $T_1$ 和 $T_2$；
3. 在原图 $G$ 中找出所有一个端点属于 $T_1$、另一个端点属于 $T_2$ 的边；
4. 这些边组成 $e$ 对应的基本割集。

4.3 基本割集系统#

一棵 $n$ 阶生成树有 $n-1$ 条树枝，每条树枝对应一个基本割集。因此，基本割集系统中共有：

$n-1$

个基本割集。

4.4 基本回路与基本割集的对照#

可以用一句话记忆：

弦加进去找圈，树枝删掉找割集。

5.1 定义#

设 $G=\langle V,E,W\rangle$ 是无向连通带权图，$T$ 是 $G$ 的一棵生成树。

生成树中所有边权之和称为 $T$ 的权，记作 $W(T)$。

在 $G$ 的所有生成树中，权值最小的生成树称为最小生成树，简称 MST。

5.2 Kruskal 算法：避圈法#

Kruskal 算法的核心思想是：

按照边权从小到大尝试加入边，但始终避免形成回路。

具体步骤：

1. 将所有边按照权值从小到大排序；
2. 从最小边开始依次检查；
3. 如果加入当前边不会形成回路，则保留该边；
4. 如果加入当前边会形成回路，则舍弃该边；
5. 当选中的边达到 $n-1$ 条时停止。

5.3 算法竞赛中的实现方式#

在程序中，通常使用并查集判断两个顶点是否已经连通：

• 如果当前边的两个端点已经属于同一个集合，则加入后会形成回路，应舍弃；
• 如果属于不同集合，则加入该边，并合并两个集合。

5.4 注意事项#

• 原图必须连通，才能得到最小生成树；
• 若原图不连通，Kruskal 算法得到的是最小生成森林；
• 若存在相同权值的边，最小生成树可能不唯一，但最小权值相同。

1.1 有向树#

如果一个有向图的基图是一棵无向树，则称该有向图为有向树。

1.2 根树#

有一个顶点入度为 $0$，其余顶点入度均为 $1$ 的非平凡有向树，称为根树。

其中：

• 入度为 $0$ 的顶点称为树根；
• 每个非根顶点都有唯一的父亲。

实际画根树时，通常把树根画在最上方，并省略边上的箭头。默认所有边均由上指向下。

1.3 根树中的常用术语#

树根的层数规定为 $0$。

3.1 有序树#

若规定同一层顶点之间的先后次序，则称为有序树。

3.2 $r$ 叉树#

若根树中每个分支点至多有 $r$ 个儿子，则称为 $r$ 叉树。

3.3 $r$ 叉正则树#

若每个分支点恰好有 $r$ 个儿子，则称为 $r$ 叉正则树。

3.4 $r$ 叉完全正则树#

若一棵 $r$ 叉正则树的所有树叶层数都相同，则称为 $r$ 叉完全正则树。

3.5 二叉树#

当 $r=2$ 时，得到二叉树。

对于二叉正则有序树，每个分支点的两个儿子有明确顺序，分别称为左儿子和右儿子；对应的根子树称为左子树和右子树。

5.1 带权路径长度#

设二叉树 $T$ 有 $t$ 片树叶 $v_1,v_2,\dots,v_t$，各树叶权值分别为 $w_1,w_2,\dots,w_t$。

树的权定义为：

$W(T)=\sum_{i=1}^{t} w_i l(v_i)$。

其中，$l(v_i)$ 表示树叶 $v_i$ 的层数。

在所有具有相同树叶权值的二叉树中，使 $W(T)$ 最小的二叉树称为最优二叉树，也称为 Huffman 树。

5.2 Huffman 算法#

给定权值 $w_1,w_2,\dots,w_t$：

1. 先建立 $t$ 个只有树叶的单点树；
2. 每次选择权值最小的两个根结点；
3. 新建一个分支点，将这两个结点作为儿子；
4. 新分支点的权值等于两个儿子权值之和；
5. 重复上述过程，直到只剩下一棵树。

最终得到 Huffman 树。

5.3 快速求树的总权#

Huffman 树的带权路径长度 $W(T)$ 等于所有新建分支点权值之和。

5.4 例题#

给定权值：

$1,1,2,3,4,5$。

一种合并过程为：

1. $1+1=2$；
2. $2+2=4$；
3. $3+4=7$；
4. $4+5=9$；
5. $7+9=16$。

因此：

$W(T)=2+4+7+9+16=38$。

5.5 注意事项#

当存在相同权值时，Huffman 树的具体形状可能不唯一，但最小总权 $W(T)$ 相同。

6.1 前缀#

设字符串 $\alpha=\alpha_1\alpha_2\cdots\alpha_n$。

其前缀是：

$\alpha_1\alpha_2\cdots\alpha_k$，其中 $1\le k<n$。

6.2 前缀码#

若一个编码集合中，任意一个码字都不是另一个码字的前缀，则称该编码集合为前缀码。

例如：

• $\{0,10,110,1111\}$ 是前缀码；
• $\{10,01,001,110\}$ 是前缀码；
• $\{0,10,010,1010\}$ 不是前缀码，因为 $0$ 是 $010$ 的前缀。

6.3 为什么二叉树可以产生前缀码？#

对二叉树中的每个分支点：

• 左边标记为 $0$；
• 右边标记为 $1$。

从树根走到每片树叶，将路径上的数字依次拼接起来，得到该树叶对应的编码。

由于任何一片树叶都不可能是另一片树叶的祖先，因此任何一个码字都不会成为另一个码字的前缀。

6.4 最佳前缀码#

若用字符出现频率作为树叶权值，并构造 Huffman 树，则由这棵 Huffman 树产生的前缀码所需二进制位数最少。

因此：

设计最佳前缀码，本质上就是构造最优二叉树。

6.5 课件中的八进制编码例子#

设八进制数字出现频率为：

使用 Huffman 算法后，传输 $100$ 个按上述比例出现的数字，需要 $285$ 个二进制位。

平均每个数字需要：

$285\div 100=2.85$

个二进制位。

若使用定长编码，因为共有 $8$ 个符号，每个符号需要 $3$ 个二进制位，因此 $100$ 个数字需要 $300$ 位。

Huffman 编码比定长编码节省了 $15$ 位。

7.1 三种周游方式#

7.2 递归理解#

假设一棵二叉树由“根、左子树、右子树”构成，则：

• 前序：先访问根，再递归访问左子树和右子树；
• 中序：先递归访问左子树，再访问根，再递归访问右子树；
• 后序：先递归访问左右子树，最后访问根。

8.1 表示规则#

使用二叉有序正则树表示算式时：

• 运算符放在分支点；
• 数字或变量放在树叶；
• 最高层次的运算放在树根；
• 对于减法和除法，被减数、被除数放在左子树中。

8.2 前缀表达式：波兰式#

按照前序周游访问表达式树，得到前缀表达式，也称波兰式。

例如：

$a+b$

写成前缀表达式为：

$+\ a\ b$

8.3 后缀表达式：逆波兰式#

按照后序周游访问表达式树，得到后缀表达式，也称逆波兰式。

例如：

$a+b$

写成后缀表达式为：

$a\ b\ +$

8.4 与程序设计的联系#

• 前缀表达式和后缀表达式都不需要额外括号；
• 后缀表达式可以使用栈直接求值；
• 编译器中的表达式分析、计算器实现、栈结构题目都可能使用逆波兰式。