離散數(shù)學(xué)71-2

1、1第第7 7章章 樹(shù)及其應(yīng)用樹(shù)及其應(yīng)用2第第7 7章章 樹(shù)及其應(yīng)用樹(shù)及其應(yīng)用 7.1 無(wú)向樹(shù)無(wú)向樹(shù) 7.2 根樹(shù)及其應(yīng)用根樹(shù)及其應(yīng)用37.1 無(wú)向樹(shù)無(wú)向樹(shù) 7.1.1 無(wú)向樹(shù)的定義及其性質(zhì)無(wú)向樹(shù)的定義及其性質(zhì) 7.1.2 生成樹(shù)與基本回路和基本割集生成樹(shù)與基本回路和基本割集 7.1.3 最小生成樹(shù)最小生成樹(shù)4無(wú)向樹(shù)的定義無(wú)向樹(shù)的定義無(wú)向樹(shù)無(wú)向樹(shù): 連通無(wú)回路的無(wú)向圖連通無(wú)回路的無(wú)向圖平凡樹(shù)平凡樹(shù): 平凡圖平凡圖森林森林: 每個(gè)連通分支都是樹(shù)的非連通的無(wú)向圖每個(gè)連通分支都是樹(shù)的非連通的無(wú)向圖樹(shù)葉樹(shù)葉: 樹(shù)中度數(shù)為樹(shù)中度數(shù)為1的頂點(diǎn)的頂點(diǎn)分支點(diǎn)分支點(diǎn): 樹(shù)中度數(shù)樹(shù)中度數(shù) 2的頂點(diǎn)的頂點(diǎn)例如例如(a

2、)(b)5無(wú)向樹(shù)的性質(zhì)無(wú)向樹(shù)的性質(zhì)定理定理7.1 設(shè)設(shè)G=是是n階階m條邊的無(wú)向圖條邊的無(wú)向圖, 下面各命題是下面各命題是等價(jià)的：等價(jià)的：(1) G是樹(shù)是樹(shù)(連通無(wú)回路連通無(wú)回路);(2) G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑;(3) G是連通的且是連通的且m=n 1;(4) G中無(wú)回路且中無(wú)回路且m=n 1;(5) G中無(wú)回路中無(wú)回路, 但在任何兩個(gè)不相鄰的頂點(diǎn)之間加一條邊但在任何兩個(gè)不相鄰的頂點(diǎn)之間加一條邊 所得圖中有惟一的一條初級(jí)回路所得圖中有惟一的一條初級(jí)回路.(6) G是連通的且是連通的且G中任意一條邊均為橋中任意一條邊均為橋.P173(200)6定理定

3、理7.1的證明的證明(1)(2) 由連通性由連通性, 任意任意2個(gè)頂點(diǎn)之間有一條路徑個(gè)頂點(diǎn)之間有一條路徑. 又又, 假設(shè)假設(shè)某某2個(gè)頂點(diǎn)之間有個(gè)頂點(diǎn)之間有2條路徑條路徑, 則這則這2條路徑可組合成一條回條路徑可組合成一條回路路, 與樹(shù)的定義矛盾與樹(shù)的定義矛盾.(2)(3) 顯然連通顯然連通, 要證要證m=n 1. 對(duì)對(duì)n作歸納證明作歸納證明. 當(dāng)當(dāng)n=1時(shí)時(shí), 顯然顯然m=0, 結(jié)論成立結(jié)論成立. 假設(shè)當(dāng)假設(shè)當(dāng)n k(k 1)時(shí)結(jié)論成立時(shí)結(jié)論成立, 考慮考慮n=k+1. 任取一條邊任取一條邊e=(u,v), 它是它是u,v之間惟一的通路之間惟一的通路, 刪去刪去e, G被分成被分成2個(gè)連通分個(gè)

