1
第 9章 树
? 9.1 无向树及生成树
? 9.2 根树及其应用
2
9.1 无向树及生成树
?无向树, 森林
?树枝, 弦, 余树
?生成树
?基本回路与基本回路系统
?基本割集与基本割集系统
?最小生成树
3
无向树
无向树, 连通无回路的无向图
平凡树, 平凡图
森林, 每个连通分支都是树的非连通的无向图
树叶, 树中度数为 1的顶点
分支点, 树中度数 ?2的顶点
右图为一棵 12阶树,
声明,本章中所讨论的回路均
指简单回路或初级回路
4
无向树的性质
定理 9.1 设 G=<V,E>是 n阶 m条边的无向图, 则下面
各命题是等价的,
（ 1） G是树 (连通无回路 );
（ 2） G中任意两个顶点之间存在惟一的路径 ;
（ 3） G中无回路且 m=n?1;
（ 4） G是连通的且 m=n?1;
（ 5） G是连通的且 G中任何边均为桥 ;
（ 6） G中没有回路,但在任何两个不同的顶点之间
加一条新边后所得图中有惟一的一个含新边的圈,
5
无向树的性质 (续 )
)(2)()1(2 xnxvdn i ????? ?
定理 9.2 设 T 是 n 阶非平凡的无向树, 则 T中至少
有两片树叶,
证 设 T有 x片树叶, 由握手定理及定理 9.1可知,
由上式解出 x?2,
6
例题
例 1 已知无向树 T中,有 1个 3度顶点,2个 2度顶点,其余顶点全
是树叶, 试求树叶数,并画出满足要求的非同构的无向树,
解 用树的性质 m=n?1和握手定理,
设有 x片树叶, 于是 n=1+2+x=3+x,
2m=2(n?1)=2?(2+x)=1?3+2?2+x
解出 x=3，故 T有 3片树叶,
T的度数列为 1,1,1,2,2,3
有 2棵非同构的无向树,如图所示
7
例题
例 2 已知无向树 T有 5片树叶,2度与 3度顶点各 1个,其余顶点
的度数均为 4,求 T的阶数 n,并画出满足要求的所有非同构
的无向树,
解 设 T的阶数为 n,则边数为 n?1,4度顶点的个数为 n?7,由握
手定理得
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棵非同构的无向树
8
生成树
T
T
设 G为无向连通图
G的 生成树, G的生成子图并且是树
生成树 T的 树枝, G在 T中的边
生成树 T的 弦, G不在 T中的边
生成树 T的 余树, 所有弦的集合的导出子图
注意,不一定连通,也不一定不含回路,
右图黑边构成生成树
红边构成余树
9
生成树的存在性
定理 任何无向连通图都有生成树,
证 用破圈法, 若图中无圈,则图本身就是自己的生成树,
否则删去圈上的任一条边,这不破坏连通性,重复进行
直到无圈为止,剩下的图是一棵生成树,
推论 1 设 n阶无向连通图有 m条边,则 m?n?1,
推论 2 设 n阶无向连通图有 m条边,则它的生成树的余树
有 m?n+1条边,
推论 3 设 为 G的生成树 T 的余树,C 为 G 中任意一
个圈，则 C与 一定有公共边,
T
T
10
基本回路与基本回路系统
定义 设 T是 n阶 m条边的无向连通图 G的一棵生成
树, 设 e1?,e2?,…,e?m?n+1为 T的弦, 设 Cr为 T添加弦 er?
产生的 G中惟一的圈 (由 er?和 树枝组成 ),称 Cr为对应
弦 er?的 基本回路 或 基本圈,r=1,2,…,m?n+1,称 {C1,
C2,…,Cm?n+1}为对应 T的 基本回路系统,
求基本回路的算法, 设弦 e=(u,v),先求 T中 u到 v的路径
?uv,再并上弦 e,即得对应 e的基本回路,
11
基本割集与基本割集系统
定义 设 T是 n阶连通图 G的一棵生成树,e1?,e2?,…,
e?n?1为 T的树枝, Si是 G的只含树枝 ei?,其他边都是弦
的割集,称 Si为对应生成树 T由树枝 ei?生成的 基本割
集,i=1,2,…,n?1,称 {S1,S2,…,Sn?1}为对应 T的 基本
割集系统,
求基本割集的算法, 设 e?为生成树 T的树枝,T?e?由两
棵子树 T1与 T2组成,令
Se?={e | e?E(G)且 e的两个端点分别属于 T1与 T2}
则 Se?为 e?对应的基本割集,
12
实例
例 图中红边为一棵生成树,
求对应它的基本回路系统
与基本割集系统
解 弦 e,f,g对应的基本回路分别为
Ce=e b c,Cf=f a b c,Cg=g a b c d,
C基 ={Ce,Cf,Cg},
树枝 a,b,c,d对应的基本割集分别为
Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,f g},Sd={d,g},
S基 ={Sa,Sb,Sc,Sd},
13
无向图与最小生成树
对无向图或有向图的每一条边 e附加一个实数 w(e),称作 边 e
的权, 图连同附加在边上的权称作 带权图,记作 G=<V,E,W>,
设 G?是 G的子图,G?所有边的权的和称作 G?的权,记作 W(G?),
最小生成树, 带权图权最小的生成树
求最小生成树的算法 —— 避圈法 (Kruskal)
设 G=<V,E,W>,将非环边按权从小到大排序,e1,e2,…,em,
(1) 取 e1在 T中
(2) 检查 e2,若 e2与 e1不构成回路,则将 e2加入 T中,否则弃去 e2,
(3) 检查 e3,…,重复进行直至得到生成树为止,
14
实例
例 求图的一棵最小生成树
W(T)=38
15
9.2 根树及其应用
?有向树 ?
根树, 树根, 树叶, 内点, 分支点 ?
家族树, 根子树, 有序树 ?
r元树 （ r元有序树 ） ?
r元正则树 （ r元有序正则树 ） ?
r元完全正则树 （ r元有序完全正则树 ） ?
最优 2元树与 Huffman算法 ?
前缀吗与最佳前缀吗 ?
中序行遍法, 前序行遍法, 后续行遍法 ?
波兰符号法与逆波兰符号法
16
有向树与根树的定义
有向树, 基图为无向树的有向图
根树, 有一个顶点入度为 0,其余的入度均为 1的
非平凡的有向树
树根, 有向树中入度为 0的顶点
树叶, 有向树中入度为 1,出度为 0的顶点
内点, 有向树中入度为 1,出度大于 0的顶点
分支点, 树根与内点的总称
顶点 v的层数, 从树根到 v的通路长度
树高, 有向树中顶点的最大层数
17
根树 (续 )
根树的画法,树根放上方,省去所有有向边上的箭头
如右图所示
a是树根
b,e,f,h,i是树叶
c,d,g是内点
a,c,d,g是分支点
a为 0层 ;1层有 b,c; 2层有 d,e,f;
3层有 g,h; 4层有 i,
树高为 4
18
家族树
定义 把根树看作一棵 家族树,
(1) 若顶点 a 邻接到顶点 b,则称 b 是 a 的 儿子,a 是
b 的 父亲 ;
(2) 若 b和 c为同一个顶点的儿子,则称 b和 c是 兄弟 ;
(3) 若 a?b且 a可达 b,则称 a是 b的 祖先,b是 a的 后代,
设 v为根树的一个顶点且不是树根,称 v及其所有后
代的导出子图为以 v为根的 根子树,
19
根树的分类
有序树, 将根树同层上的顶点规定次序
r元树,根树的每个分支点至多有 r个儿子
r元正则树, 根树的每个分支点恰有 r个儿子
r元完全正则树, 树叶层数相同的 r元正则树
r元有序树, 有序的 r元树
r元正则有序树, 有序的 r元正则树
r元完全正则有序树, 有序的 r元完全正则树
20
最优 2元树
)()(
1
i
t
i
i vlwtW ?
?
?
定义 设 2元树 T有 t片树叶 v1,v2,…,vt,树叶的权分别
为 w1,w2,…,wt,称 为 T的权,记作
W(T),其中 l(vi)是 vi的层数, 在所有有 t片树叶,带权
w1,w2,…,wt 的 2元树中,权最小的 2元树称为 最优
2元树,
21
求最优树
Huffman算法,
给定实数 w1,w2,…,wt,
① 作 t片树叶,分别以 w1,w2,…,wt为权,
② 在所有入度为 0的顶点 (不一定是树叶 )中选出两个
权最小的顶点,添加一个新分支点,以这 2个顶点为
儿子,其权等于这 2个儿子的权之和,
③ 重复②,直到只有 1个入度为 0 的顶点为止,
W(T)等于所有分支点的权之和
22
实例
例 求带权为 1,1,2,3,4,5的最优树,
解题过程由下图给出,W(T)=38
23
前缀码
设 ? =?1?2… ?n-1?n是长度为 n的符号串
?的 前缀, ?1?2… ?k,k=1,2,…,n-1
前缀码, {?1,?2,…,?m},其中 ?1,?2,…,?m为非空字符
串,且任何两个互不为前缀
2元前缀码, 只出现两个符号 (如 0与 1)的前缀码
如 {0,10,110,1111},{10,01,001,110}是 2元前缀码
{0,10,010,1010} 不是前缀码
24
前缀码 (续 )
一棵 2元树产生一个二元前缀码,
对每个分支点,若关联 2条边,则给左边标 0,右边标 1;
若只关联 1条边,则可以给它标 0(看作左边 ),也可以
标 1(看作右边 ),将从树根到每一片树叶的通路上标
的数字组成的字符串
记在树叶处,所得的字符
串构成一个前缀码,
如右图所示
25
最佳前缀码
例 在通信中, 设八进制数字出现的频率如下,
0,25% 1,20% 2,15% 3,10%
4,10% 5,10% 6,5% 7,5%
采用 2元前缀码,求传输数字最少的 2元前缀码 (称作 最佳前
缀码 ),并求传输 10n(n?2)个按上述比例出现的八进制数字需
要多少个二进制数字？若用等长的 (长为 3) 的码字传输需要
多少个二进制数字?
解 用 Huffman算法求以频率 (乘以 100)为权的最优 2元树, 这
里 w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25,
最优 2元树如图所示,
26
编码,
0---01
1---11
2---001
3---100
4---101
5---0001
6---00000
7---00001
传 100个按比例出现的八进制数字所需二进制数字的个数
为 W(T)=285,
传 10n(n?2)个所用二进制数字的个数为 2.85?10n,而用等长
码 (长为 3)需要用 3?10n个数字,
27
波兰符号法与逆波兰符号法
行遍 (周游 )根树 T, 对 T 的每个顶点访问且仅访问一次,
行遍 2元有序正则树的方式,
① 中序行遍法, 左子树, 根, 右子树
② 前序行遍法, 根, 左子树, 右子树
③ 后序行遍法, 左子树、右子树、根
例如,对图所示根树按中序, 前序,
后序行遍法访问结果分别为,
b a (f d g) c e a b (c (d f g) e) b ((f g d) e c) a
带下划线的是 (子 )树根,一对括号内是一棵子树
28
波兰符号法与逆波兰符号法 (续 )
用 2元有序正则树表示算式, 最高层次运算放在树
根上,然后依次将运算符放在根子树的根上,数放
在树叶上,规定被除数, 被减数放在左子树树叶上,
例如,右图表示算式
((b+(c+d))?a)?((e?f)?(g+h)?(i?j))
29
波兰符号法与逆波兰符号法 (续 )
波兰符号法 (前缀符号法 ),按前序行遍法访问表示
算式的 2元有序正则树,其结果不加括号,规定每个
运算符号与其后面紧邻两个数进行运算,
例如,对上页中树的访问结果为
? ? ? b + c d a ? ? e f ? + g h ? i j
逆波兰符号法 (后缀符号法 ),按后序行遍法访问,
规定每个运算符与前面紧邻两数运算,
例如,对上页中树的访问结果为
b c d + + a ? e f ? g h + i j ? ? ? ?
第 9章 树
? 9.1 无向树及生成树
? 9.2 根树及其应用
2
9.1 无向树及生成树
?无向树, 森林
?树枝, 弦, 余树
?生成树
?基本回路与基本回路系统
?基本割集与基本割集系统
?最小生成树
3
无向树
无向树, 连通无回路的无向图
平凡树, 平凡图
森林, 每个连通分支都是树的非连通的无向图
树叶, 树中度数为 1的顶点
分支点, 树中度数 ?2的顶点
右图为一棵 12阶树,
声明,本章中所讨论的回路均
指简单回路或初级回路
4
无向树的性质
定理 9.1 设 G=<V,E>是 n阶 m条边的无向图, 则下面
各命题是等价的,
（ 1） G是树 (连通无回路 );
（ 2） G中任意两个顶点之间存在惟一的路径 ;
（ 3） G中无回路且 m=n?1;
（ 4） G是连通的且 m=n?1;
（ 5） G是连通的且 G中任何边均为桥 ;
（ 6） G中没有回路,但在任何两个不同的顶点之间
加一条新边后所得图中有惟一的一个含新边的圈,
5
无向树的性质 (续 )
)(2)()1(2 xnxvdn i ????? ?
定理 9.2 设 T 是 n 阶非平凡的无向树, 则 T中至少
有两片树叶,
证 设 T有 x片树叶, 由握手定理及定理 9.1可知,
由上式解出 x?2,
6
例题
例 1 已知无向树 T中,有 1个 3度顶点,2个 2度顶点,其余顶点全
是树叶, 试求树叶数,并画出满足要求的非同构的无向树,
解 用树的性质 m=n?1和握手定理,
设有 x片树叶, 于是 n=1+2+x=3+x,
2m=2(n?1)=2?(2+x)=1?3+2?2+x
解出 x=3，故 T有 3片树叶,
T的度数列为 1,1,1,2,2,3
有 2棵非同构的无向树,如图所示
7
例题
例 2 已知无向树 T有 5片树叶,2度与 3度顶点各 1个,其余顶点
的度数均为 4,求 T的阶数 n,并画出满足要求的所有非同构
的无向树,
解 设 T的阶数为 n,则边数为 n?1,4度顶点的个数为 n?7,由握
手定理得
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棵非同构的无向树
8
生成树
T
T
设 G为无向连通图
G的 生成树, G的生成子图并且是树
生成树 T的 树枝, G在 T中的边
生成树 T的 弦, G不在 T中的边
生成树 T的 余树, 所有弦的集合的导出子图
注意,不一定连通,也不一定不含回路,
右图黑边构成生成树
红边构成余树
9
生成树的存在性
定理 任何无向连通图都有生成树,
证 用破圈法, 若图中无圈,则图本身就是自己的生成树,
否则删去圈上的任一条边,这不破坏连通性,重复进行
直到无圈为止,剩下的图是一棵生成树,
推论 1 设 n阶无向连通图有 m条边,则 m?n?1,
推论 2 设 n阶无向连通图有 m条边,则它的生成树的余树
有 m?n+1条边,
推论 3 设 为 G的生成树 T 的余树,C 为 G 中任意一
个圈，则 C与 一定有公共边,
T
T
10
基本回路与基本回路系统
定义 设 T是 n阶 m条边的无向连通图 G的一棵生成
树, 设 e1?,e2?,…,e?m?n+1为 T的弦, 设 Cr为 T添加弦 er?
产生的 G中惟一的圈 (由 er?和 树枝组成 ),称 Cr为对应
弦 er?的 基本回路 或 基本圈,r=1,2,…,m?n+1,称 {C1,
C2,…,Cm?n+1}为对应 T的 基本回路系统,
求基本回路的算法, 设弦 e=(u,v),先求 T中 u到 v的路径
?uv,再并上弦 e,即得对应 e的基本回路,
11
基本割集与基本割集系统
定义 设 T是 n阶连通图 G的一棵生成树,e1?,e2?,…,
e?n?1为 T的树枝, Si是 G的只含树枝 ei?,其他边都是弦
的割集,称 Si为对应生成树 T由树枝 ei?生成的 基本割
集,i=1,2,…,n?1,称 {S1,S2,…,Sn?1}为对应 T的 基本
割集系统,
求基本割集的算法, 设 e?为生成树 T的树枝,T?e?由两
棵子树 T1与 T2组成,令
Se?={e | e?E(G)且 e的两个端点分别属于 T1与 T2}
则 Se?为 e?对应的基本割集,
12
实例
例 图中红边为一棵生成树,
求对应它的基本回路系统
与基本割集系统
解 弦 e,f,g对应的基本回路分别为
Ce=e b c,Cf=f a b c,Cg=g a b c d,
C基 ={Ce,Cf,Cg},
树枝 a,b,c,d对应的基本割集分别为
Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,f g},Sd={d,g},
S基 ={Sa,Sb,Sc,Sd},
13
无向图与最小生成树
对无向图或有向图的每一条边 e附加一个实数 w(e),称作 边 e
的权, 图连同附加在边上的权称作 带权图,记作 G=<V,E,W>,
设 G?是 G的子图,G?所有边的权的和称作 G?的权,记作 W(G?),
最小生成树, 带权图权最小的生成树
求最小生成树的算法 —— 避圈法 (Kruskal)
设 G=<V,E,W>,将非环边按权从小到大排序,e1,e2,…,em,
(1) 取 e1在 T中
(2) 检查 e2,若 e2与 e1不构成回路,则将 e2加入 T中,否则弃去 e2,
(3) 检查 e3,…,重复进行直至得到生成树为止,
14
实例
例 求图的一棵最小生成树
W(T)=38
15
9.2 根树及其应用
?有向树 ?
根树, 树根, 树叶, 内点, 分支点 ?
家族树, 根子树, 有序树 ?
r元树 （ r元有序树 ） ?
r元正则树 （ r元有序正则树 ） ?
r元完全正则树 （ r元有序完全正则树 ） ?
最优 2元树与 Huffman算法 ?
前缀吗与最佳前缀吗 ?
中序行遍法, 前序行遍法, 后续行遍法 ?
波兰符号法与逆波兰符号法
16
有向树与根树的定义
有向树, 基图为无向树的有向图
根树, 有一个顶点入度为 0,其余的入度均为 1的
非平凡的有向树
树根, 有向树中入度为 0的顶点
树叶, 有向树中入度为 1,出度为 0的顶点
内点, 有向树中入度为 1,出度大于 0的顶点
分支点, 树根与内点的总称
顶点 v的层数, 从树根到 v的通路长度
树高, 有向树中顶点的最大层数
17
根树 (续 )
根树的画法,树根放上方,省去所有有向边上的箭头
如右图所示
a是树根
b,e,f,h,i是树叶
c,d,g是内点
a,c,d,g是分支点
a为 0层 ;1层有 b,c; 2层有 d,e,f;
3层有 g,h; 4层有 i,
树高为 4
18
家族树
定义 把根树看作一棵 家族树,
(1) 若顶点 a 邻接到顶点 b,则称 b 是 a 的 儿子,a 是
b 的 父亲 ;
(2) 若 b和 c为同一个顶点的儿子,则称 b和 c是 兄弟 ;
(3) 若 a?b且 a可达 b,则称 a是 b的 祖先,b是 a的 后代,
设 v为根树的一个顶点且不是树根,称 v及其所有后
代的导出子图为以 v为根的 根子树,
19
根树的分类
有序树, 将根树同层上的顶点规定次序
r元树,根树的每个分支点至多有 r个儿子
r元正则树, 根树的每个分支点恰有 r个儿子
r元完全正则树, 树叶层数相同的 r元正则树
r元有序树, 有序的 r元树
r元正则有序树, 有序的 r元正则树
r元完全正则有序树, 有序的 r元完全正则树
20
最优 2元树
)()(
1
i
t
i
i vlwtW ?
?
?
定义 设 2元树 T有 t片树叶 v1,v2,…,vt,树叶的权分别
为 w1,w2,…,wt,称 为 T的权,记作
W(T),其中 l(vi)是 vi的层数, 在所有有 t片树叶,带权
w1,w2,…,wt 的 2元树中,权最小的 2元树称为 最优
2元树,
21
求最优树
Huffman算法,
给定实数 w1,w2,…,wt,
① 作 t片树叶,分别以 w1,w2,…,wt为权,
② 在所有入度为 0的顶点 (不一定是树叶 )中选出两个
权最小的顶点,添加一个新分支点,以这 2个顶点为
儿子,其权等于这 2个儿子的权之和,
③ 重复②,直到只有 1个入度为 0 的顶点为止,
W(T)等于所有分支点的权之和
22
实例
例 求带权为 1,1,2,3,4,5的最优树,
解题过程由下图给出,W(T)=38
23
前缀码
设 ? =?1?2… ?n-1?n是长度为 n的符号串
?的 前缀, ?1?2… ?k,k=1,2,…,n-1
前缀码, {?1,?2,…,?m},其中 ?1,?2,…,?m为非空字符
串,且任何两个互不为前缀
2元前缀码, 只出现两个符号 (如 0与 1)的前缀码
如 {0,10,110,1111},{10,01,001,110}是 2元前缀码
{0,10,010,1010} 不是前缀码
24
前缀码 (续 )
一棵 2元树产生一个二元前缀码,
对每个分支点,若关联 2条边,则给左边标 0,右边标 1;
若只关联 1条边,则可以给它标 0(看作左边 ),也可以
标 1(看作右边 ),将从树根到每一片树叶的通路上标
的数字组成的字符串
记在树叶处,所得的字符
串构成一个前缀码,
如右图所示
25
最佳前缀码
例 在通信中, 设八进制数字出现的频率如下,
0,25% 1,20% 2,15% 3,10%
4,10% 5,10% 6,5% 7,5%
采用 2元前缀码,求传输数字最少的 2元前缀码 (称作 最佳前
缀码 ),并求传输 10n(n?2)个按上述比例出现的八进制数字需
要多少个二进制数字？若用等长的 (长为 3) 的码字传输需要
多少个二进制数字?
解 用 Huffman算法求以频率 (乘以 100)为权的最优 2元树, 这
里 w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25,
最优 2元树如图所示,
26
编码,
0---01
1---11
2---001
3---100
4---101
5---0001
6---00000
7---00001
传 100个按比例出现的八进制数字所需二进制数字的个数
为 W(T)=285,
传 10n(n?2)个所用二进制数字的个数为 2.85?10n,而用等长
码 (长为 3)需要用 3?10n个数字,
27
波兰符号法与逆波兰符号法
行遍 (周游 )根树 T, 对 T 的每个顶点访问且仅访问一次,
行遍 2元有序正则树的方式,
① 中序行遍法, 左子树, 根, 右子树
② 前序行遍法, 根, 左子树, 右子树
③ 后序行遍法, 左子树、右子树、根
例如,对图所示根树按中序, 前序,
后序行遍法访问结果分别为,
b a (f d g) c e a b (c (d f g) e) b ((f g d) e c) a
带下划线的是 (子 )树根,一对括号内是一棵子树
28
波兰符号法与逆波兰符号法 (续 )
用 2元有序正则树表示算式, 最高层次运算放在树
根上,然后依次将运算符放在根子树的根上,数放
在树叶上,规定被除数, 被减数放在左子树树叶上,
例如,右图表示算式
((b+(c+d))?a)?((e?f)?(g+h)?(i?j))
29
波兰符号法与逆波兰符号法 (续 )
波兰符号法 (前缀符号法 ),按前序行遍法访问表示
算式的 2元有序正则树,其结果不加括号,规定每个
运算符号与其后面紧邻两个数进行运算,
例如,对上页中树的访问结果为
? ? ? b + c d a ? ? e f ? + g h ? i j
逆波兰符号法 (后缀符号法 ),按后序行遍法访问,
规定每个运算符与前面紧邻两数运算,
例如,对上页中树的访问结果为
b c d + + a ? e f ? g h + i j ? ? ? ?
