《離散數(shù)學(xué)》ppt課件

1、離散數(shù)學(xué)離散數(shù)學(xué)Discrete Discrete Mathematics Mathematics 16.1 無(wú)向樹及其性質(zhì)無(wú)向樹及其性質(zhì)16.2 生成樹生成樹16.3 根樹及其運(yùn)用根樹及其運(yùn)用定義定義16.1無(wú)向樹無(wú)向樹: 連通無(wú)回路的無(wú)向圖連通無(wú)回路的無(wú)向圖平凡樹平凡樹: 平凡圖平凡圖森林森林: 每個(gè)連通分支都是樹的非連通的無(wú)向圖每個(gè)連通分支都是樹的非連通的無(wú)向圖樹葉樹葉: 樹中度數(shù)為樹中度數(shù)為1的頂點(diǎn)的頂點(diǎn)分支點(diǎn)分支點(diǎn): 樹中度數(shù)樹中度數(shù)2的頂點(diǎn)的頂點(diǎn)右圖為一棵右圖為一棵12階樹階樹.聲明聲明:本章中所討論的回路均本章中所討論的回路均 指簡(jiǎn)單回路或初級(jí)回路指簡(jiǎn)單回路或初級(jí)回路定理定理16

2、.1 設(shè)設(shè)G=是是n階階m條邊的無(wú)向圖，那么以下等價(jià)的：條邊的無(wú)向圖，那么以下等價(jià)的：1G是樹是樹;2G中恣意兩個(gè)頂點(diǎn)之間存在獨(dú)一的途徑中恣意兩個(gè)頂點(diǎn)之間存在獨(dú)一的途徑;3G中無(wú)回路且中無(wú)回路且m=n1;4G是連通的且是連通的且m=n1;5G是連通的且是連通的且G中任何邊均為橋中任何邊均為橋;6G中沒(méi)有回路中沒(méi)有回路, 但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有獨(dú)一的一個(gè)含新邊的圈所得圖中有獨(dú)一的一個(gè)含新邊的圈. 證明：證明： 由于由于G是樹，所以是樹，所以G是連通的，是連通的，u, vV，u和和v之間存在一條路。之間存在一條路。假設(shè)路不獨(dú)一，設(shè)假設(shè)

3、路不獨(dú)一，設(shè)L1和和L2都是都是u和和v之間的路，之間的路，那么由那么由L1和和L2上的邊組成了上的邊組成了G中的一個(gè)回路，矛盾。中的一個(gè)回路，矛盾。 先證先證G中無(wú)回路。假設(shè)中無(wú)回路。假設(shè)G中存在某個(gè)結(jié)點(diǎn)中存在某個(gè)結(jié)點(diǎn)v上的環(huán)，上的環(huán)， uV，由條件知，由條件知u到到v存在一條路存在一條路L1：uv， 那么那么u到到v有另一條路有另一條路L2：uvv，矛盾。，矛盾。 假設(shè)假設(shè)G中存在長(zhǎng)度大于等于中存在長(zhǎng)度大于等于2的一條回路，那么回路上兩個(gè)結(jié)點(diǎn)之的一條回路，那么回路上兩個(gè)結(jié)點(diǎn)之間存在不同的路間存在不同的路, 矛盾。所以矛盾。所以G中無(wú)回路。中無(wú)回路。 以下用歸納法證明以下用歸納法證明m=n1

4、。 當(dāng)當(dāng)n=1時(shí)，時(shí)，G為平凡圖，為平凡圖，m=0=11=n1。結(jié)論成立。結(jié)論成立。 設(shè)設(shè)nk時(shí)，結(jié)論成立。下證時(shí)，結(jié)論成立。下證n=k+1時(shí)，結(jié)論也成立。時(shí)，結(jié)論也成立。 設(shè)設(shè)e=(u,v)是是G中的一條邊，由于中的一條邊，由于G中無(wú)回路，所以中無(wú)回路，所以G-e有兩個(gè)有兩個(gè)連通分支連通分支G1和和G2，設(shè)它們的結(jié)點(diǎn)數(shù)和邊數(shù)分別為：，設(shè)它們的結(jié)點(diǎn)數(shù)和邊數(shù)分別為：n1，m1和和n2，m2。 于是有于是有n1k和和n2k，由歸納假設(shè)知：，由歸納假設(shè)知：m1=n11和和m2=n2-1， m=m1m21=n1-1n2-11=n-1。只須證明只須證明G是連通的。假設(shè)不然是連通的。假設(shè)不然,設(shè)設(shè)G有有s

