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ù)）組成至少由兩個(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à)定義定理定理16.1 設(shè)設(shè)G=是是n階階m條邊的無(wú)向圖，則下面各命題條邊的無(wú)向圖，則下面各命題是等價(jià)的：是等價(jià)的：(1) G 是樹(shù)是樹(shù)(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(3)(4). 只需證明只需證明G連通連通. 用反證法用反證法. 否則否則G有有s（s 2）個(gè)連）個(gè)連通通分支都是小樹(shù)分支都是小樹(shù). 于是有于是有mi=ni 1, ，這與這與m=n

3、1矛盾矛盾. 證明思路證明思路(2)(3). 若若G中有回路，則回路上任意兩點(diǎn)之間的路徑不中有回路，則回路上任意兩點(diǎn)之間的路徑不惟一惟一. 對(duì)對(duì)n用歸納法證明用歸納法證明m=n 1. n=1正確正確. 設(shè)設(shè)n k時(shí)對(duì)，證時(shí)對(duì)，證n=k+1時(shí)也對(duì)：取時(shí)也對(duì)：取G中邊中邊e，G e有且僅有兩個(gè)連通分支有且僅有兩個(gè)連通分支G1,G2(為什么為什么?) . ni k，由歸納，由歸納假設(shè)得假設(shè)得mi=ni 1, i=1,2. 于是，于是，m=m1+m2+1=n1+n2 2+1=n 1.)2(11 ssnsnmmsiisii(1)(2). 關(guān)鍵一步是關(guān)鍵一步是, 若路徑不惟一必有回路若路徑不惟一必有回路.

4、 5(4)(5). 只需證明只需證明G 中每條邊都是橋中每條邊都是橋. 為此只需證明命題為此只需證明命題 “G 是是 n 階階 m 條邊的無(wú)向連通圖，則條邊的無(wú)向連通圖，則 m n 1”. 命題的證明命題的證明: 對(duì)對(duì)n歸納歸納. e E, G e只有只有n 2條邊，由命題可知條邊，由命題可知G e不連通，故不連通，故e為橋?yàn)闃? 證明思路證明思路(5)(6). 由由(5)易知易知G為樹(shù)，由為樹(shù)，由(1)(2)知，知， u,v V（u v）, u到到v有惟一路徑，加新邊有惟一路徑，加新邊(u,v)得惟一的一個(gè)圈得惟一的一個(gè)圈. (6)(1). 只需證明只需證明G連通，這是顯然的連通，這是顯然的

5、. 6)(2)()1(2xnxvdni 由上式解出由上式解出x 2. 定理定理16.2 設(shè)設(shè)T是是n階非平凡的無(wú)向樹(shù)，則階非平凡的無(wú)向樹(shù)，則T 中至少有兩片樹(shù)葉中至少有兩片樹(shù)葉. 無(wú)向樹(shù)的性質(zhì)無(wú)向樹(shù)的性質(zhì)證證 設(shè)設(shè) T 有有 x 片樹(shù)葉，由握手定理及定理片樹(shù)葉，由握手定理及定理16.1可知，可知，7例題例題例例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ù)，并畫出滿足要求的非同構(gòu)的無(wú)向樹(shù)全是樹(shù)葉，試求樹(shù)葉數(shù)，并畫出滿足要求的非同構(gòu)的無(wú)向樹(shù). 解解 解本題用樹(shù)的性質(zhì)解本題用樹(shù)的性質(zhì)m=n 1，握手定理，握手定理. 設(shè)有設(shè)有x

