離散數(shù)學(xué)第十六章課件

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

2、是樹是樹(2) G 中任意兩個(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è)含新邊的圈. 4)(2)()1(2xnxvdni 由上式解出由上式解出x 2. 定理定理16.2 設(shè)設(shè)T是是n階非平凡的無(wú)向樹，則階非平凡的無(wú)向樹，則T 中至少有兩片樹葉中至少有兩片

3、樹葉. 無(wú)向樹的性質(zhì)無(wú)向樹的性質(zhì)證證 設(shè)設(shè) T 有有 x 片樹葉，由握手定理及定理片樹葉，由握手定理及定理16.1可知，可知，5例題例題例例1 已知無(wú)向樹已知無(wú)向樹T中有中有1個(gè)個(gè)3度頂點(diǎn)，度頂點(diǎn)，2個(gè)個(gè)2度頂點(diǎn)，其余頂點(diǎn)度頂點(diǎn)，其余頂點(diǎn)全是樹葉，試求樹葉數(shù)全是樹葉，試求樹葉數(shù). 解解 解本題用樹的性質(zhì)解本題用樹的性質(zhì)m=n 1，握手定理，握手定理. 設(shè)有設(shè)有x片樹葉，于是片樹葉，于是 n = 1+2+x = 3+x, 2m = 2(n 1) = 2 (2+x) = 1 3+2 2+x解出解出x = 3，故，故T有有3片樹葉片樹葉.6例例2 已知無(wú)向樹已知無(wú)向樹T有有5片樹葉，片樹葉，2度與度

4、與3度頂點(diǎn)各度頂點(diǎn)各1個(gè)，其余頂個(gè)，其余頂點(diǎn)的度數(shù)均為點(diǎn)的度數(shù)均為4，求，求T的階數(shù)的階數(shù)n例題例題解解 設(shè)設(shè)T的階數(shù)為的階數(shù)為n, 則邊數(shù)為則邊數(shù)為n 1，4度頂點(diǎn)的個(gè)數(shù)為度頂點(diǎn)的個(gè)數(shù)為n 7. 由握手定理得由握手定理得 2m = 2(n 1) = 5 1+2 1+3 1+4(n 7)解出解出n = 8，4度頂點(diǎn)為度頂點(diǎn)為1個(gè)個(gè). 7子圖子圖定義定義14.8 G=, G =(1) GG G 為為G的的子圖子圖，G為為G 的的母圖母圖(2) 若若GG且且V =V，則稱，則稱G 為為G的的生成子圖生成子圖(3) 若若VV或或EE，稱，稱G 為為G的的真子圖真子圖(4) V （VV且且V）的）的導(dǎo)

5、出子圖導(dǎo)出子圖，記作，記作GV (5) E （EE且且E）的）的導(dǎo)出子圖導(dǎo)出子圖，記作，記作GE 在圖中，設(shè)在圖中，設(shè)G為為(1)中圖所表示，取中圖所表示，取V1=a，b，c，則，則V1的導(dǎo)出子圖的導(dǎo)出子圖GV1為為(2)中圖所示。取中圖所示。取E1=e1，e3，則，則E1的導(dǎo)出子圖的導(dǎo)出子圖GE1為為(3)中中圖所示。圖所示。8不一定連通，也不一定不含回路，如圖所示T定義定義16.2 設(shè)設(shè)G為無(wú)向圖為無(wú)向圖(1) G的的樹樹T 是是G 的子圖并且的子圖并且T是樹是樹(2) G的的生成樹生成樹T 是是G 的生成子圖并且的生成子圖并且T是樹是樹(3) 生成樹生成樹T的的樹枝樹枝G 的在的在T 中

6、的邊中的邊(4) 生成樹生成樹T的的弦弦G 的的不在不在T 中的邊中的邊(5) 生成樹生成樹T的的余樹余樹 T的所有弦的導(dǎo)出子圖的所有弦的導(dǎo)出子圖T16.2 生成樹生成樹9推論推論2 的邊數(shù)為的邊數(shù)為m n+1. T推論推論3 為為G的生成樹的生成樹T的余樹，的余樹，C為為G中任意一個(gè)圈，則中任意一個(gè)圈，則C與與 一定有公共邊一定有公共邊. .證證 否則，否則，C中的邊全在中的邊全在T中，這與中，這與T為樹矛盾為樹矛盾. TT定理定理16.3 無(wú)向圖無(wú)向圖G具有生成樹當(dāng)且僅當(dāng)具有生成樹當(dāng)且僅當(dāng)G連通連通.生成樹存在條件生成樹存在條件推論推論1 G為為n階階m條邊的無(wú)向連通圖，則條邊的無(wú)向連通圖

7、，則m n 1. 證證 必要性顯然必要性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）連通性）由定理由定理16.3和樹的邊數(shù)等于頂點(diǎn)數(shù)減和樹的邊數(shù)等于頂點(diǎn)數(shù)減1可立即得到下述推論。可立即得到下述推論。10基本回路系統(tǒng)基本回路系統(tǒng)定理定理16.4 設(shè)設(shè)T為為G的生成樹，的生成樹，e為為T的任意一條弦，則的任意一條弦，則T e中中含一個(gè)只有一條弦其余邊均為含一個(gè)只有一條弦其余邊均為T的樹枝的圈的樹枝的圈. 不同的弦對(duì)應(yīng)的不同的弦對(duì)應(yīng)的圈也不同圈也不同. 證證 設(shè)設(shè)e=(u,v)，在，在T中中u到到v有惟一路徑有惟一路徑 ，則，則

8、e為所求的圈為所求的圈. 定義定義16.3 設(shè)設(shè)T是是n階階m條邊的無(wú)向連通圖條邊的無(wú)向連通圖G的一棵生成樹，設(shè)的一棵生成樹，設(shè)e 1, e 2, , e m n+1為為T 的弦的弦. 設(shè)設(shè)Cr為為T 添加弦添加弦e r 產(chǎn)生的只含弦產(chǎn)生的只含弦e r、其余邊均為樹枝的圈、其余邊均為樹枝的圈. 稱稱Cr為為G的對(duì)應(yīng)樹的對(duì)應(yīng)樹T 的弦的弦e r的的基本基本回路回路或或基本圈基本圈，r=1, 2, , m n+1. 并稱并稱C1, C2, ,Cm n+1為為G對(duì)應(yīng)對(duì)應(yīng)T 的的基本回路系統(tǒng)基本回路系統(tǒng)，稱，稱m n+1為為G的的圈秩圈秩，記作，記作 (G). 求基本回路的算法：設(shè)弦求基本回路的算法：

9、設(shè)弦e=(u,v)，先求，先求T中中u到到v的路徑的路徑 uv，再并上弦再并上弦e，即得對(duì)應(yīng)，即得對(duì)應(yīng)e的基本回路的基本回路. 11Ca=aefCb=bdeCc=cdf此圖的圈秩為此圖的圈秩為3，基本回路系統(tǒng)為：基本回路系統(tǒng)為：Ca, Cb, Cc基本回路系統(tǒng)基本回路系統(tǒng)在下圖中，對(duì)應(yīng)生成樹的弦在下圖中，對(duì)應(yīng)生成樹的弦a，b，c的基本回路為：的基本回路為：12基本割集的存在基本割集的存在定理定理16.5 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹，的一棵生成樹，e為為T的樹枝，則的樹枝，則G中存在只含樹枝中存在只含樹枝e，其余邊都是弦的割集，且不同的樹枝對(duì)，其余邊都是弦的割集，且不同的樹枝對(duì)應(yīng)的割集

10、也不同應(yīng)的割集也不同.證證 由定理由定理16.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為所求為所求. 顯然不同的樹枝對(duì)應(yīng)的割集不同顯然不同的樹枝對(duì)應(yīng)的割集不同. 13定義定義16.4 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹，的一棵生成樹，e 1, e 2, , e n 1為為T 的樹枝，的樹枝，Si是是G的只含樹枝的只含樹枝e

11、 i的割集，則稱的割集，則稱Si為為G的對(duì)應(yīng)的對(duì)應(yīng)于生成樹于生成樹T由樹枝由樹枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并稱并稱S1,S2, , Sn 1為為G 對(duì)應(yīng)對(duì)應(yīng)T 的的基本割集系統(tǒng)基本割集系統(tǒng)，稱，稱n 1為為G的的割割集秩集秩，記作，記作 (G). 基本割集與基本割集系統(tǒng)基本割集與基本割集系統(tǒng)求基本割集的算法求基本割集的算法設(shè)設(shè)e 為生成樹為生成樹T 的樹枝，的樹枝，T e 為兩棵小樹為兩棵小樹T1與與T2，令，令 Se =e | e E(G)且且e的兩個(gè)端點(diǎn)分別屬于的兩個(gè)端點(diǎn)分別屬于T1與與T2 則則Se 為為e 對(duì)應(yīng)的基本割集對(duì)應(yīng)的基本割集. 14Sa

12、=a,f,gSb=b,g,hSd=d,h,iSc=c,f,hSe=e,f,i基本割集系統(tǒng)為：基本割集系統(tǒng)為：Sa , Sb , Sc , Sd , Se割集秩為割集秩為5.基本割集與基本割集系統(tǒng)基本割集與基本割集系統(tǒng)在下圖中，對(duì)應(yīng)樹枝在下圖中，對(duì)應(yīng)樹枝a，b，c，d，e的基本割集分別為：的基本割集分別為：15解解 弦弦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, Cf, Cg. 樹枝樹枝a, b, c, d對(duì)應(yīng)的基本割集分別為對(duì)應(yīng)的基本割集分別為 Sa=a, f, g, Sb=b, e, f, g

13、, Sc=c, e, f g, Sd=d, g, S基基=Sa, Sb, Sc, Sd. 例例 下下圖圖實(shí)線邊所示為生成樹，求基本回路系統(tǒng)與實(shí)線邊所示為生成樹，求基本回路系統(tǒng)與基本割集系統(tǒng)基本割集系統(tǒng)實(shí)例實(shí)例16最小生成樹最小生成樹定義定義16.5 T是無(wú)向連通帶權(quán)圖是無(wú)向連通帶權(quán)圖G=的生成樹的生成樹(1) T的權(quán)的權(quán)W(T)T的各邊權(quán)之和的各邊權(quán)之和(2) G的最小生成樹的最小生成樹G的所有生成樹中權(quán)最小的生成樹的所有生成樹中權(quán)最小的生成樹求最小生成樹的一個(gè)算法求最小生成樹的一個(gè)算法避圈法避圈法（Kruskal）設(shè)）設(shè)G=，將，將G中非環(huán)邊按權(quán)從小中非環(huán)邊按權(quán)從小到大排序：到大排序：e1,

14、 e2, , em.(1) 取取e1在在T中中(2) 查查e2，若，若e2與與e1不構(gòu)成回路，取不構(gòu)成回路，取e2也在也在T 中，否則棄去中，否則棄去e2.(3) 再查再查e3, 直到得到生成樹為止直到得到生成樹為止. 17例例4 求圖的一棵最小生成樹求圖的一棵最小生成樹.所求最小生成樹如所求最小生成樹如圖所示，圖所示，W(T)=38.實(shí)例實(shí)例1816.3 根根樹及其應(yīng)用樹及其應(yīng)用定義定義16.6 有向樹有向樹T 基圖為無(wú)向樹的有向圖。基圖為無(wú)向樹的有向圖。(1) T 為為根樹根樹T 中一個(gè)頂點(diǎn)入度為中一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)入度均為，其余頂點(diǎn)入度均為1的有向樹的有向樹.(2) 樹根樹根入度

