【正文】 （提示：哈夫曼樹中無度數(shù)為 1的結(jié)點(diǎn) ,則利用教材第 124頁二叉樹的性質(zhì) 3即可得證） C語言實(shí)現(xiàn)根據(jù) n個(gè)字符（結(jié)點(diǎn)）的權(quán)值求哈夫曼樹及 n個(gè)字符的哈夫曼編碼的子程序，并編制主程序main{}調(diào)用該子程序?qū)ζ湔_性進(jìn)行驗(yàn)證。 樹求解的算法思想： 3個(gè)步驟。cd[start])。 c=f, f=HT[f].parent) { // 從葉子到根逆向求編碼 if (HT[f].lchild==c) cd[ start] = “0”。 i=n。 //申請(qǐng) n個(gè)字符編碼的頭指針數(shù) 組的存儲(chǔ)空間 cd = (char *)malloc(n*sizeof(char))。 HT[i].rchild = s2。 // 在 i1棵子樹中也即 HT[1..i1]中選擇無父親 (parent為 0) //且權(quán)值最小的兩個(gè)結(jié)點(diǎn) (其序號(hào)分別為 s1和 s2)。 i=m。 HT[i].parent=0。 HT[i].rchild=0。 i=n。 if (n=1) return。 HC[i] = (char *)malloc((編碼長(zhǎng)度 +1)*sizeof(char))。 }HTNode , * HuffmanTree 。 //存放表中元素的值 int next 。 三、實(shí)例 已知某通信用電文僅由 A、 B、 C、 D這 4個(gè)字符構(gòu)成，其出現(xiàn)的頻率分別為： 2，請(qǐng)給出它們的哈夫曼編碼，要求寫出相應(yīng)的哈夫曼樹。 例如： 對(duì)于剛才的 4個(gè)字符的編碼問題，可以按如下不等長(zhǎng)編碼方案進(jìn)行編碼： A: 0 B: 00 C: 1 D: 01 問題： 譯碼時(shí)可能出現(xiàn)多意性，即譯碼不唯一： 則對(duì)于電文“ ABACCDA”的二進(jìn)制電碼為： 000011010 總長(zhǎng)為 9位 二、哈夫曼樹及其應(yīng)用 ② 壓縮編碼： 例如： 對(duì)于剛才的 4個(gè)字符的編碼問題，可以按如下不等長(zhǎng)編碼方案進(jìn)行編碼： A: 0 B: 00 C: 1 D: 01 問題： 譯碼時(shí)可能出現(xiàn)多意性，即譯碼不唯一： 則對(duì)于電文“ ABACCDA”的二進(jìn)制電碼為： 000011010 總長(zhǎng)為 9位 二、哈夫曼樹及其應(yīng)用 ② 壓縮編碼： 例如： 對(duì)于剛才的 4個(gè)字符的編碼問題，可以按如下不等長(zhǎng)編碼方案進(jìn)行編碼： A: 0 B: 00 C: 1 D: 01 問題： 譯碼時(shí)可能出現(xiàn)多意性，即譯碼不唯一。 7位二進(jìn)制數(shù)可以為 27個(gè)不同的英文字符編碼。 a 40 b 30 c 5 d 10 e 15 15 求解過程 二、哈夫曼樹及其應(yīng)用 ③ 實(shí)例：已知有 5個(gè)葉子結(jié)點(diǎn)的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 步驟 3:判斷 F中是否只有唯一的一棵二叉樹。 有關(guān)概念 二、哈夫曼樹及其應(yīng)用 實(shí)例： 已知某二叉樹的四個(gè)葉子結(jié)點(diǎn) a,b,c,d分別帶權(quán) 7， 5， 2， 4，則可構(gòu)造出有如下幾種不同形式的二叉樹： a a a 7 7 7 b 5 b 5 c 2 d 4 c 2 d 4 b 5 c 2 d 4 樹的帶權(quán)路徑長(zhǎng)度為： WPL=2*7+2*5+2*2+2*4=36 樹的帶權(quán)路徑長(zhǎng)度為： WPL=2*4+3*7+3*5+1*2=46 樹的帶權(quán)路徑長(zhǎng)度為： WPL=1*7+2*5+3*2+3*4=35 有關(guān)概念 二、哈夫曼樹及其應(yīng)用 ⑤ 哈夫曼樹的定義： 設(shè)有 n個(gè)葉子結(jié)點(diǎn)的二叉樹，其第 i個(gè)葉子結(jié)點(diǎn)的權(quán)值為 wi(i=1,2,3,...n),且第 i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度為 li ,則使 WPL=∑wi*li最小的二叉樹稱為“最優(yōu) 二叉樹”或稱為“ 哈夫曼樹 ”。 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績(jī)數(shù)據(jù)分布情況表 方法 1： a60 打印 bad“ yes a70 no 打印 pass yes a80 no 打印 general yes a90 no 打印 good yes 打印 excellent no 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 共做 31500次比較 讀取一個(gè)學(xué)生成績(jī) → a 循環(huán)一萬次 i=1 i=10000 N 結(jié)束 i = i+1 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績(jī)數(shù)據(jù)分布情況表 方法 2： a80 打印 bad yes a90 no yes no a70 yes no a60 yes no 打印“ good 打印 excellent 打印 pass 打印 general 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 讀取一個(gè)學(xué)生成績(jī) → a 循環(huán)一萬次 i=1 i=10000 N 結(jié)束 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績(jī)數(shù)據(jù)分布情況表 方法 2： a80 打印 bad yes a90 no yes no a70 yes no a60 yes no 打印“ good 打印 excellent 打印 pass 打印 general 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 共做 22022次比較 讀取一個(gè)學(xué)生成績(jī) → a 循環(huán)一萬次 i=1 i=10000 N 結(jié)束 思考： 如何找到一棵 最優(yōu)的 判斷樹使得編寫出來的程序的運(yùn)行時(shí)間是最高效的？ 有關(guān)概念 ① 結(jié)點(diǎn)的路徑長(zhǎng)度： 從根結(jié)點(diǎn)沿某條路徑到某結(jié)點(diǎn)途中所經(jīng)歷的弧的條數(shù)稱為該結(jié)點(diǎn)的路徑長(zhǎng)度。 二、哈夫曼樹及其應(yīng)用 ② 樹的路徑長(zhǎng)度： 從根結(jié)點(diǎn)到每一個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和。 i=1 n 求解過程 二、哈夫曼樹及其應(yīng)用 ① 問題： 已知 n個(gè)葉子的權(quán)值為 {w1,w2,...wn}，構(gòu)造一棵最優(yōu)二叉樹。若是，則求解過程結(jié)束；否則，轉(zhuǎn)步驟 2。 a 40 b 30 c 5 d 10 e 15 15 30 求解過程 二、哈夫曼樹及其應(yīng)用 ③ 實(shí)例：已知有 5個(gè)葉子結(jié)點(diǎn)的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 下面為討論問題簡(jiǎn)單起見，假設(shè)被編碼的字符集中只有 4個(gè)（即 22個(gè)）不同字符，故只要兩位二進(jìn)制數(shù)即可完成編碼。 則對(duì)于電文“ ABACCDA”的二進(jìn)制電碼為：