【導(dǎo)讀】樹形結(jié)構(gòu)是以分支關(guān)系來定義的層次結(jié)構(gòu)。–人類社會的族譜、家譜、行政區(qū)域劃分管理；–各種社會組織機(jī)構(gòu)；–D中其余數(shù)據(jù)元素都有且只有一個前趨；（子樹），或無后繼（葉結(jié)點(diǎn)）；樹是由n個具有相同特性的數(shù)據(jù)元素組成的集合。一棵非空樹T必須滿足：。1）其中有一個特定的元素稱為T的根root。，Tm，其中每個子集都是樹。向子樹的分支稱為結(jié)點(diǎn)。其孩子結(jié)點(diǎn)的父結(jié)點(diǎn)。依次類推，子結(jié)點(diǎn)的層次總比父結(jié)點(diǎn)。左向右有序的，則稱該樹為有序樹。–每個結(jié)點(diǎn)至多只有兩個子樹;子樹和右子樹，而樹則無此區(qū)分；–二叉樹的分支度一定為0、1或2，結(jié)點(diǎn)都在同一層上，則稱其為滿二叉樹。葉結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層上。深度的差值，稱為該結(jié)點(diǎn)的平衡因子。左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；數(shù)的2倍，即2×2i-2=2i-1。深度為h的二叉樹上至多含2h-1個結(jié)點(diǎn)(h≥1)。

　　