15、為入度為0的頂點(diǎn)的頂點(diǎn)(3) 樹葉樹葉入度為入度為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)樹根與內(nèi)點(diǎn)的總稱樹根與內(nèi)點(diǎn)的總稱(6) 頂點(diǎn)頂點(diǎn)v的的層數(shù)層數(shù)從樹根到任意頂點(diǎn)從樹根到任意頂點(diǎn)v的路徑的長(zhǎng)度（即路的路徑的長(zhǎng)度（即路徑中的邊數(shù)）徑中的邊數(shù)）(7) 樹高樹高T 中所有頂點(diǎn)的最大層數(shù)中所有頂點(diǎn)的最大層數(shù)(8) 平凡根樹平凡根樹平凡圖平凡圖19根樹的畫法根樹的畫法:樹根放上方樹根放上方,省去所有有向邊上的箭頭省去所有有向邊上的箭頭如右圖所示如右圖所示 a是樹根是樹根 b,e,f,h,i是樹葉是樹葉 c,d,g是內(nèi)點(diǎn)是內(nèi)

16、點(diǎn) a,c,d,g是分支點(diǎn)是分支點(diǎn) a為為0層層;1層有層有b,c; 2層有層有d,e,f; 3層有層有g(shù),h; 4層有層有i. 樹高為樹高為4根根樹實(shí)例樹實(shí)例20家族樹與根子樹家族樹與根子樹定義定義16.7 設(shè)設(shè)T 為一顆非平凡的根樹為一顆非平凡的根樹(1) 祖先與后代祖先與后代 vi ，vj V(T)， vi vj ，若，若vi 可達(dá)可達(dá)vj ，則稱，則稱vi 為為vj的祖先的祖先 ， vj為為vi的后代的后代 。(2) 父親與兒子父親與兒子 vi ，vj V(T)， vi vj ，若，若vi 鄰接到鄰接到vj（即（即 E(T) ） ，則稱，則稱vi 為為vj的父親的父親 ， vj為為vi