4、連通分支支, 設(shè)它們分別有設(shè)它們分別有n1, n2個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和m1, m2條邊條邊, n1 k, n2 k. 由歸納假設(shè)由歸納假設(shè), m1=n1-1, m2=n2-1, 得得m= m1+m2+1= n-1.7定理定理7.1的證明的證明(續(xù)續(xù))(3)(4) 假設(shè)有回路假設(shè)有回路, 任取一個(gè)回路任取一個(gè)回路, 刪去回路中的一條邊刪去回路中的一條邊, 所得圖仍是連通的所得圖仍是連通的. 重復(fù)這個(gè)做法重復(fù)這個(gè)做法, 直到?jīng)]有回路為止直到?jīng)]有回路為止, 得得到一棵樹(shù)到一棵樹(shù), 它有它有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)m-r條邊條邊, r0. 由由(1)(2)(3), 得得m-r =n-1, 矛盾矛盾.(4)(1) 只

5、需證只需證G連通連通. 假設(shè)假設(shè)G不連通不連通, 有有p(p1)個(gè)連通分支個(gè)連通分支.設(shè)第設(shè)第k個(gè)連通分支有個(gè)連通分支有nk個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和mk條邊條邊, 由由(1)(2)(3),mk= nk-1. 得到得到m= n-p, 矛盾矛盾.8定理定理7.1的證明的證明(續(xù)續(xù))(1)(5) 由由(1)(2), 任意任意2個(gè)不相鄰的頂點(diǎn)之間有一條惟個(gè)不相鄰的頂點(diǎn)之間有一條惟一的路徑一的路徑, 故在這故在這2個(gè)頂點(diǎn)之間添加一條新邊個(gè)頂點(diǎn)之間添加一條新邊, 必得到一條必得到一條惟一的初級(jí)回路惟一的初級(jí)回路.(5)(6) 首先首先, 任意任意2個(gè)不相鄰的頂點(diǎn)之間都有一條通路個(gè)不相鄰的頂點(diǎn)之間都有一條通路, 否

