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

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)用 216.1 無(wú)向樹(shù)及其性質(zhì)無(wú)向樹(shù)及其性質(zhì)定義定義16.1 (1) 無(wú)向樹(shù)無(wú)向樹(shù)連通無(wú)回路的無(wú)向圖連通無(wú)回路的無(wú)向圖(2) 平凡樹(shù)平凡樹(shù)平凡圖平凡圖(3) 森林森林至少由兩個(gè)連通分支（每個(gè)都是樹(shù)）組成的無(wú)向至少由兩個(gè)連通分支（每個(gè)都是樹(shù)）組成的無(wú)向圖圖(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à)定義定理定理16.1 設(shè)設(shè)G=是是n階階m條邊的無(wú)向圖，則下面各命題條邊的無(wú)向圖，則下面各命題是等價(jià)的：是等價(jià)的：(1) G

2、是樹(shù)是樹(shù)(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ú)向樹(shù)，則階非平凡的無(wú)向樹(shù)，則T 中至少有兩片樹(shù)葉中至少有兩片

3、樹(shù)葉. 無(wú)向樹(shù)的性質(zhì)無(wú)向樹(shù)的性質(zhì)證證 設(shè)設(shè) T 有有 x 片樹(shù)葉，由握手定理及定理片樹(shù)葉，由握手定理及定理16.1可知，可知，5例題例題例例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ù)全是樹(shù)葉，試求樹(shù)葉數(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ù)葉.6例例2 已知無(wú)向樹(shù)已知無(wú)向樹(shù)T有有5片樹(shù)葉，片樹(shù)葉，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的的樹(shù)樹(shù)T 是是G 的子圖并且的子圖并且T是樹(shù)是樹(shù)(2) G的的生成樹(shù)生成樹(shù)T 是是G 的生成子圖并且的生成子圖并且T是樹(shù)是樹(shù)(3) 生成樹(shù)生成樹(shù)T的的樹(shù)枝樹(shù)枝G 的在的在T 中

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

7、，則m n 1. 證證 必要性顯然必要性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）連通性）由定理由定理16.3和樹(shù)的邊數(shù)等于頂點(diǎn)數(shù)減和樹(shù)的邊數(shù)等于頂點(diǎn)數(shù)減1可立即得到下述推論?？闪⒓吹玫较率鐾普?。10基本回路系統(tǒng)基本回路系統(tǒng)定理定理16.4 設(shè)設(shè)T為為G的生成樹(shù)，的生成樹(shù)，e為為T的任意一條弦，則的任意一條弦，則T e中中含一個(gè)只有一條弦其余邊均為含一個(gè)只有一條弦其余邊均為T的樹(shù)枝的圈的樹(shù)枝的圈. 不同的弦對(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è)的一棵生成樹(shù)，設(shè)e 1, e 2, , e m n+1為為T 的弦的弦. 設(shè)設(shè)Cr為為T 添加弦添加弦e r 產(chǎn)生的只含弦產(chǎn)生的只含弦e r、其余邊均為樹(shù)枝的圈、其余邊均為樹(shù)枝的圈. 稱稱Cr為為G的對(duì)應(yīng)樹(shù)的對(duì)應(yīng)樹(shù)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)生成樹(shù)的弦在下圖中，對(duì)應(yīng)生成樹(shù)的弦a，b，c的基本回路為：的基本回路為：12基本割集的存在基本割集的存在定理定理16.5 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹(shù)，的一棵生成樹(shù)，e為為T的樹(shù)枝，則的樹(shù)枝，則G中存在只含樹(shù)枝中存在只含樹(shù)枝e，其余邊都是弦的割集，且不同的樹(shù)枝對(duì)，其余邊都是弦的割集，且不同的樹(shù)枝對(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為所求為所求. 顯然不同的樹(shù)枝對(duì)應(yīng)的割集不同顯然不同的樹(shù)枝對(duì)應(yīng)的割集不同. 13定義定義16.4 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹(shù)，的一棵生成樹(shù)，e 1, e 2, , e n 1為為T 的樹(shù)枝，的樹(shù)枝，Si是是G的只含樹(shù)枝的只含樹(shù)枝e

11、 i的割集，則稱的割集，則稱Si為為G的對(duì)應(yīng)的對(duì)應(yīng)于生成樹(shù)于生成樹(shù)T由樹(shù)枝由樹(shù)枝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 為生成樹(shù)為生成樹(shù)T 的樹(shù)枝，的樹(shù)枝，T e 為兩棵小樹(shù)為兩棵小樹(shù)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)樹(shù)枝在下圖中，對(duì)應(yīng)樹(shù)枝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. 樹(shù)枝樹(shù)枝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í)線邊所示為生成樹(shù)，求基本回路系統(tǒng)與實(shí)線邊所示為生成樹(shù)，求基本回路系統(tǒng)與基本割集系統(tǒng)基本割集系統(tǒng)實(shí)例實(shí)例16最小生成樹(shù)最小生成樹(shù)定義定義16.5 T是無(wú)向連通帶權(quán)圖是無(wú)向連通帶權(quán)圖G=的生成樹(shù)的生成樹(shù)(1) T的權(quán)的權(quán)W(T)T的各邊權(quán)之和的各邊權(quán)之和(2) G的最小生成樹(shù)的最小生成樹(shù)G的所有生成樹(shù)中權(quán)最小的生成樹(shù)的所有生成樹(shù)中權(quán)最小的生成樹(shù)求最小生成樹(shù)的一個(gè)算法求最小生成樹(shù)的一個(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, 直到得到生成樹(shù)為止直到得到生成樹(shù)為止. 17例例4 求圖的一棵最小生成樹(shù)求圖的一棵最小生成樹(shù).所求最小生成樹(shù)如所求最小生成樹(shù)如圖所示，圖所示，W(T)=38.實(shí)例實(shí)例1816.3 根根樹(shù)及其應(yīng)用樹(shù)及其應(yīng)用定義定義16.6 有向樹(shù)有向樹(shù)T 基圖為無(wú)向樹(shù)的有向圖?；鶊D為無(wú)向樹(shù)的有向圖。(1) T 為為根樹(shù)根樹(shù)T 中一個(gè)頂點(diǎn)入度為中一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)入度均為，其余頂點(diǎn)入度均為1的有向樹(shù)的有向樹(shù).(2) 樹(shù)根樹(shù)根入度