5、(s2)個(gè)連通分支個(gè)連通分支G1,G2,Gs, Gi中均無(wú)回路，都是樹。由中均無(wú)回路，都是樹。由可知，可知，mi=ni1，i=1,s。于是于是m=m1m2ms=n1-1n2-1ns-1=n1n2ns-s=ns，由于由于s2，這與，這與m=n1矛盾。所以矛盾。所以G是連通圖。是連通圖。 只須證明只須證明G的每一條邊均為橋。的每一條邊均為橋。設(shè)設(shè)e是是G的恣意邊，刪除的恣意邊，刪除e得子圖得子圖G1，它的邊數(shù)，它的邊數(shù)m1=m-1，結(jié)點(diǎn)數(shù)，結(jié)點(diǎn)數(shù)n1=n， m1=m1=n-1-1=n-2=n1-2n1-1，由習(xí)題，由習(xí)題14的第的第49題知題知G1不是連通圖，不是連通圖，所以所以e是橋。是橋。 由

6、于由于G中每一條邊均為橋，因此中每一條邊均為橋，因此G中無(wú)回路。又由于中無(wú)回路。又由于G連通，所以連通，所以G是樹。由是樹。由知，知，u, vV，uv，u與與v之間存在一條獨(dú)一的路。之間存在一條獨(dú)一的路。在在u與與v之間添加一條新邊之間添加一條新邊, 得到得到G的一條回路的一條回路, 顯然這條回路是獨(dú)一的。顯然這條回路是獨(dú)一的。 只須證明只須證明G是連通的，是連通的，u, vV，uv，在，在u與與v之間添加一條新邊之間添加一條新邊(u,v)就產(chǎn)生就產(chǎn)生G的一個(gè)獨(dú)一的回路，故結(jié)點(diǎn)的一個(gè)獨(dú)一的回路，故結(jié)點(diǎn)u和結(jié)點(diǎn)和結(jié)點(diǎn)v連通。由于連通。由于u與與v是恣意是恣意的，所以的，所以G是連通圖。是連通圖。

7、 )(2)()1(2xnxvdni 定理定理16.2 設(shè)設(shè)T 是是 n 階非平凡的無(wú)向樹，那么階非平凡的無(wú)向樹，那么T中至少有兩片中至少有兩片樹葉樹葉. 由上式解出由上式解出x2.證證 設(shè)設(shè)T有有x片樹葉，由握手定理及定理片樹葉，由握手定理及定理9.1可知，可知，例例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ù), 并畫出滿足要求的非同構(gòu)的無(wú)向樹并畫出滿足要求的非同構(gòu)的無(wú)向樹. 解解 用樹的性質(zhì)用樹的性質(zhì)m=n1和握手定理和握手定理. 設(shè)有設(shè)有x片樹葉，于是片樹葉，于是 n=1+2+x=3+x, 2m=

8、2(n1)=2(2+x)=13+22+x解出解出x=3，故，故T有有3片樹葉片樹葉. T的度數(shù)列為的度數(shù)列為1, 1, 1, 2, 2, 3 有有2棵非同構(gòu)的無(wú)向樹棵非同構(gòu)的無(wú)向樹, 如下圖如下圖例例2 知無(wú)向樹知無(wú)向樹T有有5片樹葉片樹葉, 2度與度與3度頂點(diǎn)各度頂點(diǎn)各1個(gè)個(gè), 其他頂點(diǎn)的度數(shù)其他頂點(diǎn)的度數(shù)均為均為4. 求求T的階數(shù)的階數(shù)n, 并畫出滿足要求的一切非同構(gòu)的無(wú)向樹并畫出滿足要求的一切非同構(gòu)的無(wú)向樹. 解解 設(shè)設(shè)T的階數(shù)為的階數(shù)為n, 那么邊數(shù)為那么邊數(shù)為n1, 4度頂點(diǎn)的個(gè)數(shù)為度頂點(diǎn)的個(gè)數(shù)為n7. 由由握手定理得握手定理得 2m=2(n1)=51+21+31+4(n7)解出解出

