8枚枚硬硬币币问问题题】若若有有8枚枚硬硬币币a，b，c，d，e，f，g，h，其其中中7枚枚重重量量相相等等，只只有有1枚枚稍稍轻轻现现要要求求以以天天平平为为工工具具，最最少少的的比较几次可以挑出轻币来？比较几次可以挑出轻币来？4/15/20241第九章 树J定义9.1 连通而不含回路的无向图称为无向树,简称树,常用T表示树.J连通分支数大于等于2,且每个连通分支均是树的非连通无向图称为森林.J平凡图称为平凡树.J设T为一棵无向树,vV,若d(v)1,则称v为T的树叶.若d(v)2,则称v为T的分支点.9.1无向树及生成树无向树及生成树4/15/20243图中（a），（b）为树，而（c）不是树，但（c）为森林a）（b）（c）?例4/15/20244判断下列哪些图是树？v1v2v3v4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解:图(a)是树,因为它连通又不包含回路图(b),(c)不是树,因为图(b)虽连通但有回路,图(c)虽无回路但不连通在图(a)中,v1、v4、v5为均为叶，v2、v3均为分支节点例题4/15/20245连通图、树和森林之间的相互转换例4/15/20246定理9.1 设G,则下面各命题是等价的:(1)G连通而不含回路;(2)G的每对顶点之间具有唯一的一条路径;(3)G是连通的且nm+1;(4)G中无回路且nm+1;(5)G中无回路,但在G中任两个不相邻的顶点之间 增加一条边,就形成唯一的一条初级回路;(6)G是连通的且G中每条边都是桥;(7)G是连通的,但删除任何一条边后,就不连通了.其中n为G中顶点数,m为边数.4/15/20247定理9.2 设T是n阶非平凡的树,则T中至少有2片树叶.证明：设树T有x片树叶，树T中所有结点的度数之和 等于边数的2倍。
在树T中边数等于结点数减1，即n1所以2(n1)=另一方面，树中的分支点为n-x个，每个分支点的度数大于等于2，所有分支点度数之和大于等于2(nx)，从而下式成立：2(n-1)=x+2(n-x)解之，得 x24/15/20248画出5阶所有非同构的无向树解：设Ti为5阶无向树,则Ti的边数为4，Ti的度序列之和为8，(Ti)4,(Ti)1,可能的度序列为：(1)1,1,1,1,4 (2)1,1,1,2,3 (3)1,1,2,2,2称只有一个分支点且其度数为称只有一个分支点且其度数为n-1的的n阶无向树为阶无向树为星形图星形图，称，称唯一的分支点为唯一的分支点为星心星心例题4/15/20249定义9.2 设G是无向连通图,T是G的生成子图,并且T是树,则称T是G的生成树.G在T中的边称为T的树枝,G不在T中的边称为T的弦.T的所有弦的集合的导出子图称为T的余树.图(b)，(c)为图(a)的两棵生成树例（a）（b）（c）4/15/202410(2)为(1)的一棵生成树T,(3)为T的余树.?例（1）（2）（3）余树可能不连通，也可能含回路4/15/202411定理9.3 任何连通图G至少存在一棵生成树.推论1 设n阶无向连通图G有m条边,则 mn-1.推论2 设n阶无向连通图G有m条边,T是G的生成树,T是T的余树,则T中有m-n+1条边.（1）（2）（3）m=8,n=54/15/202412图中,初级回路aed，bdf，cef.这3个回路中每一个回路都只含一条弦,其余的边都是树枝,这样的回路称为基本回路基本回路.abcdef4/15/202413定义9.3 设T是n阶连通图G=的一棵生成树,G有n条边.设e1,e2,em-n+1为T的弦,设Cr是T加弦er产生的G的回路,r=1,2,m-n+1.称Cr为对应于弦er的基本回路,称C1,C2,Cm-n+1为对应生成树T的基本回路系统.在右图中,Ca=aed,Cb=dbf,Cc=cef,为对应生成树T的基本回路，Ca,Cb,Cc为T的基本回路系统。
一个连通图G对应不同的生成树的基本回路及基本回路系统可能不同，但基本回路的个数等于m-n+1.abcdef4/15/202414J定义9.4 设T是n阶连通图G=的一棵生成树,称T的n-1个树枝对应的G的n-1个割集(每个割集只含一个树枝,其余的边都是弦)S1,S2,Sn-1为对应生成树T的G的基本割集,称S1,S2,Sn-1为对应生成树T的基本割集系统.对一个n阶连通图G来说,基本割集的个数必为n-1个,这是G的固有特性.4/15/202415在右下图所示的图G中,实边所构成的子图是G的一棵生成树T，求T对应的基本回路和基本回路系统，基本割集和基本割集系统解:G中顶点数n=6,边数m=9，基本回路个数为m-n+1=4,即T有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.基本割集系统为Sa,Sb,Sc,Sd,Se.?例题例题4/15/202416定义9.5 设无向连通带权图G=,T是G的一棵生成树.T各边带权之和称为T的权,记作W(T).G的所有生成树中带权最小的生成树称为最小生成树.问题的提出：问题的提出：要在要在 n 个城市间建立通信联络个城市间建立通信联络网。
网顶点顶点：表示城市，表示城市，权：权：城市间通信线路的城市间通信线路的花费代价希望此通信网花费代价最小花费代价希望此通信网花费代价最小4/15/202417问题分析：答案只能从生成树中找，因为要做到任何两个城市之间有线路可达，通信网必须是连通的；但对长度最小的要求可以知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连通性，但总代价显然减少了，这与总代价最小的假设是矛盾的结论：希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 最小代价生成树4/15/202418Kruskal算法(避圈法)设n阶无向连通带权图G=中有m条边e1,e2,em,它们带的权分别为a1,a2,am,不妨设a1a2am.(1)取e1在T中(e1非环,若e1为环,则弃e1)；(2)若e2不与e1构成回路,取e2在T中,否则弃e2,再查e3,继续这一过程,直到形成生成树T为止.用以上算法生成的T是最小生成树.4/15/202419用避圈法求下图所示的最小生成树.abcdef5555136642解:?例题例题W(T)=1+2+3+4+5=154/15/202420febacd546036388404820452815383062251210hg铺设一个连接各个城市的光纤通信网络。
单位：万元）?例题例题4/15/202421V1V6V5V4V3V26513566425算法思想：算法思想：设设 N=(V,E)是连通网，是连通网，TE 是是 N 上最小生成树中上最小生成树中边的集合边的集合初始令初始令 U=u0,(u0 V),TE=在所有在所有 u U,v V-U 的边的边(u,v)E 中，中，找一条代价最小的边找一条代价最小的边(u0,v0)将将(u0,v0)并入集合并入集合 TE，同时同时 v0 并入并入 U重复上述操作直至重复上述操作直至 U=V 为止，则为止，则 T=(V,TE)为为 N 的最小生成树的最小生成树V1V3V6V4V2V5构造最小生成树的另一方法：普里姆(Prim)算法 4/15/202422 设D是有向图,如果略去有向边的方向所得无向图为一棵无向树,则称D为有向树定义 9.6 设T是n(n 2)阶有向树，若T中有一个顶点的入度为0，其余的顶点的入度均为1，则称T为根树v入度为0的顶点称为树根，v入度为1出度为0的顶点称为树叶，v入度为1出度不为0的顶点称为内点，内点和树根统称为分支点9.2根树及其应用根树及其应用4/15/202423(1)(2)v0v1v2v3v4v5v6v7下图(1)为一棵根树。
v0为树根,v1,v4,v3,v6,v7为树叶,v2,v5为内点,v0,v2,v5为均为分支点,由于在根树中有向边的方向均一致,故可省掉其方向,如图(2)v0v1v2v3v4v5v6v74/15/202424v从树根到T的任意顶点v的通路（路径）长度称为v的层数层数，记为l(v).层数最大顶点的层数称为树高树高，记为h(T)v0v1v2v3v4v5v6v7左图中,v1,v2,v3,在第一层上，v4,v5在第二层上，v6,v7在第三层上树高为34/15/202425家族树一棵根树可以看成一棵家族树：(1)若顶点a邻接到顶点b，则称b为a的儿子，a为b的父亲；(2)若b，c同为a的儿子，则称b，c为兄弟；(3)若ad，而a可达d，则称a为d的祖先，d为a的后代v0v1v2v3v4v5v6v74/15/202426定义9.7 设T为一棵根树，a为T中的一个顶点，且a不是树根，称a及其后代导出的子图T为T的以a为根的子树，简称根子树定义9.8 设T为根树，若将T中层数相同的 顶点都标定次序，则称T为有序树4/15/202427定义9.9 设T为一棵根树：（1）若T的每个分支点至多有r个儿子，则称T为r元树（r叉树）；（2）若T的每个分支点都恰好有r个儿子，则称T为r元正则树；（3）若r元树T是有序的，则称T是r元有序树；根树分成下列各类根树分成下列各类4/15/202428（4）若r元正则树T是有序的，则称T是r元有序正则树；（5)若T是r元正则树，且所有树叶的层数相同，都等于树高，则称T为r元完全正则树；（6）若r元完全正则树T是有序树，则称T是r元有序完全正则树。
4/15/202429图（1）为2元有序树，图（2）为2元有序正则树，图（3）为2元有序完全正则树112121 21212121212（1）（2）（3）4/15/202430定义9.10 设2元树T有t片树叶,分别带权为w1,w2,wi,wt(wi为实数,i1,2,t,)称为T的权,其中L(wi)为带权wi的树叶vi的层数.在所有的带权w1,w2,wt的2元树中,带权最小的2元树称为最优2元树.4/15/202431在下图所示的三棵树中,都是带权1,3,4,5,6的二元树,W(T1)=47，W(T2)=54，W(T3)=42T234561 115463T154631T34/15/202432n给定实数w1,w2,wt,且w1w2wt.n (1)连接w1,w2为权的两片树叶,得一分支点,其权为w1w2;n (2)在w1w2,w3,wt中选出两个最小的权,连接它们对应的顶点(不一定都是树叶),得分支点及所带的权;n (3)重复(2),直到形成t1个分支点,t片树叶为止.HuffmanHuffman算法算法 一种求最优二叉树的算法一种求最优二叉树的算法4/15/202433【例】求带权2，2，3，3，5的最优二叉树T。
最优树的权为：W(T)=2323523232=344/15/202434最优二叉树在通信编码中的应用定义9.11 设=12 n-1n为长为n的符号串,称其子串 1,12,12 n-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为二元前缀码二元前缀码4/15/202435如何产生如何产生二元前缀二元前缀码呢？码呢？如：0,10,110,1111 1,01,001,0001 等是(二元)前缀码而 1,11,101,001,0011 不是(二元)前缀码4/15/202436由二元树产生二元前缀码由二元树产生二元前缀码010110101000100010101111【例】右图所示的二元树产生的前缀吗为11,00,011,0100,01014/15/202437 由一棵给定的2元正则树，可以产生唯一的一个二元前缀码例】右图所示的是一棵2元正则树,它产生唯一的一个二元前缀码是000,001,01,10,11010110014/15/202438提示把各字符看作为树叶,各字符出现的频率(或n倍的频率)作为其相应的权,利用Huffman算法求出最优2元树,由此产生的前缀码即为最佳前缀码。
利用Huffman算法求出的最优2元树产生的前缀码称为最佳前缀码4/15/202439【解】将各字符出现的频率作为其相应的权1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30为8个权,利用Huffman算法求出的最优2叉树如图所示(码长取3,如101传5)【例题】在通信中,0,1,2,3,4,5,6,7出现的频率如下 0：30,1：20,2：15 3：10,4：10,5：5 6：5,7：5 求传输它们的最佳前缀码.1303051055011004020010101011000000000010001001100101116020151501001014/15/202440由于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个码子是最佳前缀码树T是带权1,2,8的最优二元树带权为i的树叶vi对应的码子传输出现频率为i,的数字，即11传1,101传401传0,0001传5 001传2,00001传6 100传3,00000传71303051055011004020010101011000000000010001001100101116020151501001014/15/202441 对于一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树。
对于2叉有序正则树主要有以下三种周游方式：v 中序行遍法 访问的次序为：左子树，树根，右子树v 前序行遍法 访问的次序为：树根，左子树，右子树v 后序行遍法 访问的次序为：左子树，右子树，树根二元树的周游及应用4/15/202442【例例】试用三种周游方式行遍下图试用三种周游方式行遍下图中序行遍中序行遍:(a+(bc)d+e)(fg)+a ab bc cg gd df fe e4/15/202443【例例】试用三种周游方式行遍下图试用三种周游方式行遍下图a ab bc cg gd df fe e前序行遍前序行遍:(+(+a(bc)d)e)(fg)波兰符号法波兰符号法:+abcdefg4/15/202444【例例】试用三种周游方式行遍下图试用三种周游方式行遍下图后序行遍后序行遍:(a(bc)+)d)e+)(fg)+a ab bc cg gd df fe e逆波兰符号法逆波兰符号法:abc+de+fg4/15/202445。
