離散數(shù)學(xué)-專(zhuān)題7：樹(shù)

1、1第七章第七章 樹(shù)樹(shù)主要內(nèi)容主要內(nèi)容l 無(wú)向樹(shù)及其性質(zhì)無(wú)向樹(shù)及其性質(zhì)l 生成樹(shù)生成樹(shù)l 根樹(shù)及其應(yīng)用根樹(shù)及其應(yīng)用 27.1 無(wú)向樹(shù)及其性質(zhì)無(wú)向樹(shù)及其性質(zhì)定義定義7.1 (1) 無(wú)向樹(shù)無(wú)向樹(shù)連通無(wú)回路的無(wú)向圖連通無(wú)回路的無(wú)向圖(2) 平凡樹(shù)平凡樹(shù)平凡圖平凡圖(3) 森林森林至少由兩個(gè)連通分支（每個(gè)都是樹(shù)）組成至少由兩個(gè)連通分支（每個(gè)都是樹(shù)）組成(4) 樹(shù)葉樹(shù)葉1度頂點(diǎn)度頂點(diǎn)(5) 分支點(diǎn)分支點(diǎn)度數(shù)度數(shù) 2的頂點(diǎn)的頂點(diǎn) 3無(wú)向樹(shù)的等價(jià)定義無(wú)向樹(shù)的等價(jià)定義定理定理7.1 設(shè)設(shè)G=是是n階階m條邊的無(wú)向圖，則下面各命題條邊的無(wú)向圖，則下面各命題是等價(jià)的：是等價(jià)的：(1) G 是樹(shù)是樹(shù)(2) G 中任意

2、兩個(gè)頂點(diǎn)之間存在惟一的路徑中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑.(3) G 中無(wú)回路且中無(wú)回路且 m=n 1. (4) G 是連通的且是連通的且 m=n 1.(5) G 是連通的且是連通的且 G 中任何邊均為橋中任何邊均為橋.(6) G 中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到惟一的一個(gè)含新邊的圈邊，在所得圖中得到惟一的一個(gè)含新邊的圈. 42022-6-9定理定理7.1證明證明(1)(2)證明證明: (1)(2)(3)(4)(5)(6)(1)(1) G是樹(shù)是樹(shù)(連通無(wú)回連通無(wú)回)(2) G中任何中任何2頂點(diǎn)之間有唯一路徑頂點(diǎn)之間

3、有唯一路徑(1)(2): u,v V, G連通連通, u,v之間的短程線(xiàn)是路徑之間的短程線(xiàn)是路徑. 如果如果u,v之間的路徑不唯一之間的路徑不唯一, 則則G中有回路中有回路, 矛盾矛盾!52022-6-9定理定理7.1證明證明(2)(3) (2) G中任何中任何2頂點(diǎn)之間有唯一路徑頂點(diǎn)之間有唯一路徑 (3) G無(wú)圈無(wú)圈 m=n-1證明證明(續(xù)續(xù)): (2)(3): 任任2點(diǎn)之間有唯一路徑點(diǎn)之間有唯一路徑無(wú)圈無(wú)圈(反反證證: 有圈有圈存在存在2點(diǎn)點(diǎn),它們之間有它們之間有2條路徑條路徑.) m=n-1(歸納法歸納法): n=1時(shí)時(shí),m=0. 設(shè)設(shè)n k時(shí)成立時(shí)成立, 當(dāng)當(dāng)n=k+1時(shí)時(shí), 任選任選

4、1邊邊e, G-e有有2個(gè)連通分支個(gè)連通分支, m=m1+m2+1=(n1-1)+(n2-1)+1=n1+n2-1 =n-1. m1=n1-1m2=n2-1e62022-6-9定理定理7.1證明證明(3)(4) (3) G無(wú)圈無(wú)圈 m=n-1 (4) G連通連通 m=n-1證明證明(續(xù)續(xù)): (3)(4): G連通連通: 假設(shè)假設(shè)G有有s個(gè)連通分支個(gè)連通分支, 則每個(gè)連則每個(gè)連通分支都是樹(shù)通分支都是樹(shù), 所以所以m=m1+m2+ ms=(n1-1)+(n2-1)+(ns-1) =n1+n2+ns-s=n-s=n-1, 所以所以s=1.m1=n1-1m2=n2-1ms=ns-172022-6-9