9、n=8, 4度頂點(diǎn)為度頂點(diǎn)為1個(gè)個(gè). T的度數(shù)列為的度數(shù)列為1,1,1,1,1,2,3,4 有有3棵非同構(gòu)的無(wú)向樹棵非同構(gòu)的無(wú)向樹 定義定義16.2 設(shè)設(shè)G為無(wú)向連通圖為無(wú)向連通圖G的生成樹的生成樹: G的生成子圖并且是樹的生成子圖并且是樹生成樹生成樹T的樹枝的樹枝: G在在T中的邊中的邊生成樹生成樹T的弦的弦: G不在不在T中的邊中的邊T留意：留意： 不一定連通不一定連通, 也不一定不含回路也不一定不含回路.T生成樹生成樹T的余樹的余樹 : 一切弦的集合的導(dǎo)出子圖一切弦的集合的導(dǎo)出子圖例例e1e2e7e8e9e11e10e3e5e4e6(1)(2)生成樹生成樹T的弦的弦: e6, e7, e

10、8, e10 , e11定理定理16.3無(wú)向圖無(wú)向圖G具有生成樹當(dāng)且僅當(dāng)具有生成樹當(dāng)且僅當(dāng)G為連通圖。為連通圖。證明：必要行顯然。證明：必要行顯然。以下證明假設(shè)無(wú)向圖以下證明假設(shè)無(wú)向圖G為連通圖，那么為連通圖，那么G具有生成樹。具有生成樹。假設(shè)連通圖假設(shè)連通圖G無(wú)回路，那么無(wú)回路，那么G本身就是一棵生成樹；本身就是一棵生成樹；假設(shè)假設(shè)G至少有一個(gè)回路，刪除此回路的一邊，得到子圖至少有一個(gè)回路，刪除此回路的一邊，得到子圖G1，它依然，它依然連通，并與連通，并與G有一樣結(jié)點(diǎn)集。有一樣結(jié)點(diǎn)集。假設(shè)假設(shè)G1無(wú)回路，那么無(wú)回路，那么G1就是一棵生成樹；就是一棵生成樹；假設(shè)假設(shè)G1仍有一個(gè)回路，再刪除仍有

11、一個(gè)回路，再刪除G1回路上的一邊?；芈飞系囊贿叀７磸?fù)上述過(guò)程反復(fù)上述過(guò)程,直至得到一個(gè)無(wú)回路的連通圖直至得到一個(gè)無(wú)回路的連通圖, 該圖就是一棵生成樹該圖就是一棵生成樹.推論推論3 設(shè)設(shè) 為為G的生成樹的生成樹 T 的余樹，的余樹，C 為為G 中恣意一個(gè)圈，那么中恣意一個(gè)圈，那么C與與 一定有公共邊一定有公共邊. TT推論推論1 設(shè)設(shè)n階無(wú)向連通圖有階無(wú)向連通圖有m條邊條邊, 那么那么mn1. 推論推論2 設(shè)設(shè)n階無(wú)向連通圖有階無(wú)向連通圖有m條邊條邊, 那么它的生成樹的余樹有那么它的生成樹的余樹有mn+1條邊條邊.定義定義16.3 設(shè)設(shè)T是是n階階m條邊的無(wú)向連通圖條邊的無(wú)向連通圖G的一棵生成樹