6、片樹(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ù)列應(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，如圖所示，如圖所示. 8例例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，并畫出

7、滿足要求的所有非同，并畫出滿足要求的所有非同構(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. 由握手定理得由握手定理得 2m = 2(n 1) = 5 1+2 1+3 1+4(n 7)解出解出n = 8，4度頂點(diǎn)為度頂點(diǎn)為1個(gè)個(gè). 9T的度數(shù)列為的度數(shù)列為1, 1, 1, 1, 1, 2, 3, 4，共有，共有3棵非同構(gòu)的無(wú)向樹(shù)，棵非同構(gòu)的無(wú)向樹(shù)，如圖所示如圖所示.例題例題10不一定連通，也不一定不含回路，如圖所示T定義定義16.2 設(shè)設(shè)G為無(wú)向圖為無(wú)向圖(1) G的的樹(shù)樹(shù)T 是是G 的子圖并且是樹(shù)的子圖并且是樹(shù)(

8、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ù) 全體弦組成的集合的導(dǎo)出子圖全體弦組成的集合的導(dǎo)出子圖T16.2 生成樹(shù)生成樹(shù)11推論推論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)

9、具有生成樹(shù)當(dāng)且僅當(dāng)G連通連通.生成樹(shù)存在條件生成樹(shù)存在條件推論推論1 G為為n階階m條邊的無(wú)向連通圖，則條邊的無(wú)向連通圖，則m n 1. 證證 必要性顯然必要性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）連通性）12基本回路系統(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有惟一路徑有惟一路

10、徑 ，則，則 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è)弦求基

11、本回路的算法：設(shè)弦e=(u,v)，先求，先求T中中u到到v的路徑的路徑 uv，再并上弦再并上弦e，即得對(duì)應(yīng)，即得對(duì)應(yīng)e的基本回路的基本回路. 13基本割集的存在基本割集的存在定理定理16.5 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹(shù)，的一棵生成樹(shù)，e為為T的樹(shù)枝，則的樹(shù)枝，則G中存在只含樹(shù)枝中存在只含樹(shù)枝e，其余邊都是弦的割集，且不同的樹(shù)枝對(duì)，其余邊都是弦的割集，且不同的樹(shù)枝對(duì)應(yīng)的割集也不同應(yīng)的割集也不同.證證 由定理由定理16.1可知，可知，e是是T的橋，因而的橋，因而T e有兩個(gè)連通分支有兩個(gè)連通分支T1和和T2，令，令 Se=e | e E(G)且且 e 的兩個(gè)端點(diǎn)分別屬于的兩個(gè)端點(diǎn)分別屬于

12、V(T1)和和V(T2)，由構(gòu)造顯然可知由構(gòu)造顯然可知Se為為G的割集，的割集，e Se且且Se中除中除e外都是弦，外都是弦，所以所以Se為所求為所求. 顯然不同的樹(shù)枝對(duì)應(yīng)的割集不同顯然不同的樹(shù)枝對(duì)應(yīng)的割集不同. 14定義定義16.4 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹(shù)，的一棵生成樹(shù)，e 1, e 2, , e n 1為為T 的樹(shù)枝，的樹(shù)枝，Si是是G的只含樹(shù)枝的只含樹(shù)枝e 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)

13、基本割集系統(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)的基本割集. 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ì)

14、應(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 圖圖5實(shí)線邊所示為生成樹(shù)，求基本回路系統(tǒng)與實(shí)線邊所示為生成樹(shù)，求基本回路系統(tǒng)與基本割集系統(tǒng)基本割集系統(tǒng)實(shí)例實(shí)例16最小生成樹(shù)最小生成樹(shù)定義定義16.5 T是是G=的生成樹(shù)的生成樹(shù)(1) W(T)T各邊權(quán)之和各邊權(quán)之和(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)從小到大排序：到大排

15、序：e1, 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 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)(

16、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ù)根到從樹(shù)根到v的通路長(zhǎng)度的通路長(zhǎng)度(7) 樹(shù)高樹(shù)高T 中層數(shù)最大頂點(diǎn)的層數(shù)中層數(shù)最大頂點(diǎn)的層數(shù)(8) 平凡根樹(shù)平凡根樹(shù)平凡圖平凡圖19根根樹(shù)實(shí)例樹(shù)實(shí)例根樹(shù)的畫法根樹(shù)的畫法樹(shù)根放上方，省去所有有向邊上的箭頭樹(shù)根放上方，省去所有有向邊上的箭頭20家族樹(shù)與根子樹(shù)家族樹(shù)與根子樹(shù)定義定義16.7 T 為非平凡根樹(shù)為非平凡根樹(shù)(1) 祖先與后代祖先與后代(2) 父親與兒子父親與兒子(3) 兄弟兄弟定義

17、定義16.8 設(shè)設(shè)v為根樹(shù)為根樹(shù)T中任意一頂點(diǎn)，稱中任意一頂點(diǎn)，稱v及其后代的導(dǎo)出子及其后代的導(dǎo)出子圖為以圖為以v為根的為根的根子樹(shù)根子樹(shù).21根樹(shù)的分類根樹(shù)的分類(1) T 為為有序根樹(shù)有序根樹(shù)同層上頂點(diǎn)標(biāo)定次序的根樹(shù)同層上頂點(diǎn)標(biāo)定次序的根樹(shù)(2) 分類分類 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ù)樹(shù)葉層數(shù)相同的樹(shù)葉層數(shù)相同的r叉正則樹(shù)叉正則樹(shù) r 叉完全正則有序樹(shù)叉完全正則有序樹(shù)22定義定義16.9

18、設(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)樹(shù)的算法求最優(yōu)樹(shù)的算法 Huffman算法算法給定實(shí)數(shù)給定實(shí)數(shù)w1, w2, , wt，且，且w1 w2 wt. (1) 連接權(quán)為連接權(quán)為w1, w2的兩片樹(shù)葉，得一個(gè)分支點(diǎn)，其權(quán)為的兩片樹(shù)葉，得一個(gè)分支點(diǎn)，其權(quán)為w1+w

19、2.(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ù)葉為止. 23例例 5 求帶權(quán)為求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹(shù)的最優(yōu)樹(shù). 解題過(guò)程由圖解題過(guò)程由圖9給出，給出，W(T)=3824最佳前綴碼最佳前綴碼定義定義16.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