5、定理定理7.1證明證明(4)(5) (4) G連通連通 m=n-1 (5) G極小連通極小連通: 連通連通 所有邊是橋所有邊是橋證明證明(續(xù)續(xù)): (4)(5): 所有邊是橋所有邊是橋: e E, G-e是是n階階(n-2)邊圖邊圖, 一定不連通一定不連通(連通連通m n-1), 所以所以e是割邊是割邊. m=n-1em=n-282022-6-9定理定理7.1證明證明(5)(6) (5) G極小連通極小連通: 連通連通 所有邊是橋所有邊是橋 (6) G極大無(wú)回極大無(wú)回: 無(wú)圈無(wú)圈 增加任何新邊得唯一圈增加任何新邊得唯一圈證明證明(續(xù)續(xù)): (5)(6): 所有邊是橋所有邊是橋無(wú)圈無(wú)圈. u,v

6、 V, G連通連通, u,v之間有唯一路徑之間有唯一路徑 , 則則(u,v)是唯一的圈是唯一的圈. 92022-6-9定理定理7.1證明證明(6)(1)(6) G極大無(wú)回極大無(wú)回: 無(wú)圈無(wú)圈 增加任何新邊得唯一圈增加任何新邊得唯一圈(1) G是樹(shù)是樹(shù)(連通無(wú)回連通無(wú)回)證明證明(續(xù)續(xù)): (6)(1): G連通連通: u,v V, G (u,v)有唯一的圈有唯一的圈C, C-(u,v)是是u,v之間的路徑之間的路徑. # 10)(2)()1(2xnxvdni 由上式解出由上式解出x 2. 定理定理7.2 設(shè)設(shè)T是是n階非平凡的無(wú)向樹(shù)，則階非平凡的無(wú)向樹(shù)，則T 中至少有兩片樹(shù)葉中至少有兩片樹(shù)葉.

7、 無(wú)向樹(shù)的性質(zhì)無(wú)向樹(shù)的性質(zhì)證證 設(shè)設(shè) T 有有 x 片樹(shù)葉，由握手定理可知，片樹(shù)葉，由握手定理可知，11例題例題例例1 已知無(wú)向樹(shù)已知無(wú)向樹(shù)T中有中有1個(gè)個(gè)3度頂點(diǎn)，度頂點(diǎn)，2個(gè)個(gè)2度頂點(diǎn)，其余頂點(diǎn)度頂點(diǎn)，其余頂點(diǎn)全是樹(shù)葉，試求樹(shù)葉數(shù)，并畫(huà)出滿(mǎn)足要求的非同構(gòu)的無(wú)向樹(shù)全是樹(shù)葉，試求樹(shù)葉數(shù)，并畫(huà)出滿(mǎn)足要求的非同構(gòu)的無(wú)向樹(shù). 解解 解本題用樹(shù)的性質(zhì)解本題用樹(shù)的性質(zhì)m=n 1，握手定理，握手定理. 設(shè)有設(shè)有x片樹(shù)葉，于是片樹(shù)葉，于是 n = 1+2+x = 3+x, 2m = 2(n 1) = 2 (2+x) = 1 3+2 2+x解出解出x = 3，故，故T有有3片樹(shù)葉片樹(shù)葉.T 的度數(shù)列應(yīng)為的度數(shù)

8、列應(yīng)為 1, 1, 1, 2, 2, 3，易知易知3度頂點(diǎn)與度頂點(diǎn)與1個(gè)個(gè)2度頂點(diǎn)相鄰度頂點(diǎn)相鄰與和與和2個(gè)個(gè)2度頂點(diǎn)均相鄰是非同度頂點(diǎn)均相鄰是非同構(gòu)的，因而有構(gòu)的，因而有2棵非同構(gòu)的無(wú)向棵非同構(gòu)的無(wú)向樹(shù)樹(shù)T1, T2，如圖所示，如圖所示. 12例例2 已知無(wú)向樹(shù)已知無(wú)向樹(shù)T有有5片樹(shù)葉，片樹(shù)葉，2度與度與3度頂點(diǎn)各度頂點(diǎn)各1個(gè)，其余頂個(gè)，其余頂點(diǎn)的度數(shù)均為點(diǎn)的度數(shù)均為4，求，求T的階數(shù)的階數(shù)n，并畫(huà)出滿(mǎn)足要求的所有非同，并畫(huà)出滿(mǎn)足要求的所有非同構(gòu)的無(wú)向樹(shù)構(gòu)的無(wú)向樹(shù). 例題例題解解 設(shè)設(shè)T的階數(shù)為的階數(shù)為n, 則邊數(shù)為則邊數(shù)為n 1，4度頂點(diǎn)的個(gè)數(shù)為度頂點(diǎn)的個(gè)數(shù)為n 7. 由握手定理得由握手定