6、則在它們之間添加一條新邊不可能構(gòu)成回路否則在它們之間添加一條新邊不可能構(gòu)成回路, 故故G連通連通.其次其次, 若刪去一條邊若刪去一條邊G仍是連通的仍是連通的, 這條邊必在一條回路上這條邊必在一條回路上,與與G中無(wú)回路矛盾中無(wú)回路矛盾.(6)(1) G中無(wú)回路中無(wú)回路, 否則刪去回路上任意條邊否則刪去回路上任意條邊, G仍連通仍連通.9無(wú)向樹(shù)的性質(zhì)無(wú)向樹(shù)的性質(zhì)(續(xù)續(xù))定理定理7.2 非平凡的無(wú)向樹(shù)至少有兩片樹(shù)葉非平凡的無(wú)向樹(shù)至少有兩片樹(shù)葉 證證 設(shè)有設(shè)有n(n1)個(gè)頂點(diǎn)個(gè)頂點(diǎn), x片樹(shù)葉片樹(shù)葉, 由握手定理和定理由握手定理和定理7.1, 有有 解得解得 x 2.)(2)()1(2xnxvdni

7、10實(shí)例實(shí)例例例1 已知無(wú)向樹(shù)已知無(wú)向樹(shù)T中中, 有有1個(gè)個(gè)3度頂點(diǎn)度頂點(diǎn), 2個(gè)個(gè)2度頂點(diǎn)度頂點(diǎn), 其余頂其余頂點(diǎn)全是樹(shù)葉點(diǎn)全是樹(shù)葉. 試求樹(shù)葉數(shù)試求樹(shù)葉數(shù), 并畫(huà)出滿(mǎn)足要求的非同構(gòu)的無(wú)并畫(huà)出滿(mǎn)足要求的非同構(gòu)的無(wú)向樹(shù)向樹(shù). 解解 設(shè)有設(shè)有x片樹(shù)葉片樹(shù)葉,2 (2+x)=1 3+2 2+x解得解得x=3，故故T有有3片樹(shù)葉片樹(shù)葉.T的度數(shù)列為的度數(shù)列為1, 1, 1, 2, 2, 311實(shí)例實(shí)例例例2 畫(huà)出所有畫(huà)出所有6階非同構(gòu)的無(wú)向樹(shù)階非同構(gòu)的無(wú)向樹(shù)P201解解 5條邊條邊, 總度數(shù)等于總度數(shù)等于10可能的度數(shù)列可能的度數(shù)列:(1) 1,1,1,1,1,5(2) 1,1,1,1,2,4(3)

8、 1,1,1,1,3,3(4) 1,1,1,2,2,3(5) 1,1,2,2,2,2(1)(2)(3)(4a)(4b)(5)12生成樹(shù)生成樹(shù)定義定義7.2 設(shè)設(shè)G是無(wú)向連通圖是無(wú)向連通圖, 若若G的生成子圖的生成子圖T是一棵樹(shù)是一棵樹(shù), 則則稱(chēng)稱(chēng)T是是G的的生成樹(shù)生成樹(shù). G在在T中的邊稱(chēng)作中的邊稱(chēng)作T的的樹(shù)枝樹(shù)枝,不在不在T中的邊中的邊稱(chēng)作稱(chēng)作T的的弦弦. T的所有弦的集合的導(dǎo)出子圖稱(chēng)作的所有弦的集合的導(dǎo)出子圖稱(chēng)作T的的余樹(shù)余樹(shù)例如例如 圖中黑邊構(gòu)成生成樹(shù)圖中黑邊構(gòu)成生成樹(shù)紅邊構(gòu)成余樹(shù)紅邊構(gòu)成余樹(shù)注意注意: 余樹(shù)一般不是樹(shù)余樹(shù)一般不是樹(shù)13生成樹(shù)的存在性生成樹(shù)的存在性定理定理7.3 任何無(wú)向

9、連通圖都有生成樹(shù)任何無(wú)向連通圖都有生成樹(shù).證證 用破圈法用破圈法. 若圖中無(wú)圈若圖中無(wú)圈, 則圖本身就是自己的生成樹(shù)則圖本身就是自己的生成樹(shù). 否則刪去圈上的任一條邊否則刪去圈上的任一條邊, 不破壞連通性不破壞連通性, 重復(fù)進(jìn)行直到重復(fù)進(jìn)行直到無(wú)圈為止無(wú)圈為止, 得到圖的一棵生成樹(shù)得到圖的一棵生成樹(shù).推論推論1 設(shè)設(shè)n階無(wú)向連通圖有階無(wú)向連通圖有m條邊條邊, 則則m n 1. 推論推論2 設(shè)設(shè)n階無(wú)向連通圖有階無(wú)向連通圖有m條邊條邊, 則它的生成樹(shù)的余樹(shù)則它的生成樹(shù)的余樹(shù)有有m n+1條邊條邊.14基本回路與基本回路系統(tǒng)基本回路與基本回路系統(tǒng)定義定義7.3 設(shè)設(shè)G是是n階階m條邊的無(wú)向連通圖條

10、邊的無(wú)向連通圖, T是是G的一棵生成的一棵生成樹(shù)樹(shù), e1, e2, , em n+1為為T(mén)的弦的弦. G中僅含中僅含T的一條弦的一條弦er的圈的圈Cr稱(chēng)作對(duì)應(yīng)弦稱(chēng)作對(duì)應(yīng)弦er的的基本回路基本回路. 稱(chēng)稱(chēng)C1,C2, , Cm n+1為對(duì)應(yīng)為對(duì)應(yīng)T的的基本回路系統(tǒng)基本回路系統(tǒng)例例3 圖中紅邊為一棵生成樹(shù)圖中紅邊為一棵生成樹(shù), ,對(duì)應(yīng)它的基本回路系統(tǒng)為對(duì)應(yīng)它的基本回路系統(tǒng)為bce, fae, gaed 15基本割集與基本割集系統(tǒng)基本割集與基本割集系統(tǒng)定義定義7.4 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹(shù)的一棵生成樹(shù), e1 , e2 , , e n 1為為T(mén)的樹(shù)枝，的樹(shù)枝，Si是是G的只含樹(shù)

11、枝的只含樹(shù)枝ei , 其他邊都是弦其他邊都是弦的割集的割集, 稱(chēng)稱(chēng)Si為對(duì)應(yīng)樹(shù)枝為對(duì)應(yīng)樹(shù)枝ei 的的基本割集基本割集. 稱(chēng)稱(chēng)S1, S2, , Sn 1為對(duì)應(yīng)為對(duì)應(yīng)T的的基本割集系統(tǒng)基本割集系統(tǒng)例例4 圖中紅邊為一棵生成樹(shù)圖中紅邊為一棵生成樹(shù), ,對(duì)應(yīng)它的基本割集系統(tǒng)為對(duì)應(yīng)它的基本割集系統(tǒng)為a,f,g, e,b,f,g, c,b, d,g16最小生成樹(shù)最小生成樹(shù)圖圖G的每一條邊的每一條邊e附加一個(gè)實(shí)數(shù)附加一個(gè)實(shí)數(shù)w(e), 稱(chēng)作邊稱(chēng)作邊e的的權(quán)權(quán). 圖圖G連連同附加在邊上的權(quán)稱(chēng)作同附加在邊上的權(quán)稱(chēng)作帶權(quán)圖帶權(quán)圖, 記作記作G=. 設(shè)設(shè)H是是G的子圖的子圖, H所有邊的權(quán)的和稱(chēng)作所有邊的權(quán)的和稱(chēng)

12、作H的權(quán)的權(quán), 記作記作W(H). 最小生成樹(shù)最小生成樹(shù): 帶權(quán)圖權(quán)最小的生成樹(shù)帶權(quán)圖權(quán)最小的生成樹(shù)避圈法避圈法 (Kruskal) P205(1) 將所有非環(huán)邊按權(quán)從小到大排列將所有非環(huán)邊按權(quán)從小到大排列, 設(shè)為設(shè)為e1, e2, , em(2) 令令T = (3) For k=1 to m Do 若若ek與與T 中的邊不構(gòu)成回路中的邊不構(gòu)成回路, 則將則將ek加入加入T 中中17實(shí)例實(shí)例例例5 求圖的一棵最小生成樹(shù)求圖的一棵最小生成樹(shù)W(T)=38187.2 根樹(shù)及其應(yīng)用根樹(shù)及其應(yīng)用 7.2.1 根樹(shù)及其分類(lèi)根樹(shù)及其分類(lèi) 7.2.2 最優(yōu)樹(shù)與哈夫曼算法最優(yōu)樹(shù)與哈夫曼算法 7.2.3 最佳前

13、綴碼最佳前綴碼 7.2.4 根樹(shù)的周游及其應(yīng)用根樹(shù)的周游及其應(yīng)用 中序行遍法、前序行遍法和后序行遍法中序行遍法、前序行遍法和后序行遍法 波蘭符號(hào)法與逆波蘭符號(hào)法波蘭符號(hào)法與逆波蘭符號(hào)法19根樹(shù)的定義根樹(shù)的定義有向樹(shù)有向樹(shù): 略去方向后為無(wú)向樹(shù)的有向圖略去方向后為無(wú)向樹(shù)的有向圖根樹(shù)根樹(shù): 有一個(gè)頂點(diǎn)入度為有一個(gè)頂點(diǎn)入度為0, 其余的入度均為其余的入度均為1的非平凡的的非平凡的有向樹(shù)有向樹(shù)樹(shù)根樹(shù)根: 有向樹(shù)中入度為有向樹(shù)中入度為0的頂點(diǎn)的頂點(diǎn)樹(shù)葉樹(shù)葉: 有向樹(shù)中入度為有向樹(shù)中入度為1, 出度為出度為0的頂點(diǎn)的頂點(diǎn)內(nèi)點(diǎn)內(nèi)點(diǎn): 有向樹(shù)中入度為有向樹(shù)中入度為1, 出度大于出度大于0的頂點(diǎn)的頂點(diǎn)分支點(diǎn)分支

14、點(diǎn): 樹(shù)根與內(nèi)點(diǎn)的總稱(chēng)樹(shù)根與內(nèi)點(diǎn)的總稱(chēng)頂點(diǎn)頂點(diǎn)v的層數(shù)的層數(shù): 從樹(shù)根到從樹(shù)根到v的通路長(zhǎng)度的通路長(zhǎng)度樹(shù)高樹(shù)高: 有向樹(shù)中頂點(diǎn)的最大層數(shù)有向樹(shù)中頂點(diǎn)的最大層數(shù)20實(shí)例實(shí)例根樹(shù)的畫(huà)法根樹(shù)的畫(huà)法: :樹(shù)根放最上方樹(shù)根放最上方, ,省去所有有向邊上的箭頭省去所有有向邊上的箭頭右圖中右圖中 a是樹(shù)根是樹(shù)根 b,e,f,h,i是樹(shù)葉是樹(shù)葉 c,d,g是內(nèi)點(diǎn)是內(nèi)點(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ù)高為421家族樹(shù)家族樹(shù)把根樹(shù)看作一棵把根樹(shù)看作一棵家族樹(shù)家族樹(shù):若頂點(diǎn)若頂點(diǎn)a鄰接到頂點(diǎn)鄰接到頂點(diǎn)b, 則稱(chēng)則

15、稱(chēng)b是是a的的兒子兒子, a是是b的的父親父親若若b和和c為同一個(gè)頂點(diǎn)的兒子為同一個(gè)頂點(diǎn)的兒子, 則稱(chēng)則稱(chēng)b和和c是是兄弟兄弟若若a b且且a可達(dá)可達(dá)b, 則稱(chēng)則稱(chēng)a是是b的的祖先祖先, b是是a的的后代后代設(shè)設(shè)v為根樹(shù)的一個(gè)頂點(diǎn)且不是樹(shù)根為根樹(shù)的一個(gè)頂點(diǎn)且不是樹(shù)根, 稱(chēng)稱(chēng)v及其所有后代的導(dǎo)及其所有后代的導(dǎo)出子圖為以出子圖為以v為根的為根的根子樹(shù)根子樹(shù)將根樹(shù)每一層上的頂點(diǎn)規(guī)定次序后稱(chēng)作將根樹(shù)每一層上的頂點(diǎn)規(guī)定次序后稱(chēng)作有序樹(shù)有序樹(shù)22根樹(shù)的分類(lèi)根樹(shù)的分類(lèi)r元樹(shù)元樹(shù):根樹(shù)的每個(gè)分支點(diǎn)至多有根樹(shù)的每個(gè)分支點(diǎn)至多有r個(gè)兒子個(gè)兒子r元正則樹(shù)元正則樹(shù): 根樹(shù)的每個(gè)分支點(diǎn)恰有根樹(shù)的每個(gè)分支點(diǎn)恰有r個(gè)兒子個(gè)

16、兒子r元完全正則樹(shù)元完全正則樹(shù): 所有樹(shù)葉層數(shù)相同的所有樹(shù)葉層數(shù)相同的r元正則樹(shù)元正則樹(shù)r元有序樹(shù)元有序樹(shù): 有序的有序的r元樹(shù)元樹(shù)r元正則有序樹(shù)元正則有序樹(shù): 有序的有序的r元正則樹(shù)元正則樹(shù)r元完全正則有序樹(shù)元完全正則有序樹(shù): 有序的有序的r元完全正則樹(shù)元完全正則樹(shù)23最優(yōu)最優(yōu)2元樹(shù)元樹(shù)定義定義7.10 設(shè)設(shè)2元樹(shù)元樹(shù)T有有t片樹(shù)葉片樹(shù)葉v1, v2, , vt, 樹(shù)葉的權(quán)分別為樹(shù)葉的權(quán)分別為w1, w2, , wt, 稱(chēng)稱(chēng) 為為T(mén)的權(quán)的權(quán), 記作記作W(T), 其中其中l(wèi)(vi)是是vi的層數(shù)的層數(shù). 在所有有在所有有t片樹(shù)葉片樹(shù)葉, 帶權(quán)帶權(quán)w1, w2, , wt 的的 2元元樹(shù)中樹(shù)中

17、, 權(quán)最小的權(quán)最小的2元樹(shù)稱(chēng)為元樹(shù)稱(chēng)為最優(yōu)最優(yōu)2元樹(shù)元樹(shù))()(1itiivlwtW 例如例如134 561345613456W(T1)=47W(T2)=54W(T3)=4324求最優(yōu)求最優(yōu)2元樹(shù)的算法元樹(shù)的算法哈夫曼哈夫曼(Huffman)算法算法給定實(shí)數(shù)給定實(shí)數(shù)w1, w2, , wt 作作t片樹(shù)葉片樹(shù)葉, 分別以分別以w1, w2, , wt為權(quán)為權(quán) 在所有入度為在所有入度為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)之和