【正文】 樹 。 ????niii lwW P L1下一頁 上一頁 停止放映 [第 74頁 /91] Huffman樹舉例 以下有三棵樹： （ a） （ b） （ c） a b c d a b c d a c b d 7 7 7 5 5 5 2 2 2 4 4 4 WPLa =7x2+5x2+2x2+4x2 = 36 WPLb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 √ 事實(shí)證明按哈夫曼樹構(gòu)造二叉樹，可得到很好的特性，應(yīng)用于實(shí)際問題，可提高處理效率。 下一頁 上一頁 停止放映 [第 75頁 /91] 應(yīng)用舉例 由統(tǒng)計規(guī)律可知，考試成績的分布符合正態(tài)分布： 1 1 0 分?jǐn)?shù) 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100 比例數(shù) 根據(jù)正態(tài)分布規(guī)律，在 60～ 90之間的分?jǐn)?shù)占 85%，而不及格和優(yōu)秀是少數(shù)。 下一頁 上一頁 停止放映 [第 76頁 /91] 將百分制轉(zhuǎn)換成五分制 ? 判定樹比較： a60? a70? a80? a90? 不及格 及格 中等 良好 優(yōu)秀 Y Y Y Y N N N N a80? a70? a90? a60? 不及格 優(yōu)秀 良好 中等 中等 及格 不及格 Y Y Y N N N N Y (A) (B) 若輸入 1萬個數(shù)據(jù)，按 A的判定過程進(jìn)行操作，約需比較 ，而按 B比較 ,則僅需 。 下一頁 上一頁 停止放映 [第 77頁 /91] 構(gòu)造 Huffman樹 構(gòu)造 Huffman樹算法步驟： Step1 將 n個帶權(quán)值 wi（ i≤n ）的結(jié)點(diǎn)構(gòu)成 n棵二叉樹的集合 T={T1， T2， …… ， Tn}，每棵二叉樹只有一個根結(jié)點(diǎn)。 Step2 在 T中選取兩個權(quán)值最小的結(jié)點(diǎn)作為左右子樹，構(gòu)成一個新的二叉樹，其根結(jié)點(diǎn)的權(quán)值取左右子樹權(quán)值之和； Step3 在 T中刪除這兩棵樹，將新構(gòu)成的樹加入到 T中； Step4 重復(fù) 2）、 3）步的操作，直到 T中只含一棵樹為止，該樹就是 Huffman樹。 下一頁 上一頁 停止放映 [第 78頁 /91] 假定有一段報文由 a、 b、 c、 d四個字符構(gòu)成，它們的使用頻率比為 6﹕4﹕2﹕1 ，則用 a、 b、 c、 d作為葉子結(jié)點(diǎn)構(gòu)造哈夫曼樹的過程如圖所示。 若二叉樹中的左分支代表 0，右分支代表 1,則 a、 b、c、 d的哈夫曼編碼分別為 0、 1 111。 下一頁 上一頁 停止放映 [第 79頁 /91] 構(gòu)造 Huffman樹舉例 以權(quán)值分別為 7， 5， 2， 4的結(jié)點(diǎn) a、 b、 c、 d構(gòu)造Huffman樹。 T= { a b c d } c d T3 2 4 6 b T3 T2 6 5 11 b T2 6 5 11 c d 2 4 11 18 a T2 7 T1 6 18 a 7 T1 b T3 T2 5 11 18 a 7 T1 b 5 11 c d 2 6 4 （ d） T={ T1 } （ c） T= { a T2 } （ b） T= { a b T3 } （ a） T= { a b c d } 代入 T2 代入T3 示例 下一頁 上一頁 停止放映 [第 80頁 /91] Huffman編碼 編碼 ： 用二進(jìn)制數(shù)的不同組合來表示字符的方法。 前綴編碼 ：一種非等長度的編碼 (任一個字符的編碼都不是另一個字符編碼的前綴 )。 a 0 b 0 1 c d 0 1 1 編碼： a（ 0） b（ 01） c（ 011） d（ 111） 方法約定： 1）左分支為‘ 0’ 2）右分支為‘ 1’ 3） 由葉到根 路徑上字符組成的二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼。 Huffman編碼 ：一種非等長度的編碼。以給定權(quán)值的結(jié)點(diǎn)構(gòu)造 Huffman樹，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼為 Huffman編碼。 下一頁 上一頁 停止放映 [第 81頁 /91] Huffman編碼舉例 在某系統(tǒng)的通信聯(lián)絡(luò)中可能出現(xiàn) 8種字符，其頻率分別為 、 、 、 、 、 、 ，設(shè)權(quán)值分別為 {5， 29， 7， 8， 14，23， 3， 11}， n=8，其 Huffman樹為： 0 0 0 0 0 0 0 1 1 1 1 1 1 1 5 3 7 8 14 29 11 23 42 58 100 Huffman編碼為： A 5 0110 B 29 01 C 7 0111 D 8 1111 E 14 011 F 23 00 G 3 1110 H 11 010 下一頁 上一頁 停止放映 [第 82頁 /91] 【 例 25】 假定編碼系統(tǒng)中有五個字符 X、 S、 D、 E、A，它們的使用頻率比為 2﹕9﹕5﹕7﹕8 ，以這些頻率值作葉子的權(quán)構(gòu)造哈夫曼樹，并輸出哈夫曼編碼。 2 5 7 o o o o 8 9 o o o o o 0 0 1 1 1 0 0 1 下一頁 上一頁 停止放映 [第 83頁 /91] 最小生成樹 該問題是構(gòu)造連通圖的最小代價生成樹問題。一棵生成樹的代價就是樹上各邊（?。┑拇鷥r之和。 考慮一個通信網(wǎng)的建設(shè)問題 。 若要在 n個城市間建立通信聯(lián)絡(luò)網(wǎng) ， 則只需 n1條線路 。 但在 n個城市間 ， 最多可能架設(shè) n*（ n1） /2條線路 ， 選擇哪 n1條線路 ， 使費(fèi)用最少 。 普里姆 （ Prim） 算法 克魯斯卡爾 （ Kruskal） 算法 下一頁 上一頁 停止放映 [第 84頁 /91] 實(shí)例 下一頁 上一頁 停止放映 [第 85頁 /91] （ 1） 普里姆算法 假定 G={ V, E }為連通網(wǎng)絡(luò) ， 其中 V為頂點(diǎn)集合 ， E為帶權(quán)邊集合 。 設(shè)置生成樹頂點(diǎn)集合 U，最初它只包含某一個頂點(diǎn) 。 設(shè)置生成樹邊集合 T，最初為空集 。 而后考察這樣的邊 ， 它的一個頂點(diǎn) u∈U ， 另一個頂點(diǎn) v∈V U， 每次從所有這樣的邊中選擇權(quán)值最小的邊 (u, v)加入集合 T， 并把頂點(diǎn) v加入到集合 U中 。 如此不斷重復(fù) ， 直到所有頂點(diǎn)都加入到集合 U中為止 。 下一頁 上一頁 停止放映 [第 86頁 /91] 下一頁 上一頁 停止放映 [第 87頁 /91] 普里姆（ Prim）算法舉例 1 2 3 4 5 6 8 7 2 1 4 3 5 7 6 8 11 10 9 12 U={1}， VU={2， 3， 4， 5， 6， 7， 8} 1 2 2 1 2 4 2 1 4 7 3 （ 1） （ 2） （ 3） (1) U={1,2},VU={3,4,5,6,7,8} (2) U={1,2,4},VU={3,5,6,7,8} (3) U={1,2,4,7},VU={3,5,6,8} 例子 下一頁 上一頁 停止放映 [第 88頁 /91] 普里姆（ Prim）算法舉例 (續(xù) ) 4 7 5 3 5 （ 4） 7 6 （ 5） 6 (4) U={1,2,4,7,5} , VU={3,6,8} (5) U={1,2,4,7,5,6}, VU={3,8} (6) U={1,2,4,7,5,6,3}, VU={8} (7) U={1,2,4,7,5,6,3,8), VU={ } 4 3 （ 7） 8 3 6 5 4 7 2 2 1 3 6 5 8 9 1 5 5 （ 6） 4 7 6 3 6 3 5 5 8 下一頁 上一頁 停止放映 [第 89頁 /91] 下一頁 上一頁 停止放映 [第 90頁 /91] （ 2） 克魯斯卡爾算法 假定 G={ V, E }為連通網(wǎng)絡(luò) ， 其中 V為頂點(diǎn)集合 ， E為帶權(quán)邊集合 。 先構(gòu)造一個包含所有頂點(diǎn) ， 沒有邊的非連通圖T={ V, {} }， 圖中每個頂點(diǎn)自成一個連通分量 。 當(dāng)在 E中選到一條具有最小權(quán)值的邊時 ,若該邊的兩個頂點(diǎn)落在 T的不同的連通分量上 ， 則將此邊加入到 T中；否則將此邊舍去 ， 重新選擇一條權(quán)值最小的邊 。 如此重復(fù)下去 ， 直到所有頂點(diǎn)在同一個連通分量上為止 。 下一頁 上一頁 停止放映 [第 91頁 /91] 克魯斯卡爾（ Kruskal）算法舉例 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 2 5 1 3 4 6 1 2 3 (4) 1 3 1 4 6 2 (3) 1 2 3 4 5 6 (1) 1 3 (2) 1 下一頁 上一頁 停止放映 [第 92頁 /91] 克魯斯卡爾（ Kruskal）算法舉例 (續(xù)） 1 2 3 4 5 6 (5) 1 2 3 4 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 1 3 2 5 6 4 1 2 4 3 5 （ 6） 例子 下一頁 上一頁 停止放映 [第 93頁 /91] 結(jié)束語 歡迎參加到中心網(wǎng)站 《 軟件開發(fā)技術(shù)基礎(chǔ) 》課程的學(xué)習(xí)討論中來。 中心網(wǎng)址： 課件下載地址 : 我的 Email地址 : 答疑安排： 每星期五下午： 3:00～ 6:00 地點(diǎn)： 計教中心 505房間