12、的一棵生成樹,設(shè)設(shè)e1, e2, , emn+1為為T的弦的弦. 設(shè)設(shè)Cr為為T添加弦添加弦er產(chǎn)生的產(chǎn)生的G中獨(dú)一的中獨(dú)一的圈圈, 稱稱Cr為對(duì)應(yīng)弦為對(duì)應(yīng)弦er的根本回路或根本圈的根本回路或根本圈, r=1, 2, mn+1. 稱稱C1, C2, , Cmn+1為對(duì)應(yīng)為對(duì)應(yīng)T的根本回路系統(tǒng)的根本回路系統(tǒng). mn1稱為稱為G的圈的圈秩秩.無(wú)向連通圖的秩，與生成樹的選擇無(wú)關(guān)。無(wú)向連通圖的秩，與生成樹的選擇無(wú)關(guān)。求根本回路的算法求根本回路的算法: 設(shè)弦設(shè)弦e=(u,v), 先求先求T中中u到到v的途徑的途徑 uv, 再并上弦再并上弦e, 即得對(duì)應(yīng)即得對(duì)應(yīng)e的根本回路的根本回路. 例例e1e2e7e

13、8e9e11e10e3e5e4e6生成樹生成樹T的弦的弦: e6, e7, e8, e10 , e11它們對(duì)應(yīng)的根本回路分別為它們對(duì)應(yīng)的根本回路分別為: C1=e6e4e5 C2=e7e2e1C3=e8e9e2e1 C4=e10e3e5e2C4=e11e3e5e2e9上圖的圈秩為上圖的圈秩為5,根本回路系統(tǒng)為根本回路系統(tǒng)為C1,C2, C3,C4,C5.定義定義16.5 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹的一棵生成樹, e1, e2, , en1為為T的樹枝，的樹枝，Si是是G的只含樹枝的只含樹枝ei, 其他邊都是弦的割集其他邊都是弦的割集, 稱稱Si為對(duì)應(yīng)生為對(duì)應(yīng)生成樹成樹T由樹枝由

14、樹枝ei生成的根本割集生成的根本割集, i=1, 2, , n1. 稱稱S1, S2, , Sn1為對(duì)應(yīng)為對(duì)應(yīng)T的根本割集系統(tǒng)的根本割集系統(tǒng).稱稱n1為為G的割集秩的割集秩. 求根本割集的算法求根本割集的算法: 設(shè)設(shè)e為生成樹為生成樹T的樹枝的樹枝, Te由兩棵子樹由兩棵子樹T1與與T2組成組成, 令令 Se=e | eE(G)且且e的兩個(gè)端點(diǎn)分別屬于的兩個(gè)端點(diǎn)分別屬于T1與與T2 那么那么Se為為e對(duì)應(yīng)的根本割集對(duì)應(yīng)的根本割集. 例例e1e2e7e8e9e11e10e3e5e4e6T的樹枝的樹枝: e1, e2, e3, e4, e5, e9它們的根本割集分別為它們的根本割集分別為:S1 =

15、e1, e7, e8, S2 =e2, e7, e8 , e10, e11, S3 =e3, e10, e11, S4 =e4, e6, S5 =e5, e6, e10, e11, S9 =e9, e8 , e11 .G的割集秩為的割集秩為6.例例 圖中紅邊為一棵生成樹圖中紅邊為一棵生成樹, , 求對(duì)應(yīng)它的根本回路系統(tǒng)求對(duì)應(yīng)它的根本回路系統(tǒng) 與根本割集系統(tǒng)與根本割集系統(tǒng)解解 弦弦e,f,ge,f,g對(duì)應(yīng)的根本回路分別為對(duì)應(yīng)的根本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, Ce=e b c, Cf=f a b c, Cg=g a b c d, C C基基=

16、Ce, Cf, Cg. =Ce, Cf, Cg. 樹枝樹枝a,b,c,da,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, Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S S基基=Sa, Sb, Sc, Sd.=Sa, Sb, Sc, Sd.定義定義16.4 對(duì)無(wú)向圖或有向圖的每一條邊對(duì)無(wú)向圖或有向圖的每一條邊e附加一個(gè)實(shí)數(shù)附加一個(gè)實(shí)數(shù)w(e), 稱作邊稱作邊e的權(quán)的權(quán). 圖連同附加在邊上的權(quán)稱作帶權(quán)圖圖連同附加在邊上的權(quán)稱作帶權(quán)圖,

