离散数学及其应用-第2版 课件 第10章树

第10章

树2第10章树10.1树的定义和特性 10.2生成树 10.3根树 10.4根树的应用10.1树的定义和特性定义10.1.1

一个连通且无回路的无向图称为无向树。树中的边称为树枝。度数为1的结点称为树叶。度数大于1的结点称为分支点(内点)。平凡图称为平凡树。定义10.1.2一个不连通的，但每个连通分支都是无向树的图称为森林。例如(a)(b)无向树的性质定理10.1.1对于有n个结点，e条边的无向树T，下列的命题等价。(1)T是无回路的连通图。(2)T是连通的但删去任一边后,便不连通。(3)T是连通的且e=n-1。(4)T中无回路且e=n-1。(5)在T的每一对结点之间有唯一的一条简单路。(6)T中无回路,但在任意两个结点间增加一条边,得到一条且仅一条回路。4定理10.1.1的证明(1)(2)。用反证法证。对u,vV，若T中删去任一边（u，v）后仍连通，则从u到v存在一条通路L，这条通路L加上（u，v）后形成回路，和T无回路矛盾。(2)(3)。对结点个数n用数学归纳法来证明e=n-1：当结点数为n=1时，T是平凡图，结论显然成立。当结点数为n=2时，T是连通的但删去任一边后,便不连通，则e=1，结论成立。假设结点数为nk（k>1）时，结论成立。当结点数为n=k+1时，只有删去T中的一个1度结点及其关联的边的图T，才满足命题（2）的连通性。根据归纳假设，T有k个结点，所以e=n-1，而e=e-1，n=n-1。因此，将删去的1度结点及其关联的边添入T得到图T，T仍连通且e=n-1。5定理10.1.1的证明(续)（3）

（4）。对结点个数n用数学归纳法来证明T是无回路的：当结点数为2时，e=1，T中无回路，即结论成立。假设结点数为n=k-1时无回路，e=n-1，结论成立。当结点数为n=k时，因为T是连通的，故T中每一个节点的度数均大于等于1.可以证明至少有一个结点v0，使得deg(v0)=1。因为若所有结点的度数均大于等于2，则

，从而e

k,，即图T至少有k条边，与e=n-1矛盾。在T中删去1度结点v0及其关联的边，得到新图T

也是连通的。根据归纳假设，T

无回路，e

=n

-1，将删去的1度结点v0及其关联的边添入T

得到图T

，T中仍无回路，且e=n-1。（4）

（5）。用反证法证明。假设在T的每一对结点之间的简单路不唯一，若结点u,v之间存在两条简单路，这两条简单路构成回路，和T中无回路矛盾，所以在T的每一对结点之间有唯一的一条简单路。6定理10.1.1的证明(续)（5）

（6）。首先用反证法证明T中无回路。假设T中有回路，设C是一条包含边（u，v）的简单回路，在C中删去边（u，v）得到从u到v的一条简单通路，因而从u到v的简单通路不唯一，与命题（5）矛盾。若在T的任意两个不邻接的结点间加上一条边e，则e和联接这两个结点的唯一一条简单路构成T+e的唯一的一条回路。（6）

（1）。根据命题（6）,任意两个结点间存在一条通路，所以T是连通的，结论成立。7无向树的性质(续)定理10.1.2

设T是有n(n

2)个结点的一棵树,则T中至少有两片树叶。8证设有x片树叶,由握手定理和定理10.1.1,有

解得x

2.实例例10.1.2

画出所有6阶非同构的无向树。9解5条边,总度数等于10可能的度数列:(1)1,1,1,1,1,5(2)1,1,1,1,2,4(3)1,1,1,1,3,3(4)1,1,1,2,2,3(5)1,1,2,2,2,2(1)(2)(3)(4a)(4b)(5)实例例10.1.3

已知无向树T中,有1个3度顶点,3个2度顶点,其余结点全是树叶.T中有多少树叶？画出满足要求的非同构的无向树.10解设有x片树叶,2

(1+3+x-1)=1

3+3

2+x解得x=3，故T有3片树叶.T的度数列为1,1,1,2,2,2,3生成树定义10.2.1给定连通图G,如果它的生成子图TG是树,则称TG为G的生成树。生成树TG中的边称为树枝；G中的不在TG中的边称为弦；TG的所有弦的集合称为生成树TG的余树。11例如图中黑边构成生成树红边构成余树注意:余树一般不是树例题例10.2.1

在图10.2.1中，哪些是图10.2.1(1)的生成树？

（1）(2)(3)

(4)(5)（6）解

