1、閩南師范大學(xué) 計(jì)算機(jī)學(xué)院第十六章 樹第十六章 樹無向樹及其性質(zhì)生成樹根樹及其應(yīng)用知 識 點(diǎn)：無向樹、生成樹、最小生成樹、Kruskal算法 根樹、二叉樹、Huffman算法、二元前綴碼 。教學(xué)要求：深刻理解和掌握本章的基本概念。教學(xué)重點(diǎn)：無向樹和根樹的定義及其性質(zhì)。學(xué)時: 416.1 無向樹及其性質(zhì)定義16.1 連通無回路的無向圖稱為無向樹,簡稱樹每個連通分支都是樹的無向稱為森林平凡圖稱為平凡樹 在無向樹中,懸掛頂點(diǎn)稱為樹葉.度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)16.1 無向樹及其性質(zhì)定理16.1 設(shè)G=是n階m邊的無向圖, 下列幾個命題是等價的 : G是樹 G中任意兩個頂點(diǎn)之間存在唯一的路徑 G

2、中無回路, 且 m = n 1 G是連通的, 且 m = n 1 G是連通的且任何邊都是橋 G中沒有回路, 但任意兩個不同的頂點(diǎn)之間加一條新邊后所得圖中有唯一的一個含新邊的圈證明的方法: 16.1 無向樹及其性質(zhì)定理16.2 設(shè)T是n階非平凡的無向樹,則T中至少有兩片樹葉 證 設(shè)T有x片樹葉,由握手定理及定理16.1 可知 2(n-1)=d(v1)+d(v2)+d(vn)x+2(n-x) 由上式解得 x216.1 無向樹及其性質(zhì)例16.1 畫出所有6階非同構(gòu)的無向樹例16.2 畫出所有有3片樹葉、1個3度頂點(diǎn)、其余頂點(diǎn)度數(shù)不等于1和3的7階非同構(gòu)的無向樹16.2 生成樹定義16.2 如果無向圖

3、G的生成子圖T是樹,則稱T是G的生成樹設(shè)T是生成樹,G的在T中的邊稱為T的樹枝設(shè)T是生成樹,G的不在T中的邊稱為T的弦稱T的所有弦的導(dǎo)出子圖為T的余樹,記為 T定理16.3 無向圖G有生成樹當(dāng)且僅當(dāng)G是連通圖16.2 生成樹應(yīng)用破圈法求連通圖的生成樹推論 設(shè)G為n階m邊的無向連通圖,則 mn-1定理16.4 設(shè)T為無向連通圖G中的一棵生成樹,e為T的任意一條弦,則Te中含G中只含一條弦e其余邊均為樹枝的圈,而且不同的弦對應(yīng)的圈也不同16.2 生成樹定義16.3 設(shè)T是n階m條邊的無向連通圖G的一棵生成樹。 設(shè)e1,e2,em-n+1為T的弦,Cr(r=1,m-n+1) 為T添加弦er產(chǎn)生的G中

4、由弦er和樹枝構(gòu)成的圈稱Cr為G的對應(yīng)弦er的基本回路或基本圈 稱C1,C2,Cm-n+1為G對應(yīng)T的基本回路系統(tǒng) 稱 m-n+1 為G的圈秩,記作(G)16.2 生成樹定理16.5 設(shè)T是連通圖G的一棵生成樹,e為T的樹枝,則G 中存在只含樹枝e,其余邊都是弦的割集,且不同 的樹枝對應(yīng)的割集也不同定義16.4 設(shè)T是n階連通圖G的一棵生成樹,e1,e2,en-1 為T的樹枝,Si(i=1,2,n-1)是由樹枝ei和弦構(gòu)成 的割集,則稱Si為G的對應(yīng)樹枝ei的基本割集 稱S1,S2,Sn-1對G對應(yīng)T的基本割集系統(tǒng)稱n-1為G的割集秩,記作(G)16.2 生成樹定義16.5 設(shè)無向連通帶權(quán)圖G

5、=,T是G 的一棵生成樹,T的各邊權(quán)之和稱為T的 權(quán),記作W(T).G的所有生成樹中權(quán)最小的生成樹稱為G的最小生成樹142351132131116.2 生成樹求最小生成樹的避圈法(Kruskal算法)設(shè)n階無向連通帶權(quán)圖G=有m條邊,不妨設(shè)G中沒有環(huán),將m條邊按權(quán)從小到大順序排列,設(shè)為 e1,e2,em取e1在T中,然后檢查e2,e3,em,若ej(j2)與已在T中的邊不能構(gòu)成回路,則取ej在T中,否則棄去ej算法停止時得到的T為G的最小生成樹142351132131116.2 生成樹例16.4 數(shù)據(jù)分析中的單鏈聚類 設(shè)有一組離散數(shù)據(jù) D=a1,a2,an 在D上定義了一個相似度函數(shù)d. 對于