9、理得 2m = 2(n 1) = 5 1+2 1+3 1+4(n 7)解出解出n = 8，4度頂點(diǎn)為度頂點(diǎn)為1個(gè)個(gè). 13T的度數(shù)列為的度數(shù)列為1, 1, 1, 1, 1, 2, 3, 4，共有，共有3棵非同構(gòu)的無(wú)向樹(shù)，棵非同構(gòu)的無(wú)向樹(shù)，如圖所示如圖所示.例題例題142022-6-9tn表表n tnntnntnntn119471748,62925104,636,890211010618123,86726279,793,450311123519317,95527751,065,460421255120823,065282,023,443,03253131,301212,144,505295,46

10、9,566,58566143,159225,623,7563014,830,871,802711157,7412314,828,0743140,330,829,0308231619,3202439,299,89732109,972,410,221152022-6-9無(wú)向樹(shù)的枚舉無(wú)向樹(shù)的枚舉(enumeration)畫(huà)出所有非同構(gòu)的畫(huà)出所有非同構(gòu)的n階無(wú)向樹(shù)階無(wú)向樹(shù)n=1: n=2: n=3: n=4:n=5: 162022-6-96階非同構(gòu)無(wú)向樹(shù)階非同構(gòu)無(wú)向樹(shù)n=6: t6=6 172022-6-97階非同構(gòu)無(wú)向樹(shù)階非同構(gòu)無(wú)向樹(shù)n=7: t7=11182022-6-98階非同構(gòu)無(wú)向樹(shù)階非同構(gòu)無(wú)

11、向樹(shù)n=8: t8=23192022-6-98階非同構(gòu)無(wú)向樹(shù)階非同構(gòu)無(wú)向樹(shù)(續(xù)續(xù))n=8: t8=23202022-6-98階非同構(gòu)無(wú)向樹(shù)階非同構(gòu)無(wú)向樹(shù)(解法解法2)n=8: 度數(shù)列有度數(shù)列有11種種:(1)1 1 1 1 1 1 1 1 7 (7)1 1 1 1 1 1 3 3 3(2)1 1 1 1 1 1 1 2 6 (8)5 1 1 1 1 2 2 3 3(3)1 1 1 1 1 1 1 3 5 (9)3 1 1 1 1 2 2 2 4(4)1 1 1 1 1 1 1 4 4 (10)4 1 1 1 2 2 2 2 3(5)2 1 1 1 1 1 2 2 5 (11)1 1 1 2 2

12、 2 2 2 2(6)3 1 1 1 1 1 2 3 4212022-6-98階非同構(gòu)無(wú)向樹(shù)階非同構(gòu)無(wú)向樹(shù)(解法解法2)n=8: 度數(shù)列有度數(shù)列有11種種:(8)5 1 1 1 1 2 2 3 3 (10)4 1 1 1 2 2 2 2 322不一定連通，也不一定不含回路T定義定義7.2 設(shè)設(shè)G為無(wú)向圖為無(wú)向圖(1) G的的樹(shù)樹(shù)T 是是G 的子圖并且是樹(shù)的子圖并且是樹(shù)(2) G的的生成樹(shù)生成樹(shù)T 是是G 的生成子圖并且是樹(shù)的生成子圖并且是樹(shù)(3) 生成樹(shù)生成樹(shù)T的的樹(shù)枝樹(shù)枝T 中的邊中的邊(4) 生成樹(shù)生成樹(shù)T的的弦弦不在不在T 中的邊中的邊(5) 生成樹(shù)生成樹(shù)T的的余樹(shù)余樹(shù) 全體弦組成的集合