（2）（5）是（1）的生成树。（3）(4)（6）不是（1）的生成树。生成树的存在性定理10.2.1图G有生成树，当且仅当G是连通的。证明(破圈法)首先证明充分性。当图G是连通的，如果图G是一棵树时，G本身就是生成树。当连通图G不是一棵树时，G中有回路。对于G的一个回路，删去回路上的一条边，得到G的生成子图G

。若G

仍有回路，继续删去其中一个回路上的一条边。重复这个过程，直到得到G的生成子图中没有回路，从而得到G的一棵生成树TG。证明必要性。若图G有生成树，由于树是连通的，所以G是连通的。13求生成树求生成树的避圈法：设图G=（V，E），|V|=n，E={e1，e2，

，em}，

任取一条边e

E，令TG={e}；任取一条边e

E-TG，若TG

{e}无回路，则把e添加到TG中；若TG中的元素有n-1个，则算法结束，否则返回②。

当把n-1条边加入TG时，TG就是图G的生成树。例题例3如下图所示的无向图G，用避圈法求生成树.==》解

对无向图G，依次取边(a，b)，(b，c)，(b，e)和(d，e)，就得到G的一棵生成树，如上面右图所示。例题例4对下图的无向图G，用破圈法求生成树。解

依次在图G中删去边（a，d），（d，e），（b，c），如（1）(2)(3)所示，使得图G没有回路，就得到G的一棵生成树。

（1）（2）（3）基本割集定义10.2.2

设T是n阶连通图G的一棵生成树，e1,e2,…,en-1为T

的树枝，Sei是G的只含树枝ei的割集，则称Sei为G的对应于生成树T由树枝ei生成的基本割集，i=1,2,…,n-1，并称这些割集的全体为G对应T的基本割集组，称n-1为G的割集秩，记作η(G)。树枝a,b,c,d对应的基本割集:Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,f

g},Sd={d,g},{Sa,Sb,Sc,Sd}为G

对应T

的基本割集组，割集秩η(G)=4.基本回路

树的基本变换

定理

10.2.2最小生成树及其应用定义10.2.2设无向连通带权图G=(V,E,W)，T是G的一棵生成树，T各边带权之和称为T的权，记作W(T)。G的所有生成树中带权最小的生成树称为最小生成树。最小生成树的典型算法有Kruskal算法、Prim算法和Sollin算法Kruskal算法Kruskal算法（基于避圈法思想）设G=（V,E,W）是n阶连通带权图，(1)在边集E中选一条具有最小权值的边e，加入生成树T中，并将e从边集E中删去。(2)在边集E中选一条具有最小权值的边e，若e和已在T中的边不构成回路，将e添加到T中，并从边集E中删去e；若e和已在T中的边构成回路，从边集E中删去e。(3)若T中的边数为n-1，算法结束，否则返回（2）。算法结束时，T就是G的最小生成树。实例例5求图的一棵最小生成树23W(T)=3810.3根树10.3.1有向根树和有序根数10.3.2有序根树的遍历2510.3.1有向根树和有序根数定义10.3.1一个有向图G，如果略去有向边的方向所得无向图为一棵无向树，则称G为有向树。

有向根树定义10.3.2一棵非平凡的有向树，如果有一个结点的入度为0，其余结点的入度均为1，则称此有向树为有向根树。称入度为0的结点为树根，称出度为0的结点为树叶，称出度不为0的结点（含根）为分支点（内点）。在根树中，从树根到任意结点vi只有唯一的一条简单路，这条路的长度称为vi的级(层)数。级数最大的结点的级数称为树的高度。

实例根树的画法:树根放最上方,省去所有有向边上的箭头右图中

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.

树高为42728有向根树定义10.3.3在根树T中，(1)若结点vi到结点vj可达，则称vi是vj的祖先，vj是vi的后代；(2)若结点vi邻接到结点vj，则称vi是vj的父亲，vj是vi的儿子；(3)若两个节点同为一个结点的儿子，则称这两个结点为兄弟。定义10.3.4设T为一棵根树，vi为T中一个结点，且vi不是树根，称vi及其后代的导出子图为T的以vi为根的子树，简称根子树。m元树定义10.3.5在根树中，如果每个结点的出度小于或等于m，则称这棵树为m元树。m=2时称为二元树或二叉树。如果每个分支点的出度都等于m

，则称这棵树为m元正则树。所有树叶级(层)数相同的m元正则树称为完全m元正则树。三元树三元正则树

完全二元正则树定理10.3.1定理10.3.1有i个分支点的m元正则树有n=mi+1个结点。证明