15、為入度為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)的總稱樹(shù)根與內(nèi)點(diǎn)的總稱(6) 頂點(diǎn)頂點(diǎn)v的的層數(shù)層數(shù)從樹(shù)根到任意頂點(diǎn)從樹(shù)根到任意頂點(diǎn)v的路徑的長(zhǎng)度（即路的路徑的長(zhǎng)度（即路徑中的邊數(shù)）徑中的邊數(shù)）(7) 樹(shù)高樹(shù)高T 中所有頂點(diǎn)的最大層數(shù)中所有頂點(diǎn)的最大層數(shù)(8) 平凡根樹(shù)平凡根樹(shù)平凡圖平凡圖19根樹(shù)的畫法根樹(shù)的畫法:樹(shù)根放上方樹(shù)根放上方,省去所有有向邊上的箭頭省去所有有向邊上的箭頭如右圖所示如右圖所示 a是樹(shù)根是樹(shù)根 b,e,f,h,i是樹(shù)葉是樹(shù)葉 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. 樹(shù)高為樹(shù)高為4根根樹(shù)實(shí)例樹(shù)實(shí)例20家族樹(shù)與根子樹(shù)家族樹(shù)與根子樹(shù)定義定義16.7 設(shè)設(shè)T 為一顆非平凡的根樹(shù)為一顆非平凡的根樹(shù)(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為根樹(shù)為根樹(shù)T中的任意一個(gè)頂點(diǎn)，稱中的任意一個(gè)頂點(diǎn)，稱v及其后代的導(dǎo)出子及其后代的導(dǎo)出子圖圖Tv為為T的以的以v為根的為根的根子樹(shù)根子樹(shù).常將根樹(shù)看成家族樹(shù)，家族中成員之間的關(guān)系由下面的定義給出：常將根樹(shù)看成家族樹(shù)，家族中成員之間的關(guān)系由下面的定義給出：21根樹(shù)的分類根樹(shù)的分類(1) T 為為有序根樹(shù)有序根樹(shù)同層上的頂點(diǎn)都標(biāo)定次序的根樹(shù)同層上的頂點(diǎn)都標(biāo)定次序的根樹(shù)(2) 根據(jù)根樹(shù)根據(jù)根樹(shù)T中的每個(gè)分支點(diǎn)兒子數(shù)以及是否有序

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

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

20、算法 Huffman算法算法給定實(shí)數(shù)給定實(shí)數(shù)w1, w2, , wt ，且，且w1 w2 wt . （1）作）作t片樹(shù)葉片樹(shù)葉, 分別以分別以w1, w2, , wt為權(quán)為權(quán).（2）在所有入度為）在所有入度為0的頂點(diǎn)的頂點(diǎn)(不一定是樹(shù)葉不一定是樹(shù)葉)中選出兩個(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)樹(shù)的最優(yōu)樹(shù). 解題過(guò)程由下圖給出，解題過(guò)程由下圖給出，W(T)=38最優(yōu)二叉樹(shù)的算法最優(yōu)二叉樹(shù)的算法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叉樹(shù)產(chǎn)生一個(gè)二元前綴碼叉樹(shù)產(chǎn)生一個(gè)二元前綴碼.推論推論 一棵正則一棵正則2叉樹(shù)產(chǎn)生惟一的叉樹(shù)產(chǎn)生惟一的一個(gè)二元一個(gè)二元前綴碼（按左子樹(shù)前綴碼（按左子樹(shù)標(biāo)標(biāo)0，右子樹(shù)標(biāo)，右子樹(shù)標(biāo)1）25一棵一棵2元樹(shù)產(chǎn)生一個(gè)二元前綴碼元樹(shù)產(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(看作右邊看作右邊). 將從樹(shù)根到每一片樹(shù)葉的通路上標(biāo)將從樹(shù)根到每一片樹(shù)葉的通路上標(biāo)的數(shù)字組成的字符串記在樹(shù)葉處的

23、數(shù)字組成的字符串記在樹(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叉樹(shù)產(chǎn)生的前綴碼為最佳前綴碼。叉樹(shù)產(chǎn)生的前綴碼為最佳前綴碼。用最佳前綴碼傳輸?shù)亩M(jìn)制位數(shù)最省。用最佳前綴碼傳輸?shù)亩M(jìn)制位數(shù)最省。最佳前綴碼最佳前綴碼26圖所示二叉樹(shù)產(chǎn)生的前綴碼為圖所示二叉樹(shù)產(chǎn)生的前綴碼為 00, 10, 11, 011, 0100, 0101 二叉樹(shù)產(chǎn)生的前綴碼二叉樹(shù)產(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叉樹(shù)。用此權(quán)產(chǎn)生的最優(yōu)叉樹(shù)。用此權(quán)產(chǎn)生的最優(yōu)2叉叉樹(shù)如下圖所示：樹(shù)如下圖所示： 求最佳前綴碼求最佳前綴碼傳傳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)法行遍或周游根樹(shù)行遍或周游根樹(shù)T對(duì)根樹(shù)對(duì)根樹(shù)T的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次. 對(duì)于對(duì)于2叉有序正則樹(shù)有以下三種周游方式：叉有序正則樹(shù)有以下三種周游方式： 中序行遍法中序行遍法訪問(wèn)的次序?yàn)椋鹤笞訕?shù)、根、右子樹(shù)訪問(wèn)的次序?yàn)椋鹤笞訕?shù)、根、右子樹(shù) 前序行遍法前序行遍法訪問(wèn)的次序?yàn)椋焊⒆笞訕?shù)、右子樹(shù)訪問(wèn)的次序?yàn)椋焊?、左子?shù)、右子樹(shù) 后序行遍法后序行遍法訪問(wèn)的次序?yàn)椋鹤笞訕?shù)、右子樹(shù)、根訪問(wèn)的

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