13、的導(dǎo)出子圖全體弦組成的集合的導(dǎo)出子圖T7.2 生成樹(shù)生成樹(shù)232022-6-9定理定理7.3無(wú)向圖無(wú)向圖G連通連通 G有生成樹(shù)有生成樹(shù)證明證明: () 顯然顯然. () 破圈法破圈法. #24基本回路系統(tǒng)基本回路系統(tǒng)定理定理7.4 設(shè)設(shè)T為為G的生成樹(shù)，的生成樹(shù)，e為為T(mén)的任意一條弦，則的任意一條弦，則T e中中含一個(gè)只有一條弦其余邊均為含一個(gè)只有一條弦其余邊均為T(mén)的樹(shù)枝的圈的樹(shù)枝的圈. 不同的弦對(duì)應(yīng)的不同的弦對(duì)應(yīng)的圈也不同圈也不同. 證證 設(shè)設(shè)e=(u,v)，在，在T中中u到到v有惟一路徑有惟一路徑 ，則，則 e為所求的圈為所求的圈. 定義定義7.3 設(shè)設(shè)T是是n階階m條邊的無(wú)向連通圖條邊的

14、無(wú)向連通圖G的一棵生成樹(shù)，設(shè)的一棵生成樹(shù)，設(shè)e 1, e 2, , e m n+1為為T(mén) 的弦的弦. 設(shè)設(shè)Cr為為T(mén) 添加弦添加弦e r 產(chǎn)生的只含弦產(chǎn)生的只含弦e r、其余邊均為樹(shù)枝的圈、其余邊均為樹(shù)枝的圈. 稱(chēng)稱(chēng)Cr為為G的對(duì)應(yīng)樹(shù)的對(duì)應(yīng)樹(shù)T 的弦的弦e r的的基本基本回路回路或或基本圈基本圈，r=1, 2, , m n+1. 并稱(chēng)并稱(chēng)C1, C2, ,Cm n+1為為G對(duì)應(yīng)對(duì)應(yīng)T 的的基本回路系統(tǒng)基本回路系統(tǒng)，稱(chēng)，稱(chēng)m n+1為為G的的圈秩圈秩，記作，記作 (G). 25基本割集的存在基本割集的存在定理定理7.5 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹(shù)，的一棵生成樹(shù)，e為為T(mén)的樹(shù)枝，則的樹(shù)枝

15、，則G中存在只含樹(shù)枝中存在只含樹(shù)枝e，其余邊都是弦的割集，且不同的樹(shù)枝對(duì)，其余邊都是弦的割集，且不同的樹(shù)枝對(duì)應(yīng)的割集也不同應(yīng)的割集也不同.證證 由定理由定理7.1可知，可知，e是是T的橋，因而的橋，因而T e有兩個(gè)連通分支有兩個(gè)連通分支T1和和T2，令，令 Se=e | e E(G)且且 e 的兩個(gè)端點(diǎn)分別屬于的兩個(gè)端點(diǎn)分別屬于V(T1)和和V(T2)，由構(gòu)造顯然可知由構(gòu)造顯然可知Se為為G的割集，的割集，e Se且且Se中除中除e外都是弦，外都是弦，所以所以Se為所求為所求. 顯然不同的樹(shù)枝對(duì)應(yīng)的割集不同顯然不同的樹(shù)枝對(duì)應(yīng)的割集不同. 26定義定義7.4 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵

16、生成樹(shù)，的一棵生成樹(shù)，e 1, e 2, , e n 1為為T(mén) 的樹(shù)枝，的樹(shù)枝，Si是是G的只含樹(shù)枝的只含樹(shù)枝e i的割集，則稱(chēng)的割集，則稱(chēng)Si為為G的對(duì)應(yīng)的對(duì)應(yīng)于生成樹(shù)于生成樹(shù)T由樹(shù)枝由樹(shù)枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并稱(chēng)并稱(chēng)S1,S2, , Sn 1為為G 對(duì)應(yīng)對(duì)應(yīng)T 的的基本割集系統(tǒng)基本割集系統(tǒng)，稱(chēng)，稱(chēng)n 1為為G的的割割集秩集秩，記作，記作 (G). 基本割集與基本割集系統(tǒng)基本割集與基本割集系統(tǒng)27解解 弦弦e, f, g對(duì)應(yīng)的基本回路分別為對(duì)應(yīng)的基本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基基=Ce,