6、任何兩個數(shù)據(jù) ai,ajD,ai與aj 的相似度函數(shù)的值為 d(i,j),通常取 0d(i,j)1 , 并且d具有對稱性質(zhì), 即 d(i,j)=d(j,i). 給定正整數(shù) k(1kn) ,D的一個k聚類是D的一個k劃分 =C1,C2,Ck, D(Cs,Ct) = min d(i,j) | aiCs,ajCt k聚類= C1,C2,Ck 的最小間隔 D()= min D(Cs,Ct) | Cs,Ct1ijk 16.2 生成樹如何使最小間隔達(dá)到最大值的k聚類例 D=a1,a2,a3,a4,a5,D中元素的相似度如下圖所示,k=2,求1243531332a1a3a4aa2a1a3a4aa211216

7、.3 根樹及其應(yīng)用定義16.6 若有向圖的基圖是無向樹 則稱這個有向圖為有向樹一個頂點(diǎn)入度為0, 其余的頂點(diǎn)的入度為1的有向樹稱為根樹入度為0的頂點(diǎn)稱為樹根,入度為1出度為0的頂點(diǎn)稱為樹葉, 入度為1出度不為0的頂點(diǎn)稱為內(nèi)點(diǎn),內(nèi)點(diǎn)和樹根統(tǒng)稱為分支點(diǎn)如從樹根到任意頂點(diǎn)v的路徑長度(即路徑中的邊數(shù))稱為v的層數(shù)。所有頂點(diǎn)的最大層數(shù)稱為樹的樹高去掉各邊上的箭頭16.3 根樹及其應(yīng)用定義16.7 設(shè)T為一根非平凡的根樹,vi,vjV(T)若vi可達(dá)vj,則稱vi為vj的祖先,vj為vi的后代若vi鄰接到vj(即E(T),則稱vi為vj的父親,而vj為vi的兒子若vj,vk的父親相同,則稱vi與vk是兄

8、弟設(shè)T為根樹,若將T中層數(shù)相同的頂點(diǎn)都標(biāo)定次序,則稱T為有序樹16.3 根樹及其應(yīng)用根據(jù)根樹T中每個分支點(diǎn)兒子數(shù)以及是否有序,可分類如下若T的每個分支點(diǎn)至多有r個兒子,則稱T為r叉樹 又若r叉樹是有序的,則稱它是r叉有序樹若T的每個分支點(diǎn)都恰好有r個兒子,則稱T為r叉正則樹 又若r叉樹是有序的,則稱它是r叉正則有序樹若T是r叉正則樹,且每個樹葉的層數(shù)均為樹高,則稱T為r叉完全正則樹;又若T是有序的,則稱它為r叉完全正則有序樹定義16.8 設(shè)T為一棵根樹,稱v及其后代的導(dǎo)出子圖 Tv為T的以v為根的根子樹2叉正則有序樹的每個分支點(diǎn)的兩個兒子導(dǎo)出的根子樹分別稱為該分支點(diǎn)的左子樹和右子樹16.3 根

9、樹及其應(yīng)用16.3 根樹及其應(yīng)用定義16.9 設(shè)2叉樹T有t片樹葉t1,t2 ,ts權(quán)分別為 w1,w2 ,wt 稱 為T的權(quán) 其中l(wèi)(vi)是vi的層數(shù)在所有有t片樹葉,帶權(quán)w1,w2 ,wt的 2叉樹中,權(quán)最小的稱為最優(yōu)二叉樹例 給定權(quán)序列 10,20,30,40 W(T1)=3*10+3*20+2*30+40=190 W(T2)=2*10+2*20+2*30+2*40=200 10 20 30 40T2T1 10 20 30 4016.3 根樹及其應(yīng)用霍夫曼(Huffman)算法給定實(shí)數(shù)w1,w2 ,wt , 作t片樹葉,分別以為w1,w2 ,wt權(quán)在所有入度為0的頂點(diǎn)(不一定是樹葉)中

10、選兩個權(quán)最小的頂點(diǎn),添加一個新分支點(diǎn),它以這2個頂點(diǎn)為兒子,其權(quán)等于這2個兒子的權(quán)之和重復(fù)上一步直到只有1個入度為0的頂點(diǎn)為止W(T)為分枝點(diǎn)的權(quán)之和16.3 根樹及其應(yīng)用例:給定一組權(quán)1,3,4,5,5,6,9, 求對應(yīng)的最優(yōu)二叉樹 解：權(quán)序列的演變過程為: 1, 3, 4, 5, 5, 6, 9 4, 4, 5, 5, 6, 9 5, 5, 6, 8, 9 6, 8, 9, 10 9, 10, 14 14, 19 33831445510(c)341(a)31445510 6 148(d )31448 6 145510199(e)4483(b)1W(T)=4*(1+3)+3*(4+5+5)+

11、2*(6+9)=8831448 6 14551019( f )93316.3 根樹及其應(yīng)用設(shè)a1a2an-1an為長為n的符號串，稱其子串 a1 , a1a2 , a1a2an-1 分別為該符號串的長度為1,2,n-1的前綴前綴碼是非等長的編碼。若符號串 bi(i=1,2,m)中只出現(xiàn)0,1 兩個符號,則稱A為二元前綴碼 abc，acb，abda，dc，ba, cba, cad 16.3 根樹及其應(yīng)用例31，00，011，0101，01001為前綴碼 而 1，00，011，0100，01000不是前綴碼 因?yàn)?100既是01000的前綴可用2叉樹產(chǎn)生二元前綴碼 , 如右圖所示 由這棵二叉樹可產(chǎn)