17、的兒子的兒子 。(3) 兄弟兄弟 vj ，vkV(T)， vj vk ，若，若vj ，vk的父親相同的父親相同 ，則，則稱稱vj與與vk是兄弟是兄弟 。定義定義16.8 設(shè)設(shè)v為根樹為根樹T中的任意一個(gè)頂點(diǎn)，稱中的任意一個(gè)頂點(diǎn)，稱v及其后代的導(dǎo)出子及其后代的導(dǎo)出子圖圖Tv為為T的以的以v為根的為根的根子樹根子樹.常將根樹看成家族樹，家族中成員之間的關(guān)系由下面的定義給出：常將根樹看成家族樹，家族中成員之間的關(guān)系由下面的定義給出：21根樹的分類根樹的分類(1) T 為為有序根樹有序根樹同層上的頂點(diǎn)都標(biāo)定次序的根樹同層上的頂點(diǎn)都標(biāo)定次序的根樹(2) 根據(jù)根樹根據(jù)根樹T中的每個(gè)分支點(diǎn)兒子數(shù)以及是否有序

18、，可以將中的每個(gè)分支點(diǎn)兒子數(shù)以及是否有序，可以將根樹分為下列各類：根樹分為下列各類： r 叉樹叉樹每個(gè)分支點(diǎn)至多有每個(gè)分支點(diǎn)至多有r 個(gè)兒子個(gè)兒子 r 叉有序樹叉有序樹r叉樹是有序的叉樹是有序的 r 叉正則樹叉正則樹每個(gè)分支點(diǎn)恰有每個(gè)分支點(diǎn)恰有r 個(gè)兒子個(gè)兒子 r 叉正則有序樹叉正則有序樹又若又若r 叉正則樹是有序的叉正則樹是有序的 r 叉完全正則樹叉完全正則樹樹葉層數(shù)相同的樹葉層數(shù)相同的r叉正則樹叉正則樹 r 叉完全正則有序樹叉完全正則有序樹又若又若r 叉完全正則樹是有序的叉完全正則樹是有序的 2叉正則有序樹的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹分別叉正則有序樹的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹

19、分別稱為該分支點(diǎn)的左子樹和右子樹。稱為該分支點(diǎn)的左子樹和右子樹。 在所有的在所有的r叉樹中，最常用的是叉樹中，最常用的是2叉樹。下面介紹叉樹。下面介紹2叉樹的應(yīng)叉樹的應(yīng)用。用。22定義定義16.9 設(shè)設(shè)2叉樹叉樹T 有有t片樹葉片樹葉v1, v2, , vt，權(quán)分別為，權(quán)分別為w1, w2, , wt，稱，稱 為為T 的權(quán)，其中的權(quán)，其中l(wèi)(vi)是是vi 的層數(shù)的層數(shù). 在所有有在所有有t片樹葉，帶權(quán)片樹葉，帶權(quán)w1, w2, , wt 的的2叉樹中，權(quán)最小的叉樹中，權(quán)最小的2叉樹稱為叉樹稱為最優(yōu)最優(yōu)2叉樹叉樹. )()(1itiivlwtW最優(yōu)二叉樹最優(yōu)二叉樹求最優(yōu)求最優(yōu)2叉樹的算法叉樹的

20、算法 Huffman算法算法給定實(shí)數(shù)給定實(shí)數(shù)w1, w2, , wt ，且，且w1 w2 wt . （1）作）作t片樹葉片樹葉, 分別以分別以w1, w2, , wt為權(quán)為權(quán).（2）在所有入度為）在所有入度為0的頂點(diǎn)的頂點(diǎn)(不一定是樹葉不一定是樹葉)中選出兩個(gè)權(quán)最小中選出兩個(gè)權(quán)最小的頂點(diǎn)的頂點(diǎn), 添加一個(gè)新分支點(diǎn)添加一個(gè)新分支點(diǎn), 以這以這2個(gè)頂點(diǎn)為兒子個(gè)頂點(diǎn)為兒子, 其權(quán)等于這其權(quán)等于這2個(gè)兒子的權(quán)之和個(gè)兒子的權(quán)之和.（3）重復(fù)（）重復(fù)（2）, 直到只有直到只有1個(gè)入度為個(gè)入度為0 的頂點(diǎn)為止的頂點(diǎn)為止. W(T)等于所有分支點(diǎn)的權(quán)之和等于所有分支點(diǎn)的權(quán)之和23例例 5 求帶權(quán)為求帶權(quán)為1,

21、 1, 2, 3, 4, 5的最優(yōu)樹的最優(yōu)樹. 解題過(guò)程由下圖給出，解題過(guò)程由下圖給出，W(T)=38最優(yōu)二叉樹的算法最優(yōu)二叉樹的算法Huffman算法算法24最佳前綴碼最佳前綴碼定義定義16.10 設(shè)設(shè) 1 2 n-1 n是長(zhǎng)度為是長(zhǎng)度為 n 的符號(hào)串的符號(hào)串(1) 前綴前綴該符號(hào)串的子串該符號(hào)串的子串 1, 1 2, , 1 2 n 1 (2) 前綴碼前綴碼符號(hào)串集合符號(hào)串集合A= 1, 2, , m中的任意兩個(gè)符中的任意兩個(gè)符號(hào)串都互不為前綴號(hào)串都互不為前綴(3) 二元前綴碼二元前綴碼 i (i=1, 2, , m) 中只出現(xiàn)兩個(gè)符號(hào)，如中只出現(xiàn)兩個(gè)符號(hào)，如0與與1. 如何產(chǎn)生二元前綴碼

22、？如何產(chǎn)生二元前綴碼？定理定理16.6 一棵一棵2叉樹產(chǎn)生一個(gè)二元前綴碼叉樹產(chǎn)生一個(gè)二元前綴碼.推論推論 一棵正則一棵正則2叉樹產(chǎn)生惟一的叉樹產(chǎn)生惟一的一個(gè)二元一個(gè)二元前綴碼（按左子樹前綴碼（按左子樹標(biāo)標(biāo)0，右子樹標(biāo)，右子樹標(biāo)1）25一棵一棵2元樹產(chǎn)生一個(gè)二元前綴碼元樹產(chǎn)生一個(gè)二元前綴碼:對(duì)每個(gè)分支點(diǎn)對(duì)每個(gè)分支點(diǎn), 若關(guān)聯(lián)若關(guān)聯(lián)2條邊條邊, 則給左邊標(biāo)則給左邊標(biāo)0, 右邊標(biāo)右邊標(biāo)1; 若只關(guān)聯(lián)若只關(guān)聯(lián)1條邊條邊, 則可以給它標(biāo)則可以給它標(biāo)0(看作左邊看作左邊), 也可以也可以標(biāo)標(biāo)1(看作右邊看作右邊). 將從樹根到每一片樹葉的通路上標(biāo)將從樹根到每一片樹葉的通路上標(biāo)的數(shù)字組成的字符串記在樹葉處的

23、數(shù)字組成的字符串記在樹葉處, 所得的字符串所得的字符串構(gòu)成一個(gè)前綴碼，如右圖所示：構(gòu)成一個(gè)前綴碼，如右圖所示：最優(yōu)最優(yōu)2進(jìn)制編碼：使信息傳遞的進(jìn)制編碼：使信息傳遞的2進(jìn)制數(shù)最短進(jìn)制數(shù)最短由最優(yōu)由最優(yōu)2叉樹產(chǎn)生的前綴碼為最佳前綴碼。叉樹產(chǎn)生的前綴碼為最佳前綴碼。用最佳前綴碼傳輸?shù)亩M(jìn)制位數(shù)最省。用最佳前綴碼傳輸?shù)亩M(jìn)制位數(shù)最省。最佳前綴碼最佳前綴碼26圖所示二叉樹產(chǎn)生的前綴碼為圖所示二叉樹產(chǎn)生的前綴碼為 00, 10, 11, 011, 0100, 0101 二叉樹產(chǎn)生的前綴碼二叉樹產(chǎn)生的前綴碼27用用Huffman算法產(chǎn)生最佳前綴碼算法產(chǎn)生最佳前綴碼例例16.7 在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率