除根之外的每个结点都是分支点的儿子。因为每个分支点都有m个儿子，所以，在树中除根之外还有mi个结点。因此，这棵树共有mi+1个结点。定理10.3.2定理10.3.2一个m元正则树T若T有n个结点，则有i=（n−1）/m个分支点和l=[(m−1)n+1]/m片树叶；若T有i个分支点，则有n=mi+1个结点和l=(m−1)i+1片树叶；若T有l片树叶，则有n=(ml−1)/(m−1)个结点和i=（l−1）/(m−1)个分支点。定理10.3.2证明

(1)若T有n个结点，利用定理10.3.1，n=mi+1，则分支点i=（n−1）/m，树叶数l=n−i,将i的表达式代入l=n−i,得l=[(m−1)n+1]/m。(2)若T有i个分支点，利用定理10.3.1，有n=mi+1个结点；树叶数l=n−i，将n的表达式代入得l=(m−1)i+1；(3)若T有l片树叶，i=n−l,代入n=mi+1，则有n=m(n−l)+1,整理得n=(ml−1)/(m−1)，而分支点数i=n−l=(ml−1)/(m−1)−l=（l−1）/(m−1)。例题例9.3.3假设有一条计算机加法指令，可计算3个数之和。如果要计算33个数x1,x2,...x33之和，则至少执行几次加法指令？解：将问题表示为根树，有33片树叶，执行指令的结果为分支点，则问题为：求有33片树叶的3元树，有多少个分支点？由定理10.3.2可得:i=（l−1）/(m−1)=(33-1)/(3-1)=16即要执行16次加法指令.定理10.3.3定理10.3.3在高度为h的m元树里至多有mh片树叶。证明

用归纳法对高度h进行归纳证明。假设高度h=1。高度h=1的m元树由根结点及其不超过m个子结点组成，每个子结点都是树叶。因此高度为h的m元树里至多有m1=m片树叶。假设高度h=k-1时结论成立，即高度为k-1的m元树里至多有mk-1片树叶。高度h=k时，在高度为k-1的m元树中给每片树叶添加至多m个子结点，就是高度为k的m元树，最多需要添加m(mk-1)=mk片树叶。因此，高度h=k时，至多有mk片树叶，结论成立。推论推论若一个高度为h的m元树T有l片树叶，则

。证明

根据定理10.3.3，在高度为h的m元树中，树叶数l

mh，取以m为底的对数，得

，因为h是整数，所以有当m

元树的所有树叶的高度都是h时，等号成立，即

例题例：t名选手参加象棋淘汰赛，每一场比赛的失败者退出比赛，剩下的胜利者继续比赛，直到剩下最后一名胜利者就是比赛的冠军。假设比赛没有平局，问共需进行多少场比赛才能决出冠军？解

在淘汰赛中，每一场比赛的失败者退出比赛，剩下的胜利者继续比赛，直到剩下最后一名胜利者就是比赛的冠军。因此可以用二元正则树来表示比赛过程。这棵树有t片树叶，每个分支点对应一场比赛，根结点对应冠军赛。假设分支点有i个，根据定理10.3.2，有i=t−1，所以共需进行t−1场比赛才能决出冠军。有序根树定义10.3.6如果将根树每一层上的结点都规定次序，这样的根树称为有序根树。

在有序根树中，每一层上的结点按从左到右的次序排序。如二元有序树的一个分支点有两个子结点，则从左到右称这两个子结点为左儿子和右儿子。以这两个子结点为根所产生的根子树分别称为左子树和右子树。有序根树

有序根树

左子树

右子树

3910.3.2有序根树的遍历

系统地访问有序根树的每个结点，使得每个结点恰好访问一次，进行数据存取的过程称为遍历算法。三种遍历2元有序根树的算法：①前序遍历算法:树根、前序遍历左子树、前序遍历右子树②中序遍历算法:中序遍历左子树、树根、中序遍历右子树③后序遍历算法:后序遍历左子树、后序遍历右子树、树根例题例40中序遍历:前序遍历:后序遍历:b

a((f

d

g)c

e)a

b(c(d

f

g)e)b((f

g

d)e

c)a带下划线的是(子)树根,一对括号内是一棵子树例题例写出用三种遍历算法遍历下列二元树的结果。41前序遍历:hdibjea

f

kcga

b

d

hie

jcfkghidjebkf

gca(1)(2)(3)(4)(5)(6)(8)(9)(7)(10)(11)中序遍历:(1)(2)(3)(4)(5)(6)(8)(9)(7)(10)(11)(1)(3)(2)(6)(4)(5)(8)(7)(11)(10)(9)后序遍历:2元有序根树用2元有序根树表示算术运算算式如下:将运算符放在分支点上,数放在树叶上,每个运算符对它所在分支点的2棵子树进行运算,并规定左子树是被除数或被减数.42例2