17、記作記作G=. 設(shè)設(shè)G是是G的子圖的子圖, G一切邊的權(quán)的和稱作一切邊的權(quán)的和稱作G的權(quán)的權(quán), 記作記作W(G). 最小生成樹最小生成樹: 帶權(quán)圖權(quán)最小的生成樹帶權(quán)圖權(quán)最小的生成樹求最小生成樹的算法求最小生成樹的算法避圈法避圈法 (Kruskal)設(shè)設(shè)G=, 將非環(huán)邊按權(quán)從小到大排序：將非環(huán)邊按權(quán)從小到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 檢查檢查e2, 假設(shè)假設(shè)e2與與e1不構(gòu)成回路不構(gòu)成回路, 那么將那么將e2參與參與T中中, 否那否那么棄去么棄去e2.(3) 檢查檢查e3, 反復(fù)進(jìn)展直至得到生成樹為止反復(fù)進(jìn)展直至得到生成樹為止. 例例 求圖的一棵最小生成樹求

18、圖的一棵最小生成樹 W(T)=38有向樹有向樹根樹、樹根、樹葉、內(nèi)點(diǎn)、分支點(diǎn)根樹、樹根、樹葉、內(nèi)點(diǎn)、分支點(diǎn)家族樹、根子樹、有序樹家族樹、根子樹、有序樹r叉樹叉樹r叉有序樹叉有序樹r叉正那么樹叉正那么樹r叉有序正那么樹叉有序正那么樹r叉完全正那么樹叉完全正那么樹r叉有序完全正那么樹叉有序完全正那么樹最優(yōu)最優(yōu)2叉樹與叉樹與Huffman算法算法前綴嗎與最正確前綴嗎前綴嗎與最正確前綴嗎中序行遍法、前序行遍法、后續(xù)行遍法中序行遍法、前序行遍法、后續(xù)行遍法波蘭符號(hào)法與逆波蘭符號(hào)法波蘭符號(hào)法與逆波蘭符號(hào)法 有向樹有向樹: 基圖為無(wú)向樹的有向圖基圖為無(wú)向樹的有向圖定義定義16.6 根樹根樹: 有一個(gè)頂點(diǎn)入度

19、為有一個(gè)頂點(diǎn)入度為0, 其他的入度均為其他的入度均為1的非平凡的有向樹的非平凡的有向樹樹根樹根: 有向樹中入度為有向樹中入度為0的頂點(diǎn)的頂點(diǎn)樹葉樹葉: 有向樹中入度為有向樹中入度為1, 出度為出度為0的頂點(diǎn)的頂點(diǎn)內(nèi)點(diǎn)內(nèi)點(diǎn): 有向樹中入度為有向樹中入度為1, 出度大于出度大于0的頂點(diǎn)的頂點(diǎn)分支點(diǎn)分支點(diǎn): 樹根與內(nèi)點(diǎn)的總稱樹根與內(nèi)點(diǎn)的總稱頂點(diǎn)頂點(diǎn)v的層數(shù)的層數(shù): 從樹根到從樹根到v的通路長(zhǎng)度的通路長(zhǎng)度樹高樹高: 有向樹中頂點(diǎn)的最大層數(shù)有向樹中頂點(diǎn)的最大層數(shù)根樹的畫法根樹的畫法: :樹根放上方樹根放上方, ,省去一切有向邊上的箭頭省去一切有向邊上的箭頭如右圖所示如右圖所示 a a是樹根是樹根 b,e

20、,f,h,i b,e,f,h,i是樹葉是樹葉 c,d,g c,d,g是內(nèi)點(diǎn)是內(nèi)點(diǎn) a,c,d,g a,c,d,g是分支點(diǎn)是分支點(diǎn) a a為為0 0層層;1;1層有層有b,c; 2b,c; 2層有層有d,e,f;d,e,f; 3 3層有層有g(shù),h; 4g,h; 4層有層有i.i. 樹高為樹高為4 4定義定義16.7 根樹看作一棵家族樹根樹看作一棵家族樹:(1) 假設(shè)頂點(diǎn)假設(shè)頂點(diǎn) a 鄰接到頂點(diǎn)鄰接到頂點(diǎn) b, 那么稱那么稱 b 是是 a 的兒子的兒子, a 是是 b 的父親的父親;(2) 假設(shè)假設(shè)b和和c為同一個(gè)頂點(diǎn)的兒子為同一個(gè)頂點(diǎn)的兒子, 那么稱那么稱b和和c是兄弟是兄弟;(3) 假設(shè)假設(shè)a

