第 五 章 图 论 5.3 树 1. 无向树 2. 有向树 3. 周游算法 4. 前缀码与最优树.

Presentation on theme: "第 五 章 图 论 5.3 树 1. 无向树 2. 有向树 3. 周游算法 4. 前缀码与最优树."— Presentation transcript:

1 第 五 章 图 论 5.3 树 1. 无向树 2. 有向树 3. 周游算法 4. 前缀码与最优树

2 无向树 树的定义（6个等价定义） 树的性质 生成树的定义 求最小生成树的算法

3 树的基本概念 由英国数学家亚瑟·凯来（Arthur Cay ley， ）在试图列举形为CnH2n+2的化合物的同分异构体时发现了树图。 树具有广泛的应用，特别是在计算机科学和管理科学中。如： 用树构造存储和传输数据的有效编码 用树模拟决策过程

4 无向树的定义 [定义]（无向）树 一个连通且无回路的无向图称为无向树，或简称为树。
树中度数为1 的结点称为树叶，度数大于1的结点称为内结点或分枝点。 每个连通分支都是无向树的图称为森林。

5 无向树的等价定义 给定无向图T=(V,E)，以下语句是等价的： （1）T是无向树； （2）T是无回路，并且|E| = |V| - 1的图；
证明方法： （1）  （2）  （3）  （4）  （5）  （6） ； （6）  （1）

6 无向树的等价定义（证明1） 证：（1） （2） 即：T是无向树  T是无回路并且|E| = |V| -1的图
证明：从顶点数考虑，作归纳证明。 ① 当|V| = 2时，由T是无回路的连通图可知：T中边数|E| = 1，∴ |E| = |V| -1成立 ② 假设当|V| = k - 1时命题成立。 ③ 则当v = k时，∵图T连通且无回路，故至少有一条边的一个端点u的度数为1。 u

7 无向树的等价定义（证明1）续1 eu 证：（1） （2） 即：T是无向树  T是无回路并且|E| = |V| -1的图
证明(续)：续③. 设与u相关联的边为eu，在T中删去顶点u (u的度为1)及eu，得k-1个顶点的连通且无回路的图T=<V’, E’>。 由归纳假设，图T的边数: /* ② 中假设“当|V| = k-1时命题成立”*/ |E| = |V| -1 =（k-1）- 1 = k-2。 于是原图T的边数为 |E| = |E| + 1 =（k-2）+ 1 = k-1 ， 结点数 : |V| = |V| + 1 =（k-1）+ 1 = k ∴ |E| = |V| -1成立。 eu T T’

8 无向树的等价定义（证明2） 证：（2） （3） 即：T是无回路，并且|E| = |V| -1的图  T是连通且|E| = |V| -1的图 证：反证法. 设T(V, E)不连通，有k个连通分支T1 ... Tk (k≥2)，顶点数为|V1| ... |Vk|, 边数为|E1|...|Ek|。而每个连通分支是无回路连通图，则由(1) (2)得: |Ei| = |Vi| - 1。 而: |V| = |V1| + |V2| + …+ |Vk|, |E| = |E1| + |E2| + …+ |Ek| = (|V1| -1) + (|V2| -1) + …+ (|Vk| -1) = |V| - k（k≥2） 但这与前提|E| = |V| -1相矛盾。 故T是连通且|E| = |V| -1的图

9 树的等价定义（证明3） 证：（3）（4） 即：T是连通且|E| = |V| -1的图  T是无回路，但增加任一新边，得到一个且仅有一个回路的图。 证明： (归纳法) 。 ① 当|V| = 2时，|E| = |V| -1 = 1，故T必无回路。如增加一边，得到一个且仅得到一个回路。 ② 假设当v = k-1时命题成立。

10 树的等价定义（证明3）续1 证：（3）（4） 即：T是连通且|E| = |V| -1的图  T是无回路，但增加任一新边，得到一个且仅有一个回路的图。 证明（续）： ③当|V| = k时 因T是连通且|E| = |V| -1。故每个结点u有d(u)1。 断言1：至少有一个结点u0满足：d(u0)= 1。 如果断言不成立，则所有的结点u都有d(u)2。 则2|E| 2|V| ，即|E|  |V| 。与前提|E| = |V| -1矛盾。