17、 Cf, Cg. 樹(shù)枝樹(shù)枝a, b, c, d對(duì)應(yīng)的基本割集分別為對(duì)應(yīng)的基本割集分別為 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S基基=Sa, Sb, Sc, Sd. 例例3 下圖實(shí)線(xiàn)邊所示為生成樹(shù)，求基本回路系統(tǒng)與下圖實(shí)線(xiàn)邊所示為生成樹(shù)，求基本回路系統(tǒng)與基本割集系統(tǒng)基本割集系統(tǒng)實(shí)例實(shí)例282022-6-9帶權(quán)圖帶權(quán)圖(weighted graph)G=, W: ER, W(e)稱(chēng)為稱(chēng)為e的的權(quán)權(quán)ABFECD510938 1445629最小生成樹(shù)最小生成樹(shù)定義定義7.5 T是是G=的生成樹(shù)的生成樹(shù)(1) W(T)T各邊權(quán)之和各邊權(quán)之和

18、(2) 最小生成樹(shù)最小生成樹(shù)G的所有生成樹(shù)中權(quán)最小的的所有生成樹(shù)中權(quán)最小的求最小生成樹(shù)的一個(gè)算法求最小生成樹(shù)的一個(gè)算法避圈法避圈法（Kruskal）設(shè)）設(shè)G=，將，將G中非環(huán)邊按權(quán)從小中非環(huán)邊按權(quán)從小到大排序：到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 查查e2，若，若e2與與e1不構(gòu)成回路，取不構(gòu)成回路，取e2也在也在T 中，否則棄中，否則棄e2.(3) 再查再查e3, 直到得到生成樹(shù)為止直到得到生成樹(shù)為止. 30例例4 求圖的一棵最小生成樹(shù)求圖的一棵最小生成樹(shù).所求最小生成樹(shù)如所求最小生成樹(shù)如圖所示，圖所示，W(T)=38.實(shí)例實(shí)例317.3 根根樹(shù)及其應(yīng)用樹(shù)及其

19、應(yīng)用定義定義7.6 T是有向樹(shù)（基圖為無(wú)向樹(shù)）是有向樹(shù)（基圖為無(wú)向樹(shù)）(1) T 為為根樹(shù)根樹(shù)T 中一個(gè)頂點(diǎn)入度為中一個(gè)頂點(diǎn)入度為0，其余的入度均為，其余的入度均為1.(2) 樹(shù)根樹(shù)根入度為入度為0的頂點(diǎn)的頂點(diǎn)(3) 樹(shù)葉樹(shù)葉入度為入度為1，出度為，出度為0的頂點(diǎn)的頂點(diǎn)(4) 內(nèi)點(diǎn)內(nèi)點(diǎn)入度為入度為1，出度不為，出度不為0的頂點(diǎn)的頂點(diǎn)(5) 分支點(diǎn)分支點(diǎn)樹(shù)根與內(nèi)點(diǎn)的總稱(chēng)樹(shù)根與內(nèi)點(diǎn)的總稱(chēng)(6) 頂點(diǎn)頂點(diǎn)v的的層數(shù)層數(shù)從樹(shù)根到從樹(shù)根到v的通路長(zhǎng)度的通路長(zhǎng)度(7) 樹(shù)高樹(shù)高T 中層數(shù)最大頂點(diǎn)的層數(shù)中層數(shù)最大頂點(diǎn)的層數(shù)32根根樹(shù)實(shí)例樹(shù)實(shí)例根樹(shù)的畫(huà)法根樹(shù)的畫(huà)法樹(shù)根放上方，省去所有有向邊上的箭頭樹(shù)根放上方，

20、省去所有有向邊上的箭頭33家族樹(shù)與根子樹(shù)家族樹(shù)與根子樹(shù)定義定義7.7 T 為非平凡根樹(shù)為非平凡根樹(shù)(1) 祖先與后代祖先與后代(2) 父親與兒子父親與兒子(3) 兄弟兄弟定義定義7.8 設(shè)設(shè)v為根樹(shù)為根樹(shù)T中任意一頂點(diǎn)，稱(chēng)中任意一頂點(diǎn)，稱(chēng)v及其后代的導(dǎo)出子及其后代的導(dǎo)出子圖為以圖為以v為根的為根的根子樹(shù)根子樹(shù).345 根樹(shù)的分類(lèi)根樹(shù)的分類(lèi)(1) T 為為有序根樹(shù)有序根樹(shù)同層上頂點(diǎn)標(biāo)定次序的根樹(shù)同層上頂點(diǎn)標(biāo)定次序的根樹(shù)(2) 分類(lèi)分類(lèi) r 叉樹(shù)叉樹(shù)每個(gè)分支點(diǎn)至多有每個(gè)分支點(diǎn)至多有r 個(gè)兒子個(gè)兒子 r 叉有序樹(shù)叉有序樹(shù)r 樹(shù)是有序的樹(shù)是有序的 r 叉正則樹(shù)叉正則樹(shù)每個(gè)分支點(diǎn)恰有每個(gè)分支點(diǎn)恰有r 個(gè)