右图表示算式((b+(c+d))

a)

((e

f)

(g+h)

(i

j))前序遍历

b+c

d

a

e

f

+g

h

i

j后序遍历b

c

d++a

e

f

g

h+i

j

需要注意的是，结点的中序遍历结果可存在二义性为了让这样的表达式无歧义，遇到运算时，按中序遍历算法得到的表达式要包含括号，括号中是子树的表达式。波兰符号法与逆波兰符号法(续)波兰符号法(前缀符号法):按前序遍历访问,不加括号.从右到左进行,每个运算符对其后面紧邻两个数进行运算.逆波兰符号法(后缀符号法):按后序遍历访问,不加括号.从左到右进行,每个运算符对前面紧邻两数运算.43例2(续)波兰符号法逆波兰符号法

b+c

d

a

e

f

+g

h

i

j

b

c

d++a

e

f

g

h+i

j

例题例

用2元有序树表示命题公式：

（p

q）

（p

q），写出它的波兰记法和逆波兰记法。解

由底向上构造二元有序树。首先构造p

q，p和

q的子树，然后构造

（p

q），p

q的子树，最后用这两个子树分别作为左子树和右子树，以

为根结点的二元有序树就是所求的表示命题公式：

（p

q）

（p

q）的有序树。前序遍历得波兰记法：

pq

p

q后序遍历得逆波兰记法：pq

pq

10.4根树的应用10.4.1前缀码10.4.2最优二元树和Huffman编码10.4.3决策树10.4.1前缀码定义10.4.1设

=a1a2a3

an为长度为n的符号串，称a1，a1a2，

，a1a2a3

an-1分别为符号串

的长度为1，2，

，n-1的前缀；设B={

1，

2，

，

m}为一个字符串集合，若对任意的

i，

j

B，i

j，

i，

j互不为前缀，则称B为前缀码；若

i（i=1，2，，m）中只有0，1两个符号，则称B为二元前缀码。例如，{0，10，110，111}，{a,b,ca,cb,eda}都是二元前缀码，而{1，01，010，110}不是前缀码。前缀码和二元树定理10.4.1任何一棵二元树的树叶可对应一个前缀码。证明

对于给定的一棵二元树，每个分支点至少有一个子结点，至多有两个子结点。若分支点有两个子结点，在分支点和左子结点连接的边上标0，和右子结点连接的边上标1；若分支点只有1个子结点，在分支点和它的子结点连接的边上标0或1都可以。

这样，每片树叶将对应一个由0和1组成的序列，该序列由树根到这片树叶的通路上各边的标记组成。由于每片树叶对应的标记序列都不是另一片树叶标记序列的前缀，因而由所有树叶的标记序列构成一个前缀码。例题

例前缀码{00,11,011,0100}前缀码和二元树定理10.4.2任何一个前缀码都对应一棵二元树。证明

设给定一个前缀码，h表示前缀码中最长序列的长度。画出一棵高度为h的二元正则树，在分支点和子结点连接的两条边上分别标记0和1；

对长度不超过h的每一个二进制序列必对应这棵二元树上的一个结点。将对应于前缀码的每一个结点的所有后代结点及其关联的边都删去；最后再删去没有和任一前缀码对应的树叶，得到一棵二元树；这棵二元树的树叶就对应给定的前缀码。例题例1画出前缀码{00,10,010,111,1101}对应的二元树。解：画出一棵高度为h的二元正则树，在分支点和子结点连接的两条边上分别标记0和1；000000111110100011101011000111例题例1画出前缀码{00,10,010,111,1101}对应的二元树。解：画出一棵高度为h的二元正则树，在分支点和子结点连接的两条边上分别标记0和1；

标记每一个前缀码在这棵二元树上对应的一个结点。将对应于前缀码的每一个结点的所有后代结点及其关联的边都删去；删去没有和任一前缀码对应的树叶，得到前缀码对应的二元树；000000111110100011101101000111000101011011115210.4.2最优二元树和Huffman编码定义10.4.2设2元树T有t片树叶v1,v2,…,vt,树叶的权分别为w1,w2,…,wt,称为T的权,记作W(T),其中l(vi)是vi的层数.在所有有t片树叶,带权w1,w2,…,wt的2元树中,权最小的2元树称为最优2元树例如134561345613456W(T1)=47W(T2)=54W(T3)=4353求最优2元树的算法哈夫曼(Huffman)算法1）给定t个权值w1、w2

、

…、wt

，构造t个结点分别对应t个权值；