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

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

2、是樹是樹(2) G 中任意兩個頂點之間存在惟一的路徑中任意兩個頂點之間存在惟一的路徑.(3) G 中無回路且中無回路且 m=n 1. (4) G 是連通的且是連通的且 m=n 1.(5) G 是連通的且是連通的且 G 中任何邊均為橋中任何邊均為橋.(6) G 中沒有回路，但在任何兩個不同的頂點之間加一條新中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到惟一的一個含新邊的圈邊，在所得圖中得到惟一的一個含新邊的圈. 4)(2)()1(2xnxvdni 由上式解出由上式解出x 2. 定理定理16.2 設設T是是n階非平凡的無向樹，則階非平凡的無向樹，則T 中至少有兩片樹葉中至少有兩片

3、樹葉. 無向樹的性質無向樹的性質證證 設設 T 有有 x 片樹葉，由握手定理及定理片樹葉，由握手定理及定理16.1可知，可知，5例題例題例例1 已知無向樹已知無向樹T中有中有1個個3度頂點，度頂點，2個個2度頂點，其余頂點度頂點，其余頂點全是樹葉，試求樹葉數(shù)全是樹葉，試求樹葉數(shù). 解解 解本題用樹的性質解本題用樹的性質m=n 1，握手定理，握手定理. 設有設有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 已知無向樹已知無向樹T有有5片樹葉，片樹葉，2度與度

4、與3度頂點各度頂點各1個，其余頂個，其余頂點的度數(shù)均為點的度數(shù)均為4，求，求T的階數(shù)的階數(shù)n例題例題解解 設設T的階數(shù)為的階數(shù)為n, 則邊數(shù)為則邊數(shù)為n 1，4度頂點的個數(shù)為度頂點的個數(shù)為n 7. 由握手定理得由握手定理得 2m = 2(n 1) = 5 1+2 1+3 1+4(n 7)解出解出n = 8，4度頂點為度頂點為1個個. 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）的）的導

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

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

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

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

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

10、也不同應的割集也不同.證證 由定理由定理16.1可知，可知，e是是T的橋，因而的橋，因而T e有兩個連通分支有兩個連通分支T1和和T2，令，令 Se=e | e E(G)且且 e 的兩個端點分別屬于的兩個端點分別屬于V(T1)和和V(T2)，由構造顯然可知由構造顯然可知Se為為G的割集，的割集，e Se且且Se中除中除e外都是弦，外都是弦，所以所以Se為所求為所求. 顯然不同的樹枝對應的割集不同顯然不同的樹枝對應的割集不同. 13定義定義16.4 設設T是是n階連通圖階連通圖G的一棵生成樹，的一棵生成樹，e 1, e 2, , e n 1為為T 的樹枝，的樹枝，Si是是G的只含樹枝的只含樹枝e

11、 i的割集，則稱的割集，則稱Si為為G的對應的對應于生成樹于生成樹T由樹枝由樹枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并稱并稱S1,S2, , Sn 1為為G 對應對應T 的的基本割集系統(tǒng)基本割集系統(tǒng)，稱，稱n 1為為G的的割割集秩集秩，記作，記作 (G). 基本割集與基本割集系統(tǒng)基本割集與基本割集系統(tǒng)求基本割集的算法求基本割集的算法設設e 為生成樹為生成樹T 的樹枝，的樹枝，T e 為兩棵小樹為兩棵小樹T1與與T2，令，令 Se =e | e E(G)且且e的兩個端點分別屬于的兩個端點分別屬于T1與與T2 則則Se 為為e 對應的基本割集對應的基本割集. 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)在下圖中，對應樹枝在下圖中，對應樹枝a，b，c，d，e的基本割集分別為：的基本割集分別為：15解解 弦弦e, f, g對應的基本回路分別為對應的基本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基基=Ce, Cf, Cg. 樹枝樹枝a, b, c, d對應的基本割集分別為對應的基本割集分別為 Sa=a, f, g, Sb=b, e, f, g

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

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