11 无向树的等价定义（证明3）续2 证：定义（3） 定义（4）
即：T是连通且|E| = |V| -1的图  T是无回路，但增加任一新边，得到一个且仅有一个回路的图。 证明（续）： ④ 删去d(u0)=1 的结点u0及其关联边，得到新图T。 由归纳假设知T无回路。在T中加入u0及其关联边又得到T，显然T是无回路的。 若在连通图T中增加新边（ui， uj），则该边与T中ui到 uj的一条路构成一条回路。 断言2：该回路必是唯一的。若断言2不成立，若删去此新边，T中必有回路，得出矛盾。 T T’

12 无向树的等价定义（证明4） 证：（4）（5） 即：T是无回路，但增加任一新边，得到一个且仅有一个回路的图  T是连通的，但删去任一边后便不连通的图。 证明：（反证法）若T不连通，则存在结点ui与 uj，在ui与 uj之间没有路。 显然若增加新边 (ui,uj)，不会产生回路。则与题设“增加任一新边，得到一个且仅有一个回路的图”矛盾。 又∵T无回路，故删去任一边，图不连通。 T’ T

13 无向树的等价定义（证明5） 要证：（5）（6） 即：T是连通的，但删去任一边后便不连通的图  T是每一对结点间, 有且仅有一条通路的图。
证明：因图连通，故任两结点间有一条通路。 (反证法描述)若两结点之间有多于一条通路，则T中必有回路，删去该回路上任一条边，图仍连通，与题设“删去任一边后便不连通”矛盾。 所以，每一对顶点间必有唯一的一条通路。 T

14 无向树的等价定义（证明6） 要证：（6） （1） 即：T是每一对结点间有一条且仅有一条通路的图  T是无向树 证明：
任两结点间有唯一的一条通路，则图必连通。 (反证法)若图有回路，则回路上任两结点间有两条通路，与题设矛盾。

15 无向树的等价定义 给定无向简单图T=(V,E)，以下语句是等价的： （1）T是无向树；
（2）T是无回路，并且|E| = |V| - 1的图； （3）T是连通的，并且|E| = |V| - 1的图； （4）T是无回路，但增加任一新边，得到一个且仅有一个回路的图； （5）T是连通的，但删去任一边后便不连通的图； （6）T是每一对结点间有一条且仅有一条路的图。

16 无向树例题1 例1 已知无向树T有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求T的树叶个数, 并画出满足要求的非同构的无向树.
解： （利用树的性质|E| = |V|1和握手定理） 设有T有x片树叶，则 |V| =1+2+x=3+x, 2 |E| = 2(|V| 1)=2(2+x)=13+22+x 解出x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向树：

17 无向树例题2 判断下列度序列哪些可以作为无向树顶点的度序列： A 1,1,2,2,3； B 1,1,1,2,3；
C 1,1,1,2,3,4； D 1,1,1,1,2,4； 回答：B和D

18 树的性质 性质：若树T至少有两个结点，则T至少有两片树叶。 证明：∵ T =(V, E)是树，∴ |E| = |V| - 1。
又∵ T是连通的，∴对于任意viT，有deg (vi )  1，且  deg (vi ) =2|E| = 2(|V| -1) —— ① 式 若T没有树叶，即每个结点的度数均大于等于2，则 deg(vi) 2|V|，与①式矛盾 若T只有一片树叶，即有一个结点的度数等于1，其他每个结点的度数均大于等于2，则 d(vi)  1+2(|V| -1)=2|V| -1，与①式矛盾 故T至少有两片树叶。

19 生成树定义（1） G [定义]生成树 若无向图G的一个生成子图T是树，则称T为G的生成树。 只有连通图才有生成树。

20 生成树定义（2） 一个连通图可以有多棵生成树。 G

21 关于生成树的一个结论 图G中任一条回路和任意一棵生成树的补图至少有一条公共边。
证明：若G中一条回路C和G的一棵生成树T的补图无公共边，则表示该C在T中。这与生成树定义矛盾

22 最小生成树定义 [定义]最小生成树 一个连通的赋权图G中边权值之和最小的生成树称为G的最小生成树。

23 求最小生成树算法： kruskal算法 克鲁斯卡尔kruskal算法也称作避圈法。
设连通图G中有n个结点。G中的边按边权值从小到大排列为e1, e2 , …, em 。G的生成树T构造过程： (1) 初始化T为空树 (2) 将e1添加到T中。 (2) 检查e2, 若e2与e1不构成回路, 则将e2加入T中；. (3) 检查e3,…, 重复进行直至得到T中包含n-1条边为止.

24 kruskal算法举例1 利用Kruskal算法找出下图的一棵最小生成树。 11 1 6 3 2 7 8 10 5 4

