树

一、树的基本概念

1.1 无向树的定义

定义：一个连通的并且没有回路的无向图称为一棵无向树，简称树。

两个要点：

• 连通：任意两个顶点之间都有通路
• 无回路：图中不存在回路

1.2 树的等价定义

以下任意一条都可以作为无向树的定义：

1. 无回路的连通图
2. 无回路且边数比点数少1（$m = n - 1$）
3. 连通且边数比点数少1（$m = n - 1$）
4. 无回路且若增加一条边，得到唯一回路
5. 连通但删去一条边之后不连通
6. 任意一对结点之间只有唯一的一条路

证明思路：证明以上六个命题彼此等价。

1.3 树的基本术语

思考：树是森林吗？是（树是连通的森林）。平凡图是森林吗？是（平凡图无回路）。

二、有向树与根树

2.1 有向树

有向树：如果一个有向图在不考虑边的方向时是一棵无向树，则称为有向树。

2.2 根树

定义：有向树有且只有一个入度为0的结点，其余所有结点的入度为1，称为根树。

根结点：入度为0的结点（唯一的）。

叶结点（叶子）：出度为0的结点。

分支点（内结点）：出度不为0的结点。

结点的层次：从根结点到该结点的单向通路的长度。树结构也称为层次结构。

2.3 根树的实例

• 磁盘文件目录结构
• 族谱
• 管理架构

2.4 m叉树与二叉树

m叉树：每个结点的出度小于或等于 $m$ 的根树。

二叉树：每个结点的出度小于或等于2的根树（即 $m = 2$ 的m叉树）。

三、二叉树的遍历

3.1 遍历的概念

目的：把非线性结构转化为线性结构。

3.2 三种遍历方法

3.3 遍历示例

对于一棵二叉树，三种遍历序列为：

• 先序遍历：ABDGEFH
• 中序遍历：BDGAECFH
• 后序遍历：GDBEHFCA

3.4 由遍历结果重建二叉树

方法（利用先序和中序）：

1. 前序序列的第一个结点是根结点
2. 在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列（左、右子树）
3. 将前序序列去掉根结点后的序列划分为左、右两个序列，分别是左、右子树的前序序列
4. 对左、右子树递归地实施同样方法，直到所得左、右子树为空

示例：前序序列为 ABDHGCEFI，中序序列为 HDGBAECIF，可唯一画出二叉树。

3.5 遍历序列的唯一性

反例：先序都是 AB，后序都是 BA，但可以构造出结构不同的两棵树。

四、树的性质

4.1 基本性质

定理：设树 $T$ 有 $n$ 个顶点、$m$ 条边，则：

$n = m + 1$

即顶点数 = 边数 + 1。

证明思路：

• 2个顶点连起来需要1条边
• 3个顶点连起来需要2条边
• 以此类推，$n$ 个顶点需要 $n-1$ 条边

4.2 树的应用示例

例题：无向树 $T$ 有两个2度顶点、两个3度顶点、一个4度顶点，其余顶点均为树叶。求 $T$ 的阶数 $n$、边数 $m$、树叶数 $t$。

解：

• 由握手定理：$\sum d(v_i) = 2m$
• 树的性质：$m = n - 1$
• 设树叶有 $t$ 个，度数为1
• 总度数：$2 \times 2 + 3 \times 2 + 4 \times 1 + 1 \times t = 4 + 6 + 4 + t = 14 + t$
• 顶点数：$n = 2 + 2 + 1 + t = 5 + t$
• 边数：$m = n - 1 = 4 + t$
• 由握手定理：$2m = 14 + t$，即 $2(4 + t) = 14 + t$
• 解得：$t = 6$

结果：

• $n = 5 + 6 = 11$（11个顶点）
• $m = 11 - 1 = 10$（10条边）
• $t = 6$（6片树叶）

五、生成树

5.1 生成树的定义

定义：如果图 $G$ 的生成子图是一棵树，则称该树为 $G$ 的生成树。

性质：

• 生成树包含 $G$ 的所有顶点
• 生成树是连通的且无回路
• $n$ 个顶点的生成树有 $n-1$ 条边