21、兒子個(gè)兒子 r 叉正則有序樹(shù)叉正則有序樹(shù) r 叉完全正則樹(shù)叉完全正則樹(shù)樹(shù)葉層數(shù)相同的樹(shù)葉層數(shù)相同的r叉正則樹(shù)叉正則樹(shù) r 叉完全正則有序樹(shù)叉完全正則有序樹(shù)r叉正則樹(shù)的結(jié)論叉正則樹(shù)的結(jié)論定理定理 設(shè)有正則設(shè)有正則r叉樹(shù)，其樹(shù)葉數(shù)為叉樹(shù)，其樹(shù)葉數(shù)為t，分枝數(shù)為，分枝數(shù)為i，則，則(r-1)i=t-1證明證明 假設(shè)把假設(shè)把r叉樹(shù)當(dāng)作是每局有叉樹(shù)當(dāng)作是每局有r位選手參加比賽的單淘汰賽計(jì)位選手參加比賽的單淘汰賽計(jì)劃表，樹(shù)葉數(shù)為劃表，樹(shù)葉數(shù)為t表示參加比賽的選手?jǐn)?shù)表示參加比賽的選手?jǐn)?shù),分枝點(diǎn)數(shù)為分枝點(diǎn)數(shù)為i表示表示比賽的局?jǐn)?shù)比賽的局?jǐn)?shù) 因?yàn)槊烤直荣悓⑻蕴驗(yàn)槊烤直荣悓⑻蕴?r-1)位選手，比賽的結(jié)果共淘汰

22、位選手，比賽的結(jié)果共淘汰(r-1)i位選手，最后剩下一個(gè)冠軍，因此位選手，最后剩下一個(gè)冠軍，因此(m-1)i+1=t3536定義定義7.9 設(shè)設(shè)2叉樹(shù)叉樹(shù)T 有有t片樹(shù)葉片樹(shù)葉v1, v2, , vt，權(quán)分別為，權(quán)分別為w1, w2, , wt，稱(chēng)，稱(chēng) 為為T(mén) 的權(quán)，其中的權(quán)，其中l(wèi)(vi)是是vi 的層數(shù)的層數(shù). 在所在所有有有有t片樹(shù)葉，帶權(quán)片樹(shù)葉，帶權(quán)w1, w2, , wt 的的2叉樹(shù)中，權(quán)最小的叉樹(shù)中，權(quán)最小的2叉樹(shù)叉樹(shù)稱(chēng)為稱(chēng)為最優(yōu)最優(yōu)2叉樹(shù)叉樹(shù). )()(1itiivlwtW最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)求最優(yōu)樹(shù)的算法求最優(yōu)樹(shù)的算法 Huffman算法算法給定實(shí)數(shù)給定實(shí)數(shù)w1, w2, ,

23、wt，且，且w1 w2 wt. (1) 連接權(quán)為連接權(quán)為w1, w2的兩片樹(shù)葉，得一個(gè)分支點(diǎn)，其權(quán)為的兩片樹(shù)葉，得一個(gè)分支點(diǎn)，其權(quán)為w1+w2.(2) 在在w1+w2, w3, , wt 中選出兩個(gè)最小的權(quán)，連接它們對(duì)應(yīng)的中選出兩個(gè)最小的權(quán)，連接它們對(duì)應(yīng)的頂點(diǎn)頂點(diǎn)(不一定是樹(shù)葉不一定是樹(shù)葉)，得新分支點(diǎn)及所帶的權(quán)，得新分支點(diǎn)及所帶的權(quán). (3) 重復(fù)重復(fù)(2)，直到形成，直到形成 t 1個(gè)分支點(diǎn)，個(gè)分支點(diǎn)，t片樹(shù)葉為止片樹(shù)葉為止. 37例例 5 求帶權(quán)為求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹(shù)的最優(yōu)樹(shù). 解題過(guò)程由圖給出，解題過(guò)程由圖給出，W(T)=3838最佳前綴碼最佳前綴碼定義定義

