《离散数学特殊图课件.ppt》由会员分享，可在线阅读，更多相关《离散数学特殊图课件.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第8 8章章 特殊图特殊图 树树第第8 8章章 特殊图特殊图 .1.1 无向树及生成树无向树及生成树定义定义 9.1 9.1 连通无回路的无向图称为连通无回路的无向图称为无向树无向树,简称简称树树,常用常用T T表示树。表示树。(即即树是不包含回路的连通图树是不包含回路的连通图)平凡图称为平凡树。平凡图称为平凡树。若无向图若无向图G G至少有两个连通分支至少有两个连通分支,则称则称G G为森林。为森林。在无向树中，悬挂顶点称为树叶，度数大于或在无向树中，悬挂顶点称为树叶，度数大于或等于等于2 2的顶点称为分支点。的顶点称为分支点。第第8 8章章 特殊图特殊图 例例 9.1 9.1 判断下列哪
2、些图是树？判断下列哪些图是树？v1v2v3v4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解解:图图(a)是树是树,因为它连通又不包含回路。图因为它连通又不包含回路。图(b),(c)不是树不是树,因为图因为图(b)虽连通但有回路虽连通但有回路,图图(c)虽无回路但不连通。虽无回路但不连通。在图在图(a)中中,v1、v4、v5为均为叶，为均为叶，v2、v3均为均为分支节点。分支节点。第第8 8章章 特殊图特殊图 例例 9.2 9.2 连通图、树和森林之间的相互转换。连通图、树和森林之间的相互转换。第第8 8章章 特殊图特殊图 定理定理 9.1 9.1 设设G=G=,则下面各命题
3、是等价的：则下面各命题是等价的：（1 1）G G连通而不含回路（连通而不含回路（G G是树）。是树）。（2 2）G G中每对顶点之间存在唯一的路径。中每对顶点之间存在唯一的路径。（3 3）G G中无回路且中无回路且 n=m+1n=m+1。（4 4）G G是连通的且是连通的且 n=m+1n=m+1。(5)(5)G G中没有回路，但在任何两个不同的顶点中没有回路，但在任何两个不同的顶点 之间加一条新边，在所得的图中得到唯之间加一条新边，在所得的图中得到唯 一的一个含新边的圈。一的一个含新边的圈。(6)G(6)G是连通的且是连通的且G G中任何边均为桥。中任何边均为桥。(7)G(7)G是连通的是连通
4、的,但删除任何一条边后，就不但删除任何一条边后，就不 连通了。连通了。其中其中n n为为G G中顶点数，中顶点数，m m为边数。为边数。第第8 8章章 特殊图特殊图 以上两个定理给出了无向树的主要性质，以上两个定理给出了无向树的主要性质，利用这些性质和握手定理，可以画出阶数利用这些性质和握手定理，可以画出阶数n n比比较小的所有非同构的无向树。较小的所有非同构的无向树。定理定理9.29.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T中中 至少有两片树叶。至少有两片树叶。证证:因为因为T是非平凡树是非平凡树,所以所以T中每个顶点的度数中每个顶点的度数都大于等于都大于等于1,设设T有有
5、k片树叶片树叶,则有则有(n-k)个顶个顶点度数大于等于点度数大于等于2,由握手定理及定理由握手定理及定理9.1可知可知 2m=d(vi)k+2(n-k)由定理由定理9.19.1可知可知,m=n-1,m=n-1,将此结果代入上式后将此结果代入上式后解得解得 k 2.第第8 8章章 特殊图特殊图 例例9.39.3：画出：画出5阶所有非同构的无向树。阶所有非同构的无向树。解：设解：设Ti为为5阶无向树阶无向树,则则Ti的边数为的边数为4，Ti的的度序列之和为度序列之和为8，(Ti)4,(Ti)11,可可能的度序列为：能的度序列为：(1)1,1,1,1,4 (2)1,1,1,2,3 (3)1,1,2
6、,2,2 。称只有一个分支点且其度称只有一个分支点且其度数为数为n-1的的n阶无向树为阶无向树为星星形图形图，称唯一的分支点为，称唯一的分支点为星心星心。第第8 8章章 特殊图特殊图 解：由握手定理解：由握手定理 2m=d(vi)及定理及定理9.1 n=m+1n=m+1 设设G有有n个顶点个顶点,则有下列关系式则有下列关系式 5 x 1+3 x 2+(n-5-3)x 3=2 x(n-1)解得：解得：n=11 例例9.39.3：无向树：无向树G有有5片树叶，片树叶，3个个2度分支点，度分支点，其余分支点均为其余分支点均为3度，问度，问G有多少个顶点？有多少个顶点？第第8 8章章 特殊图特殊图 解
7、：由握手定理解：由握手定理 2m=d(vi)及定理及定理9.1 n=m+1n=m+1 设设G有有t个个1顶点顶点,则有下列关系式则有下列关系式 2 x 2+3+4 x 3+t=2 m =2 x(n-1)=2 x(2+1+3+t-1)解得：解得：t=9 例例9.49.4：无向树：无向树G有有2个个2度结点，度结点，1个个3度结点，度结点，3个个4度结点，则其度结点，则其1度结点数为多少？度结点数为多少？第第8 8章章 特殊图特殊图 解：设解：设G有有t个个4度分支点度分支点,则有下列关系式则有下列关系式 8 x 1+2 x 3+t x 4=2 x(8+2+t-1)解得：解得：t=2 则则G中共有
8、中共有12个顶点，个顶点，11条边，度数序列之条边，度数序列之 和为和为22，(Ti)=)=4,(Ti)=)=1 1,度序列为：度序列为：1,1,1,1,1,1,1,1,3,3,4,4 其非同构的图形为：其非同构的图形为：n例例 9.5：无向树：无向树G有有8片树叶，片树叶，2个个3度分支点，度分支点，其余分支点均为其余分支点均为4度，问度，问G有多少个有多少个4度分支点度分支点？画出其非同构的情况。？画出其非同构的情况。第第8 8章章 特殊图特殊图 。其非同构的图形为：其非同构的图形为：第第8 8章章 特殊图特殊图 图中，红色边表示图中，红色边表示生成树，白色边组生成树，白色边组成其余树。可
9、见，成其余树。可见，余树可能不连通，余树可能不连通，也可能含回路。也可能含回路。定义定义9.29.2 设设T是无向图是无向图G的的生成子图生成子图并且并且为树为树，则称，则称T为为G的的生成树生成树。G在在T中的边称为中的边称为T的的树枝树枝，G不在不在T中的边中的边称为称为T的的弦弦。T的所有的所有弦的集合的导出子图称为弦的集合的导出子图称为T的余树的余树第第8 8章章 特殊图特殊图 在下图中，在下图中，(2)为为(1)的一棵生成树的一棵生成树T，(3)为为T的余树，的余树，注意：余树不一定是树。注意：余树不一定是树。一个无向连通图，如果它本身不是树，它的一个无向连通图，如果它本身不是树，它
10、的生成树是不唯一的。但所有的连通图都具有生成生成树是不唯一的。但所有的连通图都具有生成树。事实上，若树。事实上，若G是连通图，又是连通图，又G中无回路，则中无回路，则G本身就是树。本身就是树。abcdeabcdeabcd(1)(2)(3)第第8 8章章 特殊图特殊图 定理定理9.39.3 无向图无向图G具有生成树具有生成树 G是连通图。是连通图。推论推论1 1 设设G是是n阶阶m条边的无向连通图，条边的无向连通图，则则m n-1。推论推论2 2 设设G是是n阶阶m条边的无向连通图，条边的无向连通图，T为为G 的生成树，则的生成树，则T的余树的余树T中含有中含有 m-n+1边边(即即T有有m-n
11、+1条弦条弦)。第第8 8章章 特殊图特殊图 定义定义9.39.3 设设T是是n阶阶m条边的无向连通图条边的无向连通图G的一棵生的一棵生成树，设成树，设e1,e2,em-n+1为为T的弦，设的弦，设Cr为为T添加弦添加弦er产生的产生的G的回路，的回路，r=1,2,m-n+1。则称则称Cr为对应于弦为对应于弦er的的基本回路，基本回路，称称C1,C2,Cm-n+1为对应生成数为对应生成数T的的基本回路系统基本回路系统，abcdef 在右图中在右图中,Ca=aed,Cb=dbf,Cc=cef,为对应生成树为对应生成树T的基本回路，的基本回路，Ca,Cb,Cc为为T的基本回路系统。的基本回路系统。
12、一个连通图一个连通图G对应不同的生成树的对应不同的生成树的基本回路及基本回路系统可能不同，基本回路及基本回路系统可能不同，但基本回路的个数但基本回路的个数G所固有的所固有的参数参数(弦弦)，等于，等于m-n+1第第8 8章章 特殊图特殊图 定义定义 9.4 9.4 设设T是是n阶连通图阶连通图G的一棵生成树的一棵生成树,称称T的的n-1个树枝对应的个树枝对应的G的的n-1个割集（每个割集只含一个割集（每个割集只含一个树枝，其余的边都是弦）个树枝，其余的边都是弦）S1,S2,Sn-1为对为对应生成树应生成树T的的G的的基本割集基本割集,称称S1,S2,Sn-1为对应生成树为对应生成树T的的基本割
13、集系统。基本割集系统。abcdef 在右图中在右图中,T的树枝的树枝d对应对应G的一的一个割集个割集d,b,a,e对应对应一个割集一个割集e,a,c,树枝树枝f对应对应一个割集一个割集f,c,b。3个树枝对应的个树枝对应的G的的割集的特点割集的特点是：每个割集中只含一个树枝，其余是：每个割集中只含一个树枝，其余的边都是的边都是弦。这样的弦。这样的割集称为基本割割集称为基本割集。集。第第8 8章章 特殊图特殊图 例例9.5 9.5 在右下图所示的图在右下图所示的图G G中中,实数边所构成的实数边所构成的子图是子图是G G的一棵生成树的一棵生成树T T，求求T T对应的基本回路对应的基本回路和基本
14、回路系统，基本割集和基本割集系统和基本回路系统，基本割集和基本割集系统解解:G G中顶点数中顶点数n=6,n=6,边数边数m=9m=9，基本回路个数为基本回路个数为m-n+1=4,m-n+1=4,即即T T有有4 4条条弦，弦，f,g,h,i。对应每条弦有对应每条弦有一个基本回路：一个基本回路：Cf=face;Cr=gba;Ch=hdcb;Ci=ied;基本回路系统为基本回路系统为 Cf,Cr,Ch,Ci abcdefghiT有有5个树枝个树枝a,b,c,d,e,因而有因而有5个个基本割集基本割集:Sa=a,g,f ;Sb=b,g,h ;Sc=c,f,h ;Sd=d,i,h ;Se=e,f,i
15、 基本基本割集系统为割集系统为Sa,Sb,Sc,Sd,Se第第8 8章章 特殊图特殊图 定义定义9.59.5 设无向连通带权图设无向连通带权图G=,T是是G的一的一棵生成树，棵生成树，T的各边权之和称为的各边权之和称为T的的权权，记作，记作W(T)。G的所有生成树中权最小的生成树称为的所有生成树中权最小的生成树称为G的的最小生成树最小生成树。求求最小生成树最小生成树的算法很多，我们只介绍避圈的算法很多，我们只介绍避圈法（法（Kruskal算法）算法）第第8 8章章 特殊图特殊图 设设n阶无向连通带权图阶无向连通带权图G=有有m条条边边,不妨设不妨设G中无环中无环(否则可先删去否则可先删去)，算
16、法为：，算法为：(1)将将m条边按权从小到大顺序排列，设为条边按权从小到大顺序排列，设为(2)e1,e2,em。(2)取取e1在在T中，然后依次检查中，然后依次检查e2,em，若若ej (j=2,3,m)与与T中的边不能构成回路，则中的边不能构成回路，则取取ej在在T中，否则放弃中，否则放弃ej，考虑下一条边，直考虑下一条边，直至至jm。(3)算法停止时得到的算法停止时得到的T为为G的最小生成树。的最小生成树。KruskalKruskal算法算法 一种求最小生成树的算法一种求最小生成树的算法第第8 8章章 特殊图特殊图 例例9.6 9.6 用避圈法求下图所示的最小生成树用避圈法求下图所示的最小
17、生成树abcdef5555136642解解:W(T)=1+2+3+4+5 =15注意：最小生成树的结最小生成树的结点数与原图相等，点数与原图相等，边的数目比原图边的数目比原图少。少。第第8 8章章 特殊图特殊图 bacd762fe81443472356321hg避圈法避圈法 Kruskal(克鲁斯卡尔算法克鲁斯卡尔算法)例例9.79.7：铺设一个连接各个城市的光纤通信网络铺设一个连接各个城市的光纤通信网络第第8 8章章 特殊图特殊图 febacd546036388404820452815383062251210hg例例9.8：铺设一个连接各个城市的光纤铺设一个连接各个城市的光纤通信网络。通信网
18、络。（单位：万元）（单位：万元）第第8 8章章 特殊图特殊图 2 21 12 21 13 34 43 31 15 51 11 13 31 1。OK!例例9.99.9：用用Kruskal算法求下图算法求下图的最小生成树的最小生成树。第第8 8章章 特殊图特殊图 。2 21 14 45 51 15 55 54 45 53 33 32 2例例9.109.10：用用Kruskal算法求下图的最小生成树算法求下图的最小生成树。2 21 14 45 51 15 55 54 45 53 33 32 2W(T)=1+1+2+3+2+5 =14W(T)=1+1+2+3+2+5 =14第第8 8章章 特殊图特殊图
19、 破圈法破圈法l上述算法是贪婪地增加不构成回路的边，上述算法是贪婪地增加不构成回路的边，以求得最小生成树以求得最小生成树(最优树最优树)，所以通常称，所以通常称为为“避圈法避圈法”；l我们还可以从另一个角度来考虑最小成树我们还可以从另一个角度来考虑最小成树(最优树最优树)问题，由问题，由G G的圈（回路）最优条件，的圈（回路）最优条件，我们也可以在原连通权图我们也可以在原连通权图G中逐步删除构中逐步删除构成回路中成回路中权最大的边，权最大的边，最后剩下的无回路最后剩下的无回路的生成子图为最小成树的生成子图为最小成树(最优树最优树)。我们把。我们把这种方法称为这种方法称为“破圈法破圈法”。第第8
20、 8章章 特殊图特殊图 例例 9.11 在图在图(a)中给出了一个连通图中给出了一个连通图,求此图的生求此图的生 成树成树(a)第第8 8章章 特殊图特殊图 214356787864例例9.129.12 用用“破圈法破圈法”求其最优树求其最优树的过程。的过程。第第8 8章章 特殊图特殊图 设设D是有向图是有向图,如果略去有向边的方向所得如果略去有向边的方向所得无无向图为一棵无向树向图为一棵无向树,则称则称D为为有向树有向树。其中根树最。其中根树最为重要。为重要。定义定义 9.6 9.6 v设设T是是n(n 2)阶有向树，若阶有向树，若T中有一个顶点的中有一个顶点的入度为入度为0，其余的顶点的入
21、度均为，其余的顶点的入度均为1，则称，则称T为为根树根树，v入度为入度为0的顶点称为的顶点称为树根树根，v入度为入度为1出度为出度为0的顶点称为的顶点称为树叶树叶，v入度为入度为1出度不为出度不为0的顶点称为的顶点称为内点内点，内点和树，内点和树根统称为根统称为分支点分支点，9.2 9.2 根树及其应用根树及其应用第第8 8章章 特殊图特殊图 (1)(2)v0v1v2v3v4v5v6v7v0v1v2v3v4v5v6v7例例 9.13 下图下图(1)为一棵根树。为一棵根树。V0为树根为树根,v1,v4,v3,v6,v7为树叶为树叶,v2,v5为内点为内点,v0,v2,v5为均为分为均为分支点支点
22、,由于在根树中有向边的方向均一致由于在根树中有向边的方向均一致,故可故可省掉其方向省掉其方向,如图如图(2)第第8 8章章 特殊图特殊图 (1)(2)v0v1v2v3v4v5v6v7v0v1v2v3v4v5v6v7v从树根到从树根到T的任意顶点的任意顶点v的通路（路径）长度的通路（路径）长度称为称为v的的层数层数，v层数最大顶点的层数称为层数最大顶点的层数称为树高树高v平凡树也称为根树。平凡树也称为根树。v例例 9.14 下图下图(1)中中,v1,v2,v3,在第一层上，在第一层上，v4,v5 在第二层上，在第二层上，v6,v7在第三层上。树高为在第三层上。树高为3。第第8 8章章 特殊图特殊
23、图 定义定义9.79.7 设设T为一棵根树，为一棵根树，a为为T中的一个顶点，中的一个顶点，且且a不是树根，称不是树根，称a及其后代导出的子图及其后代导出的子图T为为 T的以的以a为根的子树，简称根子树。为根的子树，简称根子树。如图所示，由于各有如图所示，由于各有向边的方向一致，故向边的方向一致，故常省略，并且树根在常省略，并且树根在最上方最上方。a第第8 8章章 特殊图特殊图 定义定义9.8 设设T为根树，若将为根树，若将T中层数相同的中层数相同的 顶点都标定次序，则称顶点都标定次序，则称T为为有序树有序树 根据根树根据根树T中每个分支点儿子数以及中每个分支点儿子数以及是否有序，可以将根树分
24、成下列各类；是否有序，可以将根树分成下列各类；定义定义9.9 设设T为一棵根树为一棵根树 若若T的每个分支点至的每个分支点至多多有有r个儿子个儿子,则称则称 T为为 r 元树元树(r叉树叉树)；若若T的每个分支点都恰好有的每个分支点都恰好有r个儿子个儿子,则则 称它为称它为 r 元正则树元正则树。第第8 8章章 特殊图特殊图 若若r元树元树T是有序的是有序的,则称则称T为为r元有序树元有序树 若若r元正则树元正则树T是有序的，则称是有序的，则称T为为r元正元正 则有序树。则有序树。若若T是是r元正则树，且所有树叶的层数相元正则树，且所有树叶的层数相 同，则称同，则称T为为r元完全正则树元完全正
25、则树 若若r元完全正则树元完全正则树T是有序树，则称是有序树，则称T是是 r元有序完全正则树。元有序完全正则树。第第8 8章章 特殊图特殊图 。二元二元(叉叉)树树二元二元(叉叉)正则正则树树二元二元(叉叉)完全正则树完全正则树 在所有的在所有的r元有序正则树中，元有序正则树中，2 元有序元有序正则树最重要。正则树最重要。例例 9.15第第8 8章章 特殊图特殊图 例例9.16：求求2元树元树T的权。的权。3 32 23 33 35 5解解:W(T)=32+22+33 +53+3 2=40是不是最优是不是最优2元树呢？元树呢？定义定义9.99.9 设设2元树元树T有有t片树叶，片树叶，v1,v
26、2,vt,权权分别为分别为w1,w2,wt，称称 W(t)=为为T的的权权，其中，其中L(vi)是是vi的层数，在所有有的层数，在所有有t片树叶，带权片树叶，带权w1,w2,wt的的2元树中，权最元树中，权最小的小的2元树称为元树称为最优最优2元树元树。第第8 8章章 特殊图特殊图 例例:9.17:9.17 在下图所示的三棵树中在下图所示的三棵树中,都是带权都是带权1,3,4,1,3,4,5,6 5,6的二元树的二元树,W(TW(T1 1)=47,W(T)=47,W(T2 2)=54,)=54,W(T W(T3 3)=42,)=42,但它们中有无但它们中有无最优最优2元树元树 还不知道还不知道
27、T T1 1T T2 2T T3 34 4 5 51 16 63 33 34 45 56 61 11 13 36 64 45 5第第8 8章章 特殊图特殊图 用此算法求上例的最优二叉树。用此算法求上例的最优二叉树。给定实数给定实数w1,w2,wt,且且w1 w2 wt（1）连接权为连接权为w1,w2的两片树叶的两片树叶,得一个分支点得一个分支点 其权为其权为w1+w2。（2）在在w1+w2,w3,wt中选出两个最小的权中选出两个最小的权,连接它们对应的顶点连接它们对应的顶点(不一定是树叶不一定是树叶),得得新新 分支点及所带的权。分支点及所带的权。（3）重复）重复(2),直到形成直到形成t-1
28、个分支点个分支点,t片树叶片树叶 为止。为止。HuffmanHuffman算法算法 一种求最优二叉树的算法一种求最优二叉树的算法第第8 8章章 特殊图特殊图 例例:9.18:9.18 求求带权带权1,3,4,5,61,3,4,5,6的最优二元树。的最优二元树。4 44 48 81 13 33 38 84 43 31 11 13 34 45 56 64 44 411115 56 61 14 48 811111919 连接权为连接权为w1,w2的两片树叶的两片树叶,得一个分支点其权为得一个分支点其权为w1+w2 在在w1+w2,w3,wt中选出两个最小的权中选出两个最小的权,连接它们对应的顶点连接
29、它们对应的顶点(不一定是树叶不一定是树叶),得得 分支点及所带的权分支点及所带的权 重复重复,直到形成直到形成t-1个分支点个分支点,t片树叶为止片树叶为止(若得到的权比后续的两若得到的权比后续的两个权大个权大,则另开分支则另开分支)第第8 8章章 特殊图特殊图 。4 43 37 7(1)(2)(3)(4)例例:9.19:9.19 求求带权带权 3,4,5,6,12 3,4,5,6,12的最优二元树。的最优二元树。解：共分为四个步骤：解：共分为四个步骤：34756116543711183456711181230第第8 8章章 特殊图特殊图 例例:9.20:9.20 求求带权带权 2,4,7,8
30、,10,12 2,4,7,8,10,12的最优二元树。的最优二元树。第第8 8章章 特殊图特殊图 第第8 8章章 特殊图特殊图 这棵最优树的权为这棵最优树的权为:2*4+4*4+7*3+12*2+8*2+10*2=105一般来说一般来说,带权带权w1,w2,wn的最优树不一定是唯一的的最优树不一定是唯一的第第8 8章章 特殊图特殊图 最优二叉树在通信编码中的应用最优二叉树在通信编码中的应用定义定义9.119.11 设设=1 2 n-1 n为长为为长为n的符号串的符号串,称其子串称其子串 1,1 2,1 2 n-1 分别为该符号串的长度为分别为该符号串的长度为1,2,n-1的的前缀前缀,设设B=
31、1,2,m 为一个符号串集合为一个符号串集合,若对于任意的若对于任意的i,j B,i j,i,j 互不为前缀互不为前缀,则称则称B为为前缀码前缀码,若符号串中若符号串中i(i=1,2,m)只出现只出现0,1两两个符号个符号,则称则称B为为二元前缀码二元前缀码。第第8 8章章 特殊图特殊图 那么：那么：00,01,100,1010,1011,11111 abc,cba,bca,bac,acb,cab 1,00,011,01001,01000 是是(二元二元)前缀码吗？前缀码吗？如何产生如何产生二元前缀二元前缀码呢？码呢？如：如：0,10,110,1111 1,01,001,0001 等是等是(二
32、元二元)前缀码前缀码而而 1,11,101,001,0011 不是不是(二元二元)前缀码前缀码第第8 8章章 特殊图特殊图 给定一棵给定一棵2叉树叉树T，设它有设它有t片树叶。设片树叶。设v为为T的一个分支点，则的一个分支点，则v至少有一个儿子，最多至少有一个儿子，最多有两个儿子。若有两个儿子。若v有两个儿子，在由有两个儿子，在由v引出的两引出的两条边上，左边的标上条边上，左边的标上0，右边的标上，右边的标上1；若；若v有有一个儿子，在由一个儿子，在由v引出的边上可标上引出的边上可标上0，也可标，也可标上上1。设。设vi为为T的任一片树叶，从树根到的任一片树叶，从树根到vi的通的通路上各边的标
33、号组成的路上各边的标号组成的0，1串组成的符号串放串组成的符号串放在在vi处，处，t片树叶处的片树叶处的t个符号串组成的集合为个符号串组成的集合为一个一个二元前缀码。二元前缀码。用二叉树产生二元前缀码之做法用二叉树产生二元前缀码之做法第第8 8章章 特殊图特殊图 由上面做法知，由上面做法知，vi处的符号串的前缀均在处的符号串的前缀均在vi所在的通路上除所在的通路上除vi外的顶点处达到，因而所得外的顶点处达到，因而所得符号串集合为二元前缀码。符号串集合为二元前缀码。若若T存在单子分支点，则由存在单子分支点，则由T产生的前缀码产生的前缀码可能不唯一。可能不唯一。若若T为正则为正则2叉树叉树,则由则
34、由T产生的前缀码唯一产生的前缀码唯一010110101000100010101111例例9.21 右图所示的二元树右图所示的二元树产生的前缀吗为产生的前缀吗为11,00,011,0100,0101第第8 8章章 特殊图特殊图 由一棵给定的由一棵给定的2叉正则树，可以产生唯一的一叉正则树，可以产生唯一的一个二元前缀码。个二元前缀码。01000111 例例9.22 右图所示的是一棵右图所示的是一棵2叉正则树叉正则树,它产生它产生唯一的一个二元前缀码唯一的一个二元前缀码是是000,001,01,10,11。第第8 8章章 特殊图特殊图 提示提示 把各字符看作为树叶把各字符看作为树叶,各字符出现的频率
35、各字符出现的频率(或或n倍的频率倍的频率)作为其相应的权作为其相应的权,利用利用Huffman算法求出最优算法求出最优2叉树叉树,由此产生的前缀码即为由此产生的前缀码即为最最佳前缀码佳前缀码。利用利用Huffman算法求出的最优算法求出的最优2叉树产生的叉树产生的前缀码称为前缀码称为最佳前缀码最佳前缀码。例例9.23 在通信中在通信中,0,1,2,3,4,5,6,7出现的频率如下出现的频率如下 0：30,1：20,2：15 3：10,4：10,5：5 6：5,7：5 求传输它们的求传输它们的最佳前缀码最佳前缀码第第8 8章章 特殊图特殊图 例例9.24 在通信中在通信中,0,1,2,3,4,5
36、,6,7出现的频率如下出现的频率如下 0：30,1：20,2：15 3：10,4：10,5：5 6：5,7：5 求传输它们的求传输它们的最佳前缀码最佳前缀码100604030302020151510555010101010101101001000000000100010011001011101解解:将将各字符出现的频率作各字符出现的频率作为其相应的权为其相应的权 1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30为为8个权个权,利用利用Huffman算法求出的算法求出的最优最优2叉树如图所示叉树如图所示(码长取码长取3,如如101传传5)第第8 8章章 特殊图特殊图 例例
37、9.24 在通信中在通信中,0,1,2,3,4,5,6,7出现的频率如下出现的频率如下0:30,1:20,2:15,3:10,4:10 5:5,6:5,7:5求传输它们的求传输它们的最佳前缀最佳前缀码码100604030302020151510555010101010101101001000000000100010011001011101图中方框中的图中方框中的8个码子是个码子是最佳前缀最佳前缀码。树码。树T T是带权是带权 1,2,8的最的最优二元树。带权为优二元树。带权为 i的树叶的树叶vi对应的码子传输出现频率对应的码子传输出现频率为为 i,的数字，即的数字，即11传传1,101传传40
38、1传传0,0001传传5 001传传2,101传传4 11传传1,00001传传6 100传传3,00000传传7第第8 8章章 特殊图特殊图 对于一棵根树的每个顶点都访问一次且对于一棵根树的每个顶点都访问一次且仅一次称为仅一次称为行遍行遍或或周游周游一棵树。一棵树。对于对于2叉有序正则树主要有以下三种周游方式：叉有序正则树主要有以下三种周游方式：v 中序行遍法中序行遍法，访问的次序为：左子树，树根，访问的次序为：左子树，树根，右子树。右子树。v 前序行遍法前序行遍法，访问的次序为：树根，左子树，访问的次序为：树根，左子树，右子树。右子树。v 后序行遍法后序行遍法，访问的次序为：左子树，右子，
39、访问的次序为：左子树，右子树，树根。树，树根。二叉树的周游及应用二叉树的周游及应用第第8 8章章 特殊图特殊图 例例9.25 试用三种周游方式行遍下图试用三种周游方式行遍下图。+-a a。b bc ce ef fg gh hi id dj j第第8 8章章 特殊图特殊图 例例9.25 试用三种周游方式行遍下图试用三种周游方式行遍下图。+-a a。b bc ce ef fg gh hi id dj j中序行遍法中序行遍法访问的次序为：访问的次序为：左子树，树根，左子树，树根，右子树。右子树。(a(b+c)+def)(g+(h-i)j)中序行遍法中序行遍法访问此树：访问此树：第第8 8章章 特殊图
40、特殊图 例例9.25 试用三种周游方式行遍下图试用三种周游方式行遍下图。+-a a。b bc ce ef fg gh hi id dj j前序行遍法前序行遍法访问的次序为：树根，访问的次序为：树根，左子树，右子树。左子树，右子树。前序行遍法前序行遍法访问此树：访问此树：(+(a(+b c)d(e f)+g(-h i j)特点：运算符在参特点：运算符在参加运算的两个数之加运算的两个数之前，每个运算符与前，每个运算符与它后面紧邻的两个它后面紧邻的两个数进行运算。数进行运算。第第8 8章章 特殊图特殊图 例例9.25 试用三种周游方式行遍下图试用三种周游方式行遍下图。+-a a。b bc ce ef fg gh hi id dj j后序行遍法后序行遍法访问的次序为：左子访问的次序为：左子树，右子树，树根树，右子树，树根a b c+de f+g h i-j+特点：运算符在参特点：运算符在参加运算的两个数之加运算的两个数之后，每个运算符与后，每个运算符与它前面紧邻的两个它前面紧邻的两个数进行运算。数进行运算。后序行遍法后序行遍法访问此树：访问此树：第第8 8章章 特殊图特殊图 结结 束束 语语 本课程到此结束本课程到此结束感谢同学们的参与配合！感谢同学们的参与配合！