思考：生成树是唯一的吗？不一定，一个连通图可能有多个不同的生成树。

5.2 树的相关定理

定理1：任意一棵非平凡树至少有两片树叶。

定理2：连通图至少有一棵生成树（用破圈法证明）。

定理3：一条回路和任何一棵生成树关于原图的补至少有一条公共边。

定理4：一个边割集和任何一棵生成树至少有一条公共边。

5.3 最小生成树

定义：图中的每条边给定了权，则所有生成树中每条边权值之和最小的生成树，称为最小生成树。

思考：最小生成树是唯一的吗？不一定，当有多条边权值相同时，可能有多个最小生成树（但权值之和相同）。

5.4 求最小生成树的方法

方法一：避圈法（Kruskal算法）

算法思想：尽可能选取权值小的边，但不能构成回路。

步骤：

1. 将图的所有边按权值递增顺序排列
2. 置树 $T$ 为空集
3. 从边集中选取权值最小的边 $e$，并从边集中删去边 $e$
4. 若边 $e$ 加入树 $T$ 后不产生回路，则把边 $e$ 并入树 $T$
5. 重复步骤3-4，直到树 $T$ 包含 $n - 1$ 条边

示例：求图 $G$ 的最小生成树

• 顶点：A, B, C, D, E
• 边按权排序：5, 5, 8, 8, 9, 9, 10, 11
• 加入AB（权5）
• 加入AE（权5）
• 跳过BC（权8，会形成圈ABCA）
• 加入EB（权8）
• 加入BC（权9）
• 已有4条边（5个顶点），停止

最小生成树的权：$5 + 5 + 8 + 9 = 27$

方法二：破圈法（删边法）

步骤：

1. 在原图 $G$ 中随意找一个圈
2. 删除该圈中权最大的边
3. 重复上述步骤，直到图中无圈
4. 剩下的图就是最小生成树

示例：

• 找到圈ACBA，删除权最大的边（权11）
• 找到圈ABE，删除权最大的边（权10）
• 找到圈AEDA，删除权最大的边（权9）
• 找到圈ECDE，删除权最大的边（权10）
• 找到圈BDCB，删除权最大的边（权11）
• 找到圈ABCDEA，删除权最大的边（权9）
• 剩下4条边，形成最小生成树

最小生成树的权：$27$（结果唯一）

六、最优二元树

6.1 基本概念

二元树：每个结点的出度小于或等于2的根树（即二叉树）。在离散数学中，"二元树"与"二叉树"含义相同。

最优二元树：每个节点的权乘以它的层数之和最小的二元树。

带权路径长度：$W(T) = \sum_{i=1}^{t} w_i \times l_i$

其中 $w_i$ 是第 $i$ 个树叶的权，$l_i$ 是该树叶的层数。

6.2 Huffman算法

步骤：

1. 将权按由小到大排序
2. 选权最小的两个节点，生成一个分支节点（内点），权为两者之和
3. 将原来的两个节点删除，加入新生成的节点
4. 重复步骤2-3，直到只剩一个节点

示例：求权为3, 4, 5, 8, 9的最优二元树

1. 排序：3, 4, 5, 8, 9
2. 选3和4，生成权7的内点 → 剩下：5, 7, 8, 9
3. 选5和7，生成权12的内点 → 剩下：8, 9, 12
4. 选8和9，生成权17的内点 → 剩下：12, 17
5. 选12和17，生成权29的根节点

最优二元树的权：$W(T) = 3 \times 3 + 4 \times 3 + 5 \times 2 + 8 \times 2 + 9 \times 1 = 9 + 12 + 10 + 16 + 9 = 56$

6.3 最佳前缀码

应用：在信号传输中，用最优二元树设计最佳前缀码，使得高频字符用短码，低频字符用长码，从而最小化传输总长度。

例题：已知字母A-H出现的频率分别为30%, 15%, 15%, 10%, 10%, 9%, 6%, 5%，设计最佳前缀码。

解：