15、為入度為0的頂點的頂點(3) 樹葉樹葉入度為入度為1，出度為，出度為0的頂點的頂點(4) 內點內點入度為入度為1，出度不為，出度不為0的頂點的頂點(5) 分支點分支點樹根與內點的總稱樹根與內點的總稱(6) 頂點頂點v的的層數(shù)層數(shù)從樹根到任意頂點從樹根到任意頂點v的路徑的長度（即路的路徑的長度（即路徑中的邊數(shù)）徑中的邊數(shù)）(7) 樹高樹高T 中所有頂點的最大層數(shù)中所有頂點的最大層數(shù)(8) 平凡根樹平凡根樹平凡圖平凡圖19根樹的畫法根樹的畫法:樹根放上方樹根放上方,省去所有有向邊上的箭頭省去所有有向邊上的箭頭如右圖所示如右圖所示 a是樹根是樹根 b,e,f,h,i是樹葉是樹葉 c,d,g是內點是內

16、點 a,c,d,g是分支點是分支點 a為為0層層;1層有層有b,c; 2層有層有d,e,f; 3層有層有g,h; 4層有層有i. 樹高為樹高為4根根樹實例樹實例20家族樹與根子樹家族樹與根子樹定義定義16.7 設設T 為一顆非平凡的根樹為一顆非平凡的根樹(1) 祖先與后代祖先與后代 vi ，vj V(T)， vi vj ，若，若vi 可達可達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 設設v為根樹為根樹T中的任意一個頂點，稱中的任意一個頂點，稱v及其后代的導出子及其后代的導出子圖圖Tv為為T的以的以v為根的為根的根子樹根子樹.常將根樹看成家族樹，家族中成員之間的關系由下面的定義給出：常將根樹看成家族樹，家族中成員之間的關系由下面的定義給出：21根樹的分類根樹的分類(1) T 為為有序根樹有序根樹同層上的頂點都標定次序的根樹同層上的頂點都標定次序的根樹(2) 根據(jù)根樹根據(jù)根樹T中的每個分支點兒子數(shù)以及是否有序

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

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

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

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

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

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

24、如下：在通信中，八進制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求傳輸它們的最佳前綴碼，并求傳輸求傳輸它們的最佳前綴碼，并求傳輸10n（n 2）個按上述比）個按上述比例出現(xiàn)的八進制數(shù)字需要多少個二進制數(shù)字？若用等長的例出現(xiàn)的八進制數(shù)字需要多少個二進制數(shù)字？若用等長的（長為（長為3）的碼字傳輸需要多少個二進制數(shù)字？）的碼字傳輸需要多少個二進制數(shù)字？28解解 用用100個八進制數(shù)字中各數(shù)字出現(xiàn)的個數(shù)，即以個八進制數(shù)字中各數(shù)字出現(xiàn)的個數(shù)，即以100乘各頻乘各頻率為權，并將各權由小到大排列，得率為權，并將各權由小到大排列，得w1=5

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

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波蘭符號法與逆波蘭符號法波蘭符號法與逆波蘭符號法行遍或周游根樹行遍或周游根樹T對根樹對根樹T的每個頂點訪問且僅訪問一次的每個頂點訪問且僅訪問一次. 對于對于2叉有序正則樹有以下三種周游方式：叉有序正則樹有以下三種周游方式： 中序行遍法中序行遍法訪問的次序為：左子樹、根、右子樹訪問的次序為：左子樹、根、右子樹 前序行遍法前序行遍法訪問的次序為：根、左子樹、右子樹訪問的次序為：根、左子樹、右子樹 后序行遍法后序行遍法訪問的次序為：左子樹、右子樹、根訪問的

27、次序為：左子樹、右子樹、根對如右圖所示的根樹對如右圖所示的根樹T（2叉有序正則叉有序正則樹樹）按中序、前序、后序行遍的周游）按中序、前序、后序行遍的周游結果分別為：結果分別為： 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 最高層次運算放在樹根最高層次運算放在樹根l 然后依次將運算符放在根子然后依次將運算符放在根子樹的根上樹的根上l 數(shù)放在樹葉上數(shù)放在樹葉上l 規(guī)定：被除數(shù)、被減數(shù)放在規(guī)定：被除數(shù)、被減數(shù)放在左子樹樹葉上左子樹樹葉上 算式算式(b+(c+d) a) (

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

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

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

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

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

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