24、7.10 設(shè)設(shè) 1, 2, , n-1, n是長(zhǎng)度為是長(zhǎng)度為 n 的符號(hào)串的符號(hào)串(1) 前綴前綴 1, 1 2, , 1 2 n 1 (2) 前綴碼前綴碼 1, 2, , m中任何兩個(gè)元素互不為前綴中任何兩個(gè)元素互不為前綴(3) 二元前綴碼二元前綴碼 i (i=1, 2, , m) 中只出現(xiàn)兩個(gè)符號(hào)，如中只出現(xiàn)兩個(gè)符號(hào)，如0與與1. 1，00，011，0101，01001，01000為前綴碼。而為前綴碼。而1，00，011，0101，0100，01001，01000不是前綴碼，不是前綴碼，因?yàn)橐驗(yàn)?100既是既是01001又是又是01000的前綴。的前綴。如何產(chǎn)生二元前綴碼？如何產(chǎn)生二元前綴

25、碼？定理定理7.6 一棵一棵2叉樹(shù)產(chǎn)生一個(gè)二元前綴碼叉樹(shù)產(chǎn)生一個(gè)二元前綴碼.推論推論 一棵正則一棵正則2叉樹(shù)產(chǎn)生惟一的前綴碼（按左子樹(shù)標(biāo)叉樹(shù)產(chǎn)生惟一的前綴碼（按左子樹(shù)標(biāo)0，右子樹(shù)標(biāo)右子樹(shù)標(biāo)1）39圖所示二叉樹(shù)產(chǎn)生的前綴碼為圖所示二叉樹(shù)產(chǎn)生的前綴碼為 00, 10, 11, 011, 0100, 0101 40用用Huffman算法產(chǎn)生最佳前綴碼算法產(chǎn)生最佳前綴碼例例6 在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下：在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求傳輸它們的最佳前綴碼，并求傳輸求傳輸它們的最佳前綴碼，并求傳輸

26、10n（n 2）個(gè)按上述比）個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的（長(zhǎng)為（長(zhǎng)為3）的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？）的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？41解解 用用100個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù)，即以個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù)，即以100乘各頻乘各頻率為權(quán)，并將各權(quán)由小到大排列，得率為權(quán)，并將各權(quán)由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此權(quán)產(chǎn)生的最優(yōu)樹(shù)如圖所示用此權(quán)產(chǎn)生的最優(yōu)樹(shù)如圖所示. 求最佳前綴碼求最佳前綴碼 01-0 11-

27、1 001-2 100-3 101-4 0001-500000-6 00001-7W(T)=285，傳傳10n(n 2)個(gè)個(gè)用二進(jìn)制數(shù)字需用二進(jìn)制數(shù)字需2.85 10n個(gè)個(gè)， 用等長(zhǎng)碼需用等長(zhǎng)碼需3 10n個(gè)數(shù)字個(gè)數(shù)字. 42波蘭符號(hào)法與逆波蘭符號(hào)法波蘭符號(hào)法與逆波蘭符號(hào)法行遍或行遍或周游根樹(shù)周游根樹(shù)T對(duì)對(duì)T的每個(gè)頂點(diǎn)訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次的每個(gè)頂點(diǎn)訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次. 對(duì)對(duì)2叉有序正則樹(shù)的周游方式：叉有序正則樹(shù)的周游方式： 中序行遍法中序行遍法次序?yàn)椋鹤笞訕?shù)、根、右子樹(shù)次序?yàn)椋鹤笞訕?shù)、根、右子樹(shù) 前序行遍法前序行遍法次序?yàn)椋焊?、左子?shù)、右子樹(shù)次序?yàn)椋焊⒆笞訕?shù)、右子樹(shù) 后序行遍法后序行遍法次序?yàn)椋鹤笞訕?shù)、右子樹(shù)、根次序?yàn)椋鹤笞訕?shù)、右子樹(shù)、根對(duì)圖所示根樹(shù)按中序、前序、對(duì)圖所示根樹(shù)按中序、前序、后序行遍法訪(fǎng)問(wèn)結(jié)果分別為：后序行遍法訪(fǎng)問(wèn)結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a43用用2叉有序正則樹(shù)存放算式叉有序正則樹(shù)存放算式存放規(guī)則存放規(guī)則l 最高層次運(yùn)算放在樹(shù)根最高層