24、如下：在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求傳輸它們的最佳前綴碼，并求傳輸求傳輸它們的最佳前綴碼，并求傳輸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ù)字？28解解 用用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

25、, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。用。用Huffman算法求以頻率算法求以頻率(乘以乘以100)為權(quán)的最優(yōu)為權(quán)的最優(yōu)2叉樹。用此權(quán)產(chǎn)生的最優(yōu)叉樹。用此權(quán)產(chǎn)生的最優(yōu)2叉叉樹如下圖所示：樹如下圖所示： 求最佳前綴碼求最佳前綴碼傳傳100個(gè)按比例出現(xiàn)的八進(jìn)個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為數(shù)為 W(T)=285，傳，傳10n(n 2)個(gè)個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字按比例出現(xiàn)的八進(jìn)制數(shù)字需要需要2.85 10n個(gè)個(gè)二進(jìn)制數(shù)字二進(jìn)制數(shù)字，用等長(zhǎng)碼用等長(zhǎng)碼(長(zhǎng)為長(zhǎng)為3)傳輸需傳輸需3 10n個(gè)二進(jìn)制數(shù)字個(gè)二進(jìn)制

26、數(shù)字. 01-0 11-1 001-2 100-3 101-4 0001-500000-6 00001-7它產(chǎn)生的最優(yōu)前綴碼它產(chǎn)生的最優(yōu)前綴碼29波蘭符號(hào)法與逆波蘭符號(hào)法波蘭符號(hào)法與逆波蘭符號(hào)法行遍或周游根樹行遍或周游根樹T對(duì)根樹對(duì)根樹T的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次. 對(duì)于對(duì)于2叉有序正則樹有以下三種周游方式：叉有序正則樹有以下三種周游方式： 中序行遍法中序行遍法訪問(wèn)的次序?yàn)椋鹤笞訕?、根、右子樹訪問(wèn)的次序?yàn)椋鹤笞訕洹⒏?、右子?前序行遍法前序行遍法訪問(wèn)的次序?yàn)椋焊⒆笞訕?、右子樹訪問(wèn)的次序?yàn)椋焊⒆笞訕?、右子?后序行遍法后序行遍法訪問(wèn)的次序?yàn)椋鹤笞訕?、右子樹、根訪問(wèn)的

