數(shù)據(jù)結(jié)構(gòu)第六章樹(shù)和二叉樹(shù)-資料下載頁(yè)
2025-10-08 15:26本頁(yè)面
【導(dǎo)讀】如果n>0,稱(chēng)為非空樹(shù),對(duì)于非空樹(shù),有且僅有一個(gè)特定的稱(chēng)為根的。如果n>1，則除根以外的其它結(jié)點(diǎn)劃分為m(m>0)個(gè)互不相交的有限集。,Tm，其中每個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。每個(gè)結(jié)點(diǎn)都有唯一的直接前驅(qū)，但可能有多個(gè)后繼。T1,T2,T3都是根A的子樹(shù)，且本身也是一棵樹(shù)。對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)而言，其子樹(shù)的。二叉樹(shù)的子樹(shù)有左右之分。二叉樹(shù)性質(zhì)２：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。左子樹(shù)深度與右子樹(shù)深度相等或大１。顯然，二叉樹(shù)的結(jié)點(diǎn)必須按某種次序分別存入數(shù)組的各個(gè)單元，對(duì)于完全二叉樹(shù)來(lái)說(shuō)，可以采用“以編號(hào)為地址”的方法，將。完全二叉樹(shù)的順序表示。對(duì)于非完全二叉樹(shù)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更合適。TElemType可以是任何相應(yīng)的數(shù)據(jù)類(lèi)型如int、float或char等。
【正文】 轉(zhuǎn)換而成。右子樹(shù) RB是由森林 F中除樹(shù) T1外余下部分轉(zhuǎn)換而成。 對(duì)應(yīng)的二叉樹(shù) F G C E B D A J I K H T1 T2 T3 F G C E B D A K H I J 三棵樹(shù)的森林 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 640 樹(shù)與森林 ? 樹(shù)的遍歷 對(duì)樹(shù)的遍歷主要有兩種：先根（次序）遍歷、后根（次序）遍歷 ? 先根（次序）遍歷：當(dāng)樹(shù)非空時(shí) 1. 訪問(wèn)根結(jié)點(diǎn) 2. 依次先根遍歷根的各棵子樹(shù) ? 輸出結(jié)果： ABEFCDG ? 后根（次序）遍歷：當(dāng)樹(shù)非空時(shí) 1. 依次后根遍歷根的各棵子樹(shù) 2. 訪問(wèn)根結(jié)點(diǎn) ? 輸出結(jié)果： EFBCGDA C E F G B D A 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 641 樹(shù)與森林 ? 與二叉樹(shù)遍歷的關(guān)系 當(dāng)采用孩子兄弟表示法表示樹(shù)時(shí)： ? 樹(shù)的先根遍歷，與樹(shù)對(duì)應(yīng)的二叉樹(shù)的先根遍歷完全相同 ? 樹(shù)的后根遍歷，與樹(shù)對(duì)應(yīng)的二叉樹(shù)的中根遍歷完全相同 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 642 赫夫曼樹(shù)及其應(yīng)用 ? 赫夫曼 樹(shù) 赫夫曼 樹(shù)（ Huffman）樹(shù)也稱(chēng)最優(yōu)二叉樹(shù)，是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)，在判定、查找及數(shù)據(jù)壓縮技術(shù)中有著廣泛的應(yīng)用。 ? 基本術(shù)語(yǔ) ? 路徑 ：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑 ? 路徑長(zhǎng)度 ：路徑上的分支數(shù)目 ? 樹(shù)的路徑長(zhǎng)度 ：從樹(shù)根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和 ? 帶權(quán)路徑長(zhǎng)度 ：從結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)權(quán)的乘積 ? 樹(shù)的帶權(quán)路徑長(zhǎng)度 (WPL)：樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 ? 最優(yōu)二叉樹(shù) ：假設(shè)二叉樹(shù)有 n個(gè)葉子，其每個(gè)葉子結(jié)點(diǎn)權(quán)為 wi，則帶權(quán)路徑長(zhǎng)度 WPL最小的二叉樹(shù)稱(chēng)為最優(yōu)二叉樹(shù)。赫夫曼(Huffman)樹(shù)就是一棵最優(yōu)二叉樹(shù) 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 643 赫夫曼樹(shù)及其應(yīng)用 ? 例：下圖所示的樹(shù)路徑長(zhǎng)度為： 2*1+3*2+1*3=11 下圖所示的樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL = 2*5+3*3+2*4=27 A D B F C G E 5 4 3 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 644 赫夫曼樹(shù)及其應(yīng)用 ? 構(gòu)造 Huffman樹(shù) ? 在 Huffman樹(shù)中，權(quán)值最大的結(jié)點(diǎn)離根最近 ? 權(quán)值最小的結(jié)點(diǎn)離根最遠(yuǎn) ? Huffman樹(shù)算法 n個(gè)權(quán)值 (w1, w2, ?, w n)構(gòu)成 n棵二叉樹(shù)的集合F={T1, T2, ?, T n}，其中每棵二叉樹(shù) Ti中只有一個(gè)帶樹(shù)為 Ti的根結(jié)點(diǎn) F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置其根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)權(quán)值之和 F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入 F中 2, 3，直到 F只含一棵樹(shù)為止 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 645 赫夫曼樹(shù)及其應(yīng)用 ? 構(gòu)造 Huffman樹(shù)示例 F : {7} {5} {2} {4} F : {7} {5} {6} F : {7} {11} 7 5 2 4 1. 初始 2. 合并 {2} {4} 7 5 2 4 6 F : {18} 11 7 5 2 4 6 3. 合并 {5} {6} 5 4. 合并 {7} {11} 2 7 4 6 11 18 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 646 赫夫曼樹(shù)及其應(yīng)用 ? Huffman編碼 設(shè)給出一段報(bào)文： GOOD_GOOD_GOOD_GOOOOOOOO_OFF，字符集合是 {O,G,_,D,F}，各個(gè)字符出現(xiàn)的頻度 (次數(shù) )是 W={15,4,4,3,2}。 ? 等長(zhǎng)編碼 ：若采用等長(zhǎng)辦法給每個(gè)字符編碼： O:000 G:001 _:010 D:011 F:100 則總編碼長(zhǎng)度為 (15+4+4+3+2) * 3 = 出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度。各字符出現(xiàn)概率為 { 15/28,4/28,4/28,3/28,2/28 }, 取整數(shù)為{15,4,4,3,2}如果規(guī)定， Huffman 樹(shù)的 左子樹(shù)小于右子樹(shù) ，則可構(gòu)成右 圖所示 Huffman樹(shù)。 4 15 4 2 3 G _ F D O 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 647 赫夫曼樹(shù)及其應(yīng)用 ? 令左孩子分支為編碼‘ 0’ ，右孩子分支為編碼‘ 1’ ? 將根結(jié)點(diǎn)到葉子結(jié)點(diǎn)路徑上的分支編碼，組合起來(lái)，作為該字符的 Huffman碼，則可得到：字母 O:1 _:011 G:010 D:001 F:000 ? 則總編碼長(zhǎng)度為 15*1+(2+3+4+4)*3 = 54 84 ? Huffman是一種前綴編碼，解碼時(shí)不會(huì)混淆 ? 如 GOOD編碼為： 01011001 4 15 4 2 3 0 0 0 0 1 1 1 1 G _ F D O 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 648 習(xí)題 ? 本章習(xí)題參見(jiàn)教師網(wǎng)頁(yè)：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1