18、重復(fù)重復(fù), 直到只有直到只有1個(gè)入度為個(gè)入度為0 的頂點(diǎn)為止的頂點(diǎn)為止 W(T)等于所有分支點(diǎn)的權(quán)之和等于所有分支點(diǎn)的權(quán)之和25實(shí)例實(shí)例例例1 求以求以1,3,4,5,6為權(quán)的最優(yōu)為權(quán)的最優(yōu)2元樹(shù)元樹(shù), 并計(jì)算它的權(quán)并計(jì)算它的權(quán)解解134(a)13448(b)134456811(c)1344 5681119(d)W(T)=4+8+11+19=4226最佳前綴碼最佳前綴碼定義定義7.11 設(shè)設(shè) = 1 2 n-1 n是長(zhǎng)度為是長(zhǎng)度為n的符號(hào)串的符號(hào)串, 1 2 k稱(chēng)作稱(chēng)作 的長(zhǎng)度為的長(zhǎng)度為k的的前綴前綴, k=1,2,n-1. 若非空字符串若非空字符串 1, 2, , m中任何兩個(gè)互不為前綴中任

19、何兩個(gè)互不為前綴, 則稱(chēng)則稱(chēng) 1, 2, , m為為前綴碼前綴碼只出現(xiàn)兩個(gè)符號(hào)只出現(xiàn)兩個(gè)符號(hào)(如如0與與1)的前綴碼稱(chēng)作的前綴碼稱(chēng)作2元前綴碼元前綴碼例如例如 0,10,110, 1111, 10,01,001,110是是2元前綴碼元前綴碼 0,10,010, 1010 不是前綴碼不是前綴碼27用用2元樹(shù)產(chǎn)生元樹(shù)產(chǎn)生2元前綴碼的方法元前綴碼的方法對(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)的