27、次序?yàn)椋鹤笞訕洹⒂易訕?、根?duì)如右圖所示的根樹對(duì)如右圖所示的根樹T（2叉有序正則叉有序正則樹樹）按中序、前序、后序行遍的周游）按中序、前序、后序行遍的周游結(jié)果分別為：結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a30用用2叉有序正則樹存放算式叉有序正則樹存放算式存放規(guī)則存放規(guī)則l 最高層次運(yùn)算放在樹根最高層次運(yùn)算放在樹根l 然后依次將運(yùn)算符放在根子然后依次將運(yùn)算符放在根子樹的根上樹的根上l 數(shù)放在樹葉上數(shù)放在樹葉上l 規(guī)定：被除數(shù)、被減數(shù)放在規(guī)定：被除數(shù)、被減數(shù)放在左子樹樹葉上左子樹樹葉上 算式算式(b+(c+d) a) (

28、e f) (g+h) (i j)存放在如上圖所示的存放在如上圖所示的2叉有叉有序正則樹上序正則樹上. 31波蘭符號(hào)法波蘭符號(hào)法波蘭符號(hào)法波蘭符號(hào)法按前序行遍法訪問(wèn)存放算式的按前序行遍法訪問(wèn)存放算式的2叉有序正則樹，其結(jié)果不加括號(hào)，叉有序正則樹，其結(jié)果不加括號(hào)，規(guī)定從右到左每個(gè)運(yùn)算符對(duì)它后面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算。在這規(guī)定從右到左每個(gè)運(yùn)算符對(duì)它后面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算。在這種算法中，由于運(yùn)算符在它的兩個(gè)運(yùn)算對(duì)象之前，所以稱此種算種算法中，由于運(yùn)算符在它的兩個(gè)運(yùn)算對(duì)象之前，所以稱此種算法為前綴符號(hào)法或波蘭符號(hào)法法為前綴符號(hào)法或波蘭符號(hào)法. 對(duì)下圖的訪問(wèn)結(jié)果為對(duì)下圖的訪問(wèn)結(jié)果為 b + c d a e