1. 将频率作为权，排序：5, 6, 9, 10, 10, 15, 15, 30
2. 用Huffman算法构建最优二元树
3. 对每个分支节点的左分支标0，右分支标1
4. 从根到树叶读取编码

最佳前缀码：

注意：最佳前缀码不唯一（同层叶子可交换），但最优二元树的权唯一。

七、最小生成树的实际应用

通讯线路敷设问题：要把 $n$ 个城市连成一个通讯网络，需敷设至少 $n - 1$ 条线路。任意两个城市间可敷设一条线路，最多可敷设 $n(n-1)/2$ 条线路，各条线路的造价可能不同。问题是如何选择 $n - 1$ 条线路，使该网络的造价最小，这就是最小生成树问题。

练习题

练习1：二叉树遍历

题目：对下面的二叉树，写出先序、中序、后序遍历序列。

1
2
3
4
5
6
7

    A
   / \
  B   C
 / \   \
D   E   F
   / \
  G   H

解：

• 先序遍历（根→左→右）：A B D E G H C F
• 中序遍历（左→根→右）：D B G E H A C F
• 后序遍历（左→右→根）：D G H E B F C A

练习2：由遍历结果重建二叉树

题目：已知前序序列为 ABDHGCEFI，中序序列为 HDGBAECIF，画出二叉树。

解：

1. 前序第一个结点 A 是根结点
2. 在中序中找到 A，左边 HDGB 是左子树，右边 ECIF 是右子树
3. 前序中去掉 A 后：BDHG C EFI，前4个是左子树的前序，后3个是右子树的前序
4. 递归处理左子树：前序 BDHG，中序 HDGB → B 是根，左 HD，右 G
5. 递归处理右子树：前序 EFI，中序 CIF → E 是根，左 C，右 IF → I 是根，左 F

1
2
3
4
5
6
7
8
9

    A
   / \
  B   E
 /   / \
D   C   I
 \     /
  G   F
 /
H

练习3：Kruskal 算法

题目：用 Kruskal 算法求下图的最小生成树。边按权排序：AB(5), AE(5), BE(8), BC(9), AD(10), BD(11), CD(11)。

解：

1. 选 AB（权5），不形成回路 ✓，加入
2. 选 AE（权5），不形成回路 ✓，加入
3. 选 BE（权8），不形成回路 ✓，加入
4. 选 BC（权9），不形成回路 ✓，加入
5. 已有4条边（5个顶点），停止

最小生成树的权：$5 + 5 + 8 + 9 = 27$

练习4：树的性质应用

题目：无向树 $T$ 有两个2度顶点、两个3度顶点、一个4度顶点，其余顶点均为树叶。求 $T$ 的阶数 $n$、边数 $m$、树叶数 $t$。

解：

设树叶有 $t$ 个（度数为1），则：

• 顶点数：$n = 2 + 2 + 1 + t = 5 + t$
• 边数：$m = n - 1 = 4 + t$
• 由握手定理：$\sum d(v_i) = 2m$

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

$14 + t = 8 + 2t$，解得 $t = 6$。

结果：$n = 11$，$m = 10$，$t = 6$（6片树叶）。

本节小结

• 无向树：连通且无回路的无向图，$n = m + 1$
• 树的六种等价定义：连通无回路 / $m = n - 1$ / 增边得唯一回路 / 删边不连通 / 唯一路
• 树叶：度数为1的顶点；分支点：度数大于1的顶点
• 森林：无回路的无向图
• 有向树：不考虑方向时是无向树的有向图
• 根树：有且只有一个入度为0的结点（根结点），其余入度为1
• m叉树：每个结点出度 $\leq m$；二叉树：出度 $\leq 2$
• 二叉树遍历：先序（根左右）、中序（左根右）、后序（左右根）
• 遍历唯一性：先序+中序或中序+后序可唯一确定二叉树；先序+后序不能
• 生成树：包含所有顶点的树，连通图至少有一棵
• 最小生成树：权最小的生成树，用避圈法（Kruskal）或破圈法求解
• 最优二元树：权×层数之和最小的二元树，用Huffman算法
• 最佳前缀码：用最优二元树设计的编码

关键术语速查