20、數(shù)字組成的字將從樹(shù)根到每一片樹(shù)葉的通路上標(biāo)的數(shù)字組成的字符串記在樹(shù)葉處符串記在樹(shù)葉處, 所得的字符串構(gòu)成一個(gè)前綴碼所得的字符串構(gòu)成一個(gè)前綴碼.P209例如例如前綴碼前綴碼00, 11, 011, 010028實(shí)例實(shí)例例例2 在通信中在通信中,設(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元前綴碼元前綴碼 (稱(chēng)作稱(chēng)作最佳最佳前綴碼前綴碼), 并求傳輸并求傳輸100個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需個(gè)按上述比例出現(xiàn)的八進(jìn)

21、制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的 (長(zhǎng)為長(zhǎng)為3) 的碼字傳輸需的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字要多少個(gè)二進(jìn)制數(shù)字?解解 用用Huffman算法求以頻率算法求以頻率(乘以乘以100)為權(quán)的最優(yōu)為權(quán)的最優(yōu)2元樹(shù)元樹(shù). 這里這里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.29實(shí)例實(shí)例(續(xù)續(xù))編碼編碼:0-01 1-112-0013-1004-1015-00016-000007-00001傳傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字需個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字需W(T)=285個(gè)二進(jìn)制數(shù)個(gè)二進(jìn)制數(shù)字字, 用等長(zhǎng)碼用等長(zhǎng)碼(長(zhǎng)為長(zhǎng)為3)需要用需要用 300個(gè)數(shù)字個(gè)數(shù)字.w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=2530根樹(shù)的周游及其應(yīng)用根樹(shù)的周游及其應(yīng)用對(duì)一棵根樹(shù)的每個(gè)頂點(diǎn)訪(fǎng)問(wèn)一次且僅訪(fǎng)問(wèn)一次稱(chēng)作對(duì)根對(duì)一棵根樹(shù)的每個(gè)頂點(diǎn)訪(fǎng)問(wèn)一次且僅訪(fǎng)問(wèn)一次稱(chēng)作對(duì)根樹(shù)的樹(shù)的行遍行遍或或周游周游 行遍行遍2元有序正則樹(shù)的方式：元有序正則樹(shù)的方式： 中序行遍法中序行遍法: 左子樹(shù)、樹(shù)根、右子樹(shù)左子樹(shù)、樹(shù)根、右子樹(shù) 前序行遍法前序行遍法:樹(shù)根、左子樹(shù)、右子樹(shù)樹(shù)根、左子樹(shù)、右子樹(shù) 后序行遍法后