29、 f + g h i j 逆波蘭符號(hào)法逆波蘭符號(hào)法按后序行遍法訪問(wèn)存放算式的按后序行遍法訪問(wèn)存放算式的2叉有序正則樹，其結(jié)果不加括號(hào)，叉有序正則樹，其結(jié)果不加括號(hào)，規(guī)定從左到右每個(gè)運(yùn)算符對(duì)它前面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算。在這規(guī)定從左到右每個(gè)運(yùn)算符對(duì)它前面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算。在這種算法中，由于運(yùn)算符在它的兩個(gè)運(yùn)算對(duì)象之后，所以稱此種算種算法中，由于運(yùn)算符在它的兩個(gè)運(yùn)算對(duì)象之后，所以稱此種算法為后綴符號(hào)法或逆波蘭符號(hào)法法為后綴符號(hào)法或逆波蘭符號(hào)法. 對(duì)上圖的訪問(wèn)結(jié)果為對(duì)上圖的訪問(wèn)結(jié)果為 b c d + + a e f g h + i j 32重點(diǎn)重點(diǎn)主要內(nèi)容主要內(nèi)容l 無(wú)向樹及其性質(zhì)無(wú)向樹及其性質(zhì)l

30、 生成樹、生成樹、最小生成樹最小生成樹、基本回路系統(tǒng)基本回路系統(tǒng)、基本割集系統(tǒng)基本割集系統(tǒng)l 根樹及其分類根樹及其分類、最優(yōu)樹最優(yōu)樹、二叉樹產(chǎn)生的前綴碼二叉樹產(chǎn)生的前綴碼、最佳前綴最佳前綴碼碼、波蘭符號(hào)法波蘭符號(hào)法、逆波蘭符號(hào)法逆波蘭符號(hào)法基本要求基本要求l 深刻理解無(wú)向樹的定義及性質(zhì)深刻理解無(wú)向樹的定義及性質(zhì)l 熟練地求解無(wú)向樹熟練地求解無(wú)向樹l 準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹l 深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算l 理解根樹及其分類等概念理解根樹及其分類等概念l 熟練掌握求最優(yōu)樹及最佳前綴碼的方法熟