25 kruskal算法正确性的证明 ∴T0为一棵树，且为图G的生成树。
证明：（1）先证明kruskal算法得到的图为图G=（V, E)的生成树。 设T0为kruskal算法构造的一个图，它的结点集是图G的结点集V，T0的边是e1， e2，…，en-1。 根据构造过程，T0中没有回路。 由树的等价定义（无回路，有n-1条边）， ∴T0为一棵树，且为图G的生成树。

26 kruskal算法正确性的证明（续1） （2）下证明T0为G的最小生成树。
设G的最小生成树为T，若T与T0相同，则T0为G的最小生成树，命题得证。 若T与T0不同，则T0中至少有一条边ei+1，使得ei+1不是T的边，但e1， e2，…，ei是T的边。 因为T是树，在T上加上边ei+1 必有一条回路r。 而T0是树，所以在r中必存在某条边f不在T0中。 对于树T，若添加ei+1删除f，则得到新的一棵树T 树T的权W(T) = W(T) + W( ei+1 )－W(f) 因为T是最小生成树，故W(T)  W(T) 即W( ei+1 )－W(f)  0 或W( ei+1 )  W(f)

27 Kruskal算法正确性的证明（续2） 而f不在T0中，故fe1, e2, …, ei, ei+1。而e1， e2，…，ei ， em， 按权值从小到大排列，故W(f)W( ei+1 ) 。 于是W( ei+1 ) = W(f)， 而W(T) = W(T) + W( ei+1 )－W(f) 因此， T也是一棵最小生成树。 但T与T0的公共边比T与T0的公共边多1。 用T置换T，重复上面论证，直到得到与T0有n-1条公共边的最小生成树。 这时，我们断定T0是最小生成树。

28 kruskal算法举例2 求下图给出的赋权连通图的一棵最小生成树。 1 2 1 2 3 3 2 2

29 有向树定义 [定义]有向树 底图为无向树的有向图，称为有向树。 每个分支都是有向树的图称为有向森林。 G

30 常用特殊有向树 有根树 k元树(k叉树) 有序树

31 有根树的定义（1） 有根树 恰有一个结点的入度为0，其余所有结点的入度都为1的有向树。 入度为0的结点称为根。
r T d a b c e f 有根树 恰有一个结点的入度为0，其余所有结点的入度都为1的有向树。 入度为0的结点称为根。 出度为0的结点，称为叶子（树叶）。 出度不为0的结点，称为分支点（内结点）。

32 有根树的定义（2） 注意：有向树通常采用根在最上层，所有边方向向下的图表示.(箭头也可省略)
h r T d a b c e f g i 若<x, y>为有根树中的有向边，则称x为y的父亲，y为x的儿子。 若结点x到y有有向通路，则称x是y的祖先；y是x的后裔。 注意：有向树通常采用根在最上层，所有边方向向下的图表示.(箭头也可省略)

33 有根树的定义（3） [定义]层次 从树根到顶点x的通路长度（即通路经过的边数），称为x的层次或水平。 [定义]高度
在有根树T中，最长通路的长度称为T的高度。 r T d a b c e f 第0层 第1层 第2层

34 请判断以下有根树T的高度。 h r T d a b c e f g i

35 有根树的定义（4） [定义]子树 在有根树T中任选一点x，由x以及x的所有后裔导出的子图称为T的子树。 r T a b c

36 有根树 k元树(k叉树) 有序树

37 k元树（k叉树） [定义] k元树（k叉树） T是有根树，如果T中各个分支点的儿子数至多为k，则称T为k元树。 [定义] 完全k元树
如果完全k元树所有树叶层次相同，称为正则m元树(满m叉树)。

38 完全k元树的性质 设完全k元树的叶子数为t，分枝数为i，则： t = (k-1)*i + 1 证明：在完全k元树中，边数为k*i，
k*i = i+t – 1 /* |E| = |V| -1*/ ∴ t = (k-1)*i + 1 注意：当k＝2时，t=i+1。即对任意不小于2 的正整数n，必能构造一棵有n片树叶的完全2元树。 叶子数: 5

39 完全k元树的性质应用举例 例题：设有28盏灯，拟公用一个电源插座，问最少需要用多少块具有四插座的接线板？
… 问题等价于：至少有28个树叶的4元树最少要包含几个分枝结点