20、(2) 前綴碼前綴碼 1, 2, , m中任何兩個(gè)元素互不為前綴中任何兩個(gè)元素互不為前綴(3) 二元前綴碼二元前綴碼 i (i=1, 2, , m) 中只出現(xiàn)兩個(gè)符號(hào)，如中只出現(xiàn)兩個(gè)符號(hào)，如0與與1. 如何產(chǎn)生二元前綴碼？如何產(chǎn)生二元前綴碼？定理定理16.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）25圖所示二叉樹(shù)產(chǎn)生的前綴碼為圖所示二叉樹(shù)產(chǎn)生的前綴碼為 00, 10, 11, 011, 0100, 0101 26用用Huffman算法產(chǎn)生最佳前綴碼算法產(chǎn)生最佳前

21、綴碼例例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%求傳輸它們的最佳前綴碼，并求傳輸求傳輸它們的最佳前綴碼，并求傳輸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ù)字？27解解 用用100個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù)，即以個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù)，即以100乘各頻乘各頻率為權(quán)，并將各權(quán)由小到大排列，

22、得率為權(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-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ù)字. 28波蘭符號(hào)法與逆波蘭符號(hào)法波蘭符號(hào)法與逆波蘭符號(hào)法行遍或行遍或周游根樹(shù)周游根樹(shù)T對(duì)對(duì)T的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一

23、次. 對(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ù)按中序、前序、后序行遍法訪問(wèn)結(jié)果分別為：后序行遍法訪問(wèn)結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a29用用2叉有序正則樹(shù)存放算式叉有序正則樹(shù)存放算式存放規(guī)則存放規(guī)則l 最高層次運(yùn)算放在樹(shù)根最高層次運(yùn)算放在樹(shù)

24、根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) (e f) (g+h) (i j)存放在圖所示存放在圖所示2叉樹(shù)上叉樹(shù)上. 30波蘭符號(hào)法波蘭符號(hào)法波蘭符號(hào)法波蘭符號(hào)法按前序行遍法訪問(wèn)存放算式的按前序行遍法訪問(wèn)存放算式的2叉有序正則樹(shù)，其結(jié)果不加叉有序正則樹(shù)，其結(jié)果不加括號(hào)，規(guī)定每個(gè)運(yùn)算符號(hào)與其后面緊鄰兩個(gè)數(shù)進(jìn)行運(yùn)算，運(yùn)括號(hào)，規(guī)定每個(gè)運(yùn)算符號(hào)與其后面緊鄰兩個(gè)數(shù)進(jìn)行運(yùn)算，運(yùn)算結(jié)果正確算結(jié)果正確. 稱此算法為波蘭符號(hào)法或前綴符號(hào)法稱此算法為波

25、蘭符號(hào)法或前綴符號(hào)法. 對(duì)上圖的對(duì)上圖的訪問(wèn)結(jié)果為訪問(wèn)結(jié)果為 b + c d a e f + g h i j 逆波蘭符號(hào)法逆波蘭符號(hào)法按后序行遍法訪問(wèn)，規(guī)定每個(gè)運(yùn)算符與前面緊鄰兩數(shù)運(yùn)算，按后序行遍法訪問(wèn)，規(guī)定每個(gè)運(yùn)算符與前面緊鄰兩數(shù)運(yùn)算，稱為逆波蘭符號(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 31第十六章第十六章 習(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ù)、最佳前綴

26、碼、波蘭符號(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 深刻理解基本回路、基本割集的概念，并會(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)

27、法掌握波蘭符號(hào)法與逆波蘭符號(hào)法32為樹(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ù)葉，其余頂點(diǎn)全是樹(shù)葉，求求T 的樹(shù)葉數(shù)的樹(shù)葉數(shù). 解解 用樹(shù)的性質(zhì)：邊數(shù)用樹(shù)的性質(zhì)：邊數(shù) m=n 1（n為階數(shù)），及握手定理為階數(shù)），及握手定理. (1) 332設(shè)設(shè)n階非平凡的無(wú)向樹(shù)階非平凡的無(wú)向樹(shù)T中，中， (T) k，k 1. 證明證明T至少至少 有有k片樹(shù)葉片樹(shù)葉. 證證 反證法反證法. 否則，否則，T至

28、多有至多有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í)練習(xí)2343設(shè)設(shè)G為為n 階無(wú)向簡(jiǎn)單圖，階無(wú)向簡(jiǎn)單圖，n 5，證明，證明G 或或 中必含圈中必含圈.G本題的方法很多，證明中用：本題的方法很多，證明中用：G與與 邊數(shù)之和為邊數(shù)之和為Kn的邊的邊數(shù)數(shù) ，以及樹(shù)的性質(zhì)：，以及樹(shù)的性質(zhì)：m = n 1.G21(） nn方法一方法一. 反證法反證法. 否則否則G與與 的各連通分支都是樹(shù)