12、生前綴碼 1 , 00 , 010 , 011 1 1 0110 0000 1 1 01016.3 根樹及其應(yīng)用在僅含有A,B,C,D,E,F,G,H這8個字母的信息通信中, 它們出現(xiàn)的頻率如下： A：25% B：20% C：15% D：10% E：10% F：10% G： 5% H： 5% 求傳輸它們的最佳前綴碼，并求傳輸長度為10n(n2)個字母的信息,字母按上述比例出現(xiàn)，需要多少個二進(jìn)制數(shù)字？ 若使用等長的（長為3）的碼字傳輸需要多少個二進(jìn)制數(shù)字？解: 即以100乘各頻率為權(quán)， 并將權(quán)由大到小排列， 得 w1=5,w2=5,w3=10,w4=10, w5=10,w6=15,w7=20,w

13、8=25 用Huffman算法求最優(yōu)二叉樹 16.3 根樹及其應(yīng)用8個碼字的集合 01，11，001，101，1000，1001，0000，0001 為前綴碼，而且是最佳前綴碼 從題設(shè)可知,用 11傳A ,01傳B ,101傳C ,001傳D 1000傳E ,1001傳F , 0000傳G , 0001傳H 由于 W(T)=4*(5+5+10+10)+3*(10+15)+2*(20+25)=285 所以傳輸長度為10n(n2)個字母的信息需要 285/100*10n=2.8510n 個比特(bit)使用等長的（長為3）的碼字傳輸需要 310n 個比特(bit) 例如用 000傳A ,001傳B

14、 ,010傳C ,011傳D 100傳E ,101傳F , 110傳G , 111傳H 16.3 根樹及其應(yīng)用以上述前綴碼進(jìn)行信息通信的編碼和解碼過程例如傳輸字符串 ABGHCDEABAFBAEDCABGAABEC編碼A B G H C D E A B A F B A E D C A B G A 11 01 0000 0001 101 001 1000 11 01 11 1001 01 11 1000 001 101 11 01 0000 11傳輸和接收比特流 11解碼 自左至右掃描下述比特流并與編碼表對照11 01 0000 0001 101 001 1000 11 01 11 1001 0

15、1 11 1000 001 101 11 01 0000 11A B G H C D E A B A F B A E D C A B G A 編碼表： 11-A , 01-B , 101-C , 001-D 1000-E ,1001-F , 0000-G , 0001-H16.3 根樹及其應(yīng)用2叉樹的周游及其應(yīng)用 對于一棵根樹的每個頂點(diǎn)都訪問一次且僅一次稱為行遍或周游一棵樹2叉有序正則樹的三種周游方式中序行遍法: 訪問的次序?yàn)?左子樹樹根右子樹前序行遍法: 訪問的次序?yàn)?樹根左子樹右子樹后序行遍法: 訪問的次序?yàn)?左子樹右子樹樹根例 如右圖所示的叉樹的三種周游結(jié)果如下: ( ( h d i ) b e) a ( f c g ) a ( b ( d h i ) e ) ( c f g ) ( ( h i d ) e b ) ( f g c ) a a de ibcgfh16.3 根樹及其應(yīng)用例16.8 (1) 用2叉有序正則樹表示下面算式: (a*(b+c)+d*e*f)(g+(hi)*j) (2)用3種行遍法訪問這棵2叉樹,寫出訪問結(jié)果解 (1) 如右圖所