31、練掌握求最優(yōu)樹及最佳前綴碼的方法l 掌握波蘭符號(hào)法與逆波蘭符號(hào)法掌握波蘭符號(hào)法與逆波蘭符號(hào)法33第十六章第十六章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 無(wú)向樹及其性質(zhì)無(wú)向樹及其性質(zhì)l 生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)l 根樹及其分類、最優(yōu)樹、最佳前綴碼、波蘭符號(hào)法、逆波根樹及其分類、最優(yōu)樹、最佳前綴碼、波蘭符號(hào)法、逆波蘭符號(hào)法蘭符號(hào)法基本要求基本要求l 深刻理解無(wú)向樹的定義及性質(zhì)深刻理解無(wú)向樹的定義及性質(zhì)l 熟練地求解無(wú)向樹熟練地求解無(wú)向樹l 準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹l 深刻理解基本回路、基本

32、割集的概念，并會(huì)計(jì)算深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算l 理解根樹及其分類等概念理解根樹及其分類等概念l 會(huì)畫會(huì)畫n階（階（n較?。┓峭瑯?gòu)的無(wú)向樹及根樹（較?。┓峭瑯?gòu)的無(wú)向樹及根樹（1 n 6）l 熟練掌握求最優(yōu)樹及最佳前綴碼的方法熟練掌握求最優(yōu)樹及最佳前綴碼的方法l 掌握波蘭符號(hào)法與逆波蘭符號(hào)法掌握波蘭符號(hào)法與逆波蘭符號(hào)法34為樹葉數(shù)ttnnkii 2 kiitnm21tnivdtnmkiiniikii 212)(22222)2(3 kiinit（2）（3）從而解出從而解出練習(xí)練習(xí)11. 無(wú)向樹無(wú)向樹 T 有有ni個(gè)個(gè)i 度頂點(diǎn)，度頂點(diǎn)，i=2, 3, ,k，其余頂點(diǎn)全是樹葉，其余頂

33、點(diǎn)全是樹葉，求求T 的樹葉數(shù)的樹葉數(shù). 解解 用樹的性質(zhì)：邊數(shù)用樹的性質(zhì)：邊數(shù) m=n 1（n為階數(shù)），及握手定理為階數(shù)），及握手定理. (1) 352設(shè)設(shè)n階非平凡的無(wú)向樹階非平凡的無(wú)向樹T中，中， (T) k，k 1. 證明證明T至少至少 有有k片樹葉片樹葉. 證證 反證法反證法. 否則，否則，T至多有至多有s片樹葉，片樹葉，s k，下面利用握手定理及樹的，下面利用握手定理及樹的性質(zhì)性質(zhì)m = n 1推出矛盾推出矛盾. 由于由于 (T) k，故存在，故存在v0，d(v0) k. 于是，于是，sksnvdnmnii )1(2)(2221由此解出由此解出s k，這與，這與s k矛盾矛盾. 證本題的方法有多種，請(qǐng)用分支點(diǎn)都是割點(diǎn)來(lái)證明證本題的方法有多種，請(qǐng)用分支點(diǎn)都是割點(diǎn)來(lái)證明.練習(xí)