28、e f) (g+h) (i j)存放在如上圖所示的存放在如上圖所示的2叉有叉有序正則樹(shù)上序正則樹(shù)上. 31波蘭符號(hào)法波蘭符號(hào)法波蘭符號(hào)法波蘭符號(hào)法按前序行遍法訪問(wèn)存放算式的按前序行遍法訪問(wèn)存放算式的2叉有序正則樹(shù)，其結(jié)果不加括號(hào)，叉有序正則樹(shù)，其結(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叉有序正則樹(shù)，其結(jié)果不加括號(hào)，叉有序正則樹(shù)，其結(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ú)向樹(shù)及其性質(zhì)無(wú)向樹(shù)及其性質(zhì)l

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

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

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

33、點(diǎn)全是樹(shù)葉，求求T 的樹(shù)葉數(shù)的樹(shù)葉數(shù). 解解 用樹(shù)的性質(zhì)：邊數(shù)用樹(shù)的性質(zhì)：邊數(shù) m=n 1（n為階數(shù)），及握手定理為階數(shù)），及握手定理. (1) 352設(shè)設(shè)n階非平凡的無(wú)向樹(shù)階非平凡的無(wú)向樹(shù)T中，中， (T) k，k 1. 證明證明T至少至少 有有k片樹(shù)葉片樹(shù)葉. 證證 反證法反證法. 否則，否則，T至多有至多有s片樹(shù)葉，片樹(shù)葉，s k，下面利用握手定理及樹(shù)的，下面利用握手定理及樹(shù)的性質(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í)