21、b且且a可達(dá)可達(dá)b, 那么稱那么稱a是是b的祖先的祖先, b是是a的后代的后代.有序樹有序樹: 將根樹同層上的頂點(diǎn)規(guī)定次序?qū)⒏鶚渫瑢由系捻旤c(diǎn)規(guī)定次序r叉樹叉樹:根樹的每個(gè)分支點(diǎn)至多有根樹的每個(gè)分支點(diǎn)至多有r個(gè)兒子個(gè)兒子r叉正那么樹叉正那么樹: 根樹的每個(gè)分支點(diǎn)恰有根樹的每個(gè)分支點(diǎn)恰有r個(gè)兒子個(gè)兒子r叉完全正那么樹叉完全正那么樹: 樹葉層數(shù)一樣的樹葉層數(shù)一樣的r元正那么樹元正那么樹r叉有序樹叉有序樹: 有序的有序的r元樹元樹r叉正那么有序樹叉正那么有序樹: 有序的有序的r元正那么樹元正那么樹r叉完全正那么有序樹叉完全正那么有序樹: 有序的有序的r元完全正那么樹元完全正那么樹)()(1itiivl

22、wtW 定義定義16.9 設(shè)設(shè)2叉樹叉樹T有有t片樹葉片樹葉v1, v2, , vt, 樹葉的權(quán)分別樹葉的權(quán)分別 為為w1, w2, , wt, 稱稱 為為T的權(quán)的權(quán), 記作記作 W(T), 其中其中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叉樹叉樹.定義定義16.8 設(shè)設(shè)v為根樹的一個(gè)頂點(diǎn)且不是樹根為根樹的一個(gè)頂點(diǎn)且不是樹根, 稱稱v及其一切后代及其一切后代的導(dǎo)出子圖為以的導(dǎo)出子圖為以v為根的根子樹為根的根子樹. 2叉正那么有序樹的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子

23、樹分叉正那么有序樹的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹分別稱為左子樹和右子樹別稱為左子樹和右子樹.例子例子:P313 圖圖16.7以下圖中的三棵樹以下圖中的三棵樹T1，T2和和T3都是帶權(quán)都是帶權(quán)2，2，3，3，5的二叉樹的二叉樹.以上三棵樹不是最優(yōu)樹。以上三棵樹不是最優(yōu)樹。W(T1)=2222335332=38W(T2)=3454332221=47W(T3)=3333522222=36它們的權(quán)分別是：它們的權(quán)分別是： Huffman算法算法:給定給定t片樹葉的權(quán)為片樹葉的權(quán)為W1,W2,Wt且且W1W2Wt。 銜接權(quán)為銜接權(quán)為W1，W2的兩片樹葉，得一分枝點(diǎn)，其權(quán)為的兩片樹葉，得一分枝點(diǎn)，其權(quán)

24、為W1W2在在W1W2，W3，Wt中選出兩個(gè)最小的權(quán)，銜接它們對(duì)中選出兩個(gè)最小的權(quán)，銜接它們對(duì)應(yīng)的結(jié)點(diǎn)應(yīng)的結(jié)點(diǎn)(不一定是樹葉不一定是樹葉)，得新分枝點(diǎn)及所帶的權(quán)，得新分枝點(diǎn)及所帶的權(quán)反復(fù)，直到構(gòu)成反復(fù)，直到構(gòu)成t1個(gè)分枝點(diǎn)，個(gè)分枝點(diǎn)，t片樹葉為止片樹葉為止例例16.4 求帶權(quán)求帶權(quán)2，2，3，3，5的最優(yōu)二叉樹的最優(yōu)二叉樹T。 解：生成最優(yōu)二叉樹的過(guò)程解：生成最優(yōu)二叉樹的過(guò)程最優(yōu)樹的權(quán)為：最優(yōu)樹的權(quán)為：W(T)=2323523232=34例例 求帶權(quán)為求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹的最優(yōu)樹. 解題過(guò)程由以下圖給出解題過(guò)程由以下圖給出W(T)=38定義定義16.10 設(shè)設(shè) =1

25、2n-1n是長(zhǎng)度為是長(zhǎng)度為n的符號(hào)串的符號(hào)串的前綴的前綴: 12k , k=1,2,n-1 前綴碼前綴碼: 1, 2, , m, 其中其中1, 2, , m為非空字為非空字符串符串, 且任何兩個(gè)互不為前綴且任何兩個(gè)互不為前綴2元前綴碼元前綴碼: 只出現(xiàn)兩個(gè)符號(hào)只出現(xiàn)兩個(gè)符號(hào)(如如0與與1)的前綴碼的前綴碼(2) 0,10,110, 1111, 10,01,001,110是前綴碼是前綴碼 0,10,010, 1010 不是前綴碼不是前綴碼例如例如(1) 1,00,011,0101,01001,01000是前綴碼。而是前綴碼。而 1,00,0101,0100,01001,01000不是前綴碼不是前

26、綴碼一棵一棵2元樹產(chǎn)生一個(gè)二元前綴碼元樹產(chǎn)生一個(gè)二元前綴碼:對(duì)每個(gè)分支點(diǎn)對(duì)每個(gè)分支點(diǎn), 假設(shè)關(guān)聯(lián)假設(shè)關(guān)聯(lián)2條邊條邊, 那么給左邊標(biāo)那么給左邊標(biāo)0, 右邊標(biāo)右邊標(biāo)1; 假設(shè)只關(guān)聯(lián)假設(shè)只關(guān)聯(lián)1條邊條邊, 那么可以給它標(biāo)那么可以給它標(biāo)0(左左), 也可以標(biāo)也可以標(biāo)1(右右). 將從樹根到每一片樹葉的通路上標(biāo)的數(shù)字組成的字符串記在將從樹根到每一片樹葉的通路上標(biāo)的數(shù)字組成的字符串記在樹葉處樹葉處, 所得的字符串構(gòu)成一個(gè)前綴碼所得的字符串構(gòu)成一個(gè)前綴碼.如右圖所示如右圖所示定理定理16.6 由一棵給定的二叉正那么樹，可以產(chǎn)生獨(dú)一的二元前綴由一棵給定的二叉正那么樹，可以產(chǎn)生獨(dú)一的二元前綴碼碼.例例16.5求

27、以下圖所示的二叉樹產(chǎn)生的前綴碼。求以下圖所示的二叉樹產(chǎn)生的前綴碼。產(chǎn)生的前綴碼為：產(chǎn)生的前綴碼為：01,11,000,0010,0011 例例 在通訊中，設(shè)八進(jìn)制數(shù)字出現(xiàn)的頻率如下：在通訊中，設(shè)八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用采用2元前綴碼元前綴碼, 求傳輸數(shù)字最少的求傳輸數(shù)字最少的2元前綴碼元前綴碼 (稱作最正確稱作最正確前前綴碼綴碼), 并求傳輸并求傳輸10n(n2)個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需需要多少個(gè)二進(jìn)制數(shù)字？假設(shè)用等長(zhǎng)的要多少個(gè)二進(jìn)制數(shù)字？假設(shè)用等長(zhǎng)的 (長(zhǎng)為長(zhǎng)為

28、3) 的碼字傳輸需的碼字傳輸需求求多少個(gè)二進(jìn)制數(shù)字多少個(gè)二進(jìn)制數(shù)字?解解 用用Huffman算法求以頻率算法求以頻率(乘以乘以100)為權(quán)的最優(yōu)為權(quán)的最優(yōu)2元樹元樹. 這這里里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最優(yōu)最優(yōu)2元樹如下圖元樹如下圖. 編碼編碼: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001傳傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為 W(T)=285.傳傳10n(n2)個(gè)所用二進(jìn)制數(shù)字的個(gè)數(shù)為個(gè)所用二進(jìn)制數(shù)字的個(gè)數(shù)為2.8510n, 而用等長(zhǎng)碼而用等長(zhǎng)碼(長(zhǎng)為長(zhǎng)為3)需求用需求用 310n