40 完全k元树的性质应用举例 解：包含i个分枝结点4元树最多能包含 (4-1)*i + 1 个树叶，故要使得树叶不少于28，则有：
所以至少需要9块具有四插座的接线板。 分枝数为i的完全k元树的叶子数为 (k-1)*i + 1

41 有序树定义 [定义]有序树 每一个结点的儿子规定了次序（一般从左到右）的有根树。 每个连通分支都是有序树，并且各分支也有序的图称为有序森林。
1 2 3 1 3 2

42 树的同构与有序树 如果两棵树是同构的，但点的次序不同，则应看作两棵不同的树。 同 构

43 二元有序树 二元有序树中分支点的儿子有左儿子和右儿子之分，左右儿子位置不同。 a b a b

44 k元树与2元树的转换 2元树最易于计算机处理，因此常将k元有序树转化为2元有序树。 将k元有序树T转化为2元有序树T’的过程：
从根结点开始按层逐个处理分支点。 若T的分支点v有m个儿子，则将第一个儿子作为T’中v结点的左儿子，v的第i个儿子作为第i-1个儿子的右儿子。

45 k元树与2元树的转换举例（1） 3 1 2 3 4 5 6 有序2元树 4 2 1 5 6

46 k元树与2元树的转换举例（2） 请判断右树是否由左树转换所得的二元有序树 有序2元树？ 1 2 3 4 5 6 7 1 2 3 4 5 6
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 有序2元树？ 8 8 9 9

47 有序森林与有序二元树的转化 (1) 设置一个总根，联结各树的根，得T’； (2) 把T’转换为二元树； (3) 删除总根 ；
[定义]有序森林 一个有向图G，若它的每个连通分支是有序树，且给每棵树指定次序，称此森林为有序森林。 转化过程： (1) 设置一个总根，联结各树的根，得T’； (2) 把T’转换为二元树； (3) 删除总根 ；

48 森林与二叉树的转化举例 R R B B C D E F G H I K C H D E I G K F

49 课堂练习 1. 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构的无向树.

50 课堂练习解答 1. 解：设T的阶数为n, 则边数为n1, 4度顶点的个数为n7.设边数为m，由握手定理得
2m = 2(n1) = 51+21+31+4(n7) 解出n = 8, ∴4度顶点为1个. T的度数列为1,1,1,1,1,2,3,4 有3棵非同构的无向树

51 作 业 P216：4、8

52 周游（遍历）算法 二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的过程。 类型： 前序 中序 后序

53 左子树与右子树 左子树 右子树

54 先序周游算法 先序遍历二叉树的过程： (1)访问根结点； (2)先序遍历左子树； (3)先序遍历右子树。 a b c d e
a  b  d  e  c

55 练习 C B D E G K H I F J B C B D E G K H I F J B C C H H D E E D G F J I
给出下列二叉树先序遍历结点的访问顺序： C B D E G K H I F J B C B D E G K H I F J B C C H H D E E D G F J I J G I K F K

56 中序周游算法 中序遍历二叉树的过程： (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。 a b c d e
b a  c d b  e  a  c

57 练习 C B D E G K H I F J B C B D E G K H I F J B C C H H D E E D G F J I
给出下列二叉树中序遍历结点的访问顺序： C B D E G K H I F J B C B D E G K H I F J B C C H H D E E D G F J I J G I K F K

58 后序周游算法 后序遍历二叉树的过程： (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点。 a b c d e
b  c  a d e  b  c  a

59 练习 C B D E G K H I F J B C B D E G K H I F J B C C H H D E E D G F J I
给出下列二叉树后序遍历结点的访问顺序： C B D E G K H I F J B C B D E G K H I F J B C C H H D E E D G F J I J G I K F K

60 树的遍历举例 B 已知树T(V, E)： 1）T的先序遍历次序为：GFKDAIEBCHJ 2） T的中序遍历次序为：DKIAFEGCBJH

61 + * * 波兰式 - a b c d e f + c a b / 用于表示算术表达式，也称作前缀式。 写法：将运算符写在运算数的前面。
例： a+b 写成 +ab a*b 写成 *ab (a+b)*c 写成 *+abc - / + * a b c d e f * 波兰式的构造过程，就是算术表达式树的前缀遍历。 + c a b -+a*b-cd/ef

62 + * * 逆波兰式 - a b c d e f + c a b / 写法：将运算符写在运算数的后面。 例： a+b 写成 ab+
(a+b)*c 写成 ab+c* - / + * a b c d e f * 逆波兰式的构造过程，就是算术表达式树的后缀遍历。 + c a b abcd-*+ef/-