【正文】 N N Y Y Y Y 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 (b)WPL=5x3+15x3+40x2+30x2+10x2=220 構(gòu)造赫夫曼樹(shù)的算法思想 ? (1) 根據(jù)給定的 n個(gè)權(quán)值 {w1,w2, … ,wn}構(gòu)成 n棵二叉樹(shù)的集合 F={T1,T2, … ,Tn}， 其中每棵二叉樹(shù) Ti中只有一個(gè)帶權(quán)為 Wi的根結(jié)點(diǎn) ,其左右子樹(shù)均空 。 ? (2) 在 F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù) ,且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左 、 右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和 。 ? (3) 在 F中刪除這兩棵樹(shù) ,同時(shí)將新得到的二叉樹(shù)加入 F中 。 ? (4) 重復(fù) (2)和 (3),直到 F只含一棵樹(shù)為止 。 這棵樹(shù)便是赫夫曼樹(shù) 。 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 構(gòu)造赫夫曼樹(shù)舉例 c d a b 7 5 2 4 a b c 2 d 4 5 7 a b c 6 d 5 7 a b c d 11 7 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 例題： 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 a b c 2 d 9 6 5 e 7 構(gòu)造赫夫曼樹(shù) c a 5 2 7 9 6 b d e 7 b c 7 6 13 9 d c a 5 2 7 9 d c a 5 2 7 16 b c 7 6 13 9 d c a 5 2 7 16 b c 7 6 13 26 在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二 進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則： （ 1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有 唯一性 ，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣； （ 2）發(fā)送的二進(jìn)制編碼 盡可能地短 。下面我們介紹兩種編碼的方式。 第二節(jié) 赫夫曼編碼 等長(zhǎng)編碼：每個(gè)字符的編碼 長(zhǎng)度相同 。 設(shè)字符集只含有 4個(gè)字符 A， B， C， D，用兩位二進(jìn)制表示的編碼分別為 00， 01， 10， 11。若現(xiàn)在電文為：ABACCDA，則應(yīng)發(fā)送二進(jìn)制序列： 00010010101100，總長(zhǎng)度為 14位。當(dāng)接收方接收到這段電文后，將按兩位一段進(jìn)行譯碼。 這種編碼的特點(diǎn) : 譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。 第二節(jié) 赫夫曼編碼 不等長(zhǎng)編碼 在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng)的。 ?使用頻度較 高 的字符分配一個(gè)相對(duì)比較 短 的編碼， ?使用頻度較 低 的字符分配一個(gè)比較 長(zhǎng) 的編碼。 第二節(jié) 赫夫曼編碼 例如，可以為 A、 B、 C、 D四個(gè)字符分別分配 0， 00， 1， 01，并可將上述電文用二進(jìn)制序列： 000011010發(fā) 送，其長(zhǎng)度只有 9個(gè)二進(jìn)制位。 但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú) 法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面 4個(gè) 0是 4個(gè) A， 1個(gè) B加 2個(gè) A，還是 2個(gè) B，即譯碼不唯一，因此這種編碼方法 不可使用。 第二節(jié) 赫夫曼編碼 ABACCDA 不等長(zhǎng)編碼 利用赫夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的 赫夫曼編碼 是一種 最優(yōu)前綴編碼 ， 即使所傳 電文的總長(zhǎng)度最短 。稱為赫夫曼編碼。 赫夫曼編碼 第二節(jié) 赫夫曼編碼 （ 1）利用字符集中每個(gè)字符的使用頻率作為權(quán)值構(gòu)造一個(gè)赫夫曼樹(shù)； （ 2）從根結(jié)點(diǎn)開(kāi)始，為到每個(gè)葉子結(jié)點(diǎn)路徑上的左分支賦予 0，右分支賦予 1，并從根到葉子方向形成該葉子結(jié)點(diǎn)的編碼。 赫夫曼編碼的構(gòu)造方法 ： 第二節(jié) 赫夫曼編碼 例如 ： 假設(shè)有一個(gè)電文字符集中有 8個(gè)字符，每個(gè)字符 的使用頻率分別為 {,, ,}， 現(xiàn)以此為例設(shè)計(jì)赫夫曼編碼。 為方便計(jì)算，將所有字符的頻度乘以 100，使 其轉(zhuǎn)換成整型數(shù)值集合，得到 {5,29,7,8,14,23, 3,11}； 赫夫曼編碼設(shè)計(jì)如下圖： 第二節(jié) 赫夫曼編碼 11 5 29 7 8 14 23 3 100 0 1 15 58 29 0 0 0 1 1 1 8 42 19 0 0 0 1 1 1 00 010 0110 0111 1110 1111 110 10 赫夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu) 用一個(gè)大小為 2n1的向量來(lái)存儲(chǔ)赫夫曼樹(shù)中的結(jié)點(diǎn)， 其存儲(chǔ)結(jié)構(gòu)為： typedef struct { //結(jié)點(diǎn)類型 int weight； //權(quán)值，不妨設(shè)權(quán)值均大于零 int lchild， rchild， parent； //左右孩子及雙親指針 }HTNode， *HuffmanTree。//動(dòng)態(tài)分配數(shù)組存儲(chǔ) 樹(shù) Typedef char **Huffmancode。 。 //動(dòng)態(tài)分配數(shù)組存儲(chǔ) 赫夫曼編碼表 第二節(jié) 赫夫曼編碼 Weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 0 1 2 3 4 5 6 7 W 5 29 8 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 23 3 11 9991 78 10 10 3 415 11 11 12 819 14 14 12 13 13 15 15 529 42 58 100 210 11 614 12 13 HC 0 cd 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 0 1 1 ↑ start 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 求赫夫曼編碼過(guò)程的實(shí)例 : HT數(shù)組 求哈夫曼編碼的算法 : void HuffmanCoding(HuffmanTree amp。HT/*HF樹(shù) */, int n /*n個(gè)字符 */ HuffmanCode amp。HC /*HF編碼表 */, int *w /*各字符的權(quán)值 數(shù)組 */,){ if(n=1) return。 m=2*n1 /*HF樹(shù)所需空間總數(shù) */ 。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。 for(p=HT+1,i=1。i=n。++i,++p,++w) *p={*w,0,0,0} //初始化 HF樹(shù) ,并填入初始值 for(。i=m。++i,++p) *p={0,0,0,0} //將葉子結(jié)點(diǎn)以外的結(jié)點(diǎn)初始化為 0 for(i=n+1； i=m； i++){ //建立 HF樹(shù) SelectMin(HT， i1， s1， s2)； //選出權(quán)值最小的兩個(gè)結(jié)點(diǎn) s1,s2 HT[s1].parent=i。 HT[s2].parent=i； //填寫雙親結(jié)點(diǎn)編號(hào) HTIi].1child=s1； HT[j].rchild=s2； HT[i].weight=T[s1].weight+T[s2].weight； } // end for //從葉子到根逆向求每個(gè)字符的赫夫曼編碼 HC=(Huffmancode)malloc((n+1)*sizeof(char *))。 cd=(char *)malloc(n*sizeof(char *))。 cd[n1]=“\0”； for(i=1。i=n。i++){ start=n1； for(c=i,f=HT[i].parent。f!=0。c=f,f=HT[f].parent if(HT[f].lchild==c cd[start]=“0”。 else cd[start]=“1”。 HC[i]=(char * )malloc((nstart)*sizeof(char))。 strcpy(Hc[i]， amp。cd[start])； } free(cd)。 }//Huffmancoding 求赫夫曼編碼的算法 : 小 結(jié) 1. 熟練掌握 二叉樹(shù)的結(jié)構(gòu)特性 ，了解相應(yīng)的證明方法。 2. 熟悉二叉樹(shù)的各種 存儲(chǔ)結(jié)構(gòu) 的特點(diǎn)及適用范圍。 3. 遍歷二叉樹(shù) 是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的 遞歸算法 ， 靈活運(yùn)用遍歷算法 實(shí)現(xiàn)二叉樹(shù)的其它操作。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷。 小 結(jié) 4. 理解二叉樹(shù) 線索化的實(shí)質(zhì) 是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹(shù)的 線索化過(guò)程 以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹(shù)的 線索化過(guò)程是 基于 對(duì)二叉樹(shù)進(jìn)行 遍歷 ，而線索二叉樹(shù)上的 線索又為相應(yīng)的遍歷提供 了 方便 。 小 結(jié) 5. 熟悉 樹(shù)的 各種 存儲(chǔ)結(jié)構(gòu) 及其特點(diǎn)，掌握 樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng) 掌握 1 至 2 種 建立 二叉樹(shù)和樹(shù)的 存儲(chǔ)結(jié)構(gòu)的方法 。 6. 學(xué)會(huì)編寫 實(shí)現(xiàn)樹(shù)的各種操作 的算法。 7. 了解 最優(yōu)樹(shù)的特性 ，掌握 建立最優(yōu)樹(shù)和赫夫曼編碼 的方法。 謝 謝！