【導(dǎo)讀】D是具有相同特性的數(shù)據(jù)元素的集合。若D為空集，則稱為空樹(shù)。不相交的有限集T1,T2,…棵子集本身又是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。子樹(shù)之間不存在確定的次序關(guān)系。的、互不交的二叉樹(shù)組成。二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第i層的結(jié)點(diǎn)數(shù)=2i-2?個(gè)結(jié)點(diǎn)（k≥1）。因?yàn)閗只能是整數(shù)，因此，k=?

　　

【正文】 從 F中刪去這兩棵樹(shù)，同時(shí)加入 剛生成的新樹(shù)； 重復(fù) (2) 和 (3) 兩步，直至 F 中只 含一棵樹(shù)為止。這棵樹(shù)便是哈夫 曼樹(shù) (3) (4)9 例如 : 已知權(quán)值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 注意： ? ① 初始森林中的 n棵二叉樹(shù)，每棵樹(shù)有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子 ② n個(gè)葉子的哈夫曼樹(shù)要經(jīng)過(guò) n1次合并，產(chǎn)生 n1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹(shù)中共有 2n1個(gè)結(jié)點(diǎn)。 ③ 哈夫曼樹(shù)是嚴(yán)格的二叉樹(shù)，沒(méi)有度數(shù)為 1的分支結(jié)點(diǎn)。 前綴編碼 在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則： （ 1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有 唯一性 ，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣； （ 2）發(fā)送的二進(jìn)制編碼 盡可能地短 。下面我們介紹兩種編碼的方式。 1. 等長(zhǎng)編碼 這種編碼方式的特點(diǎn) : 每個(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)度并不是 最短的。 2. 不等長(zhǎng)編碼 在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡 可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng) 的，使用頻度較 高 的字符分配一個(gè)相對(duì)比較 短 的 編碼，使用頻度較 低 的字符分配一個(gè)比較 長(zhǎng) 的編 碼。例如，可以為 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，即譯碼不唯一，因此這種編碼 方法不可使用。 利用哈夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的 哈夫曼編碼 是一種 最優(yōu)前綴編碼 ，即使所傳 電文的總長(zhǎng)度最短 。稱為哈夫曼編碼 哈夫曼編碼 （ 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)造方法 ： 例如 ： 假設(shè)有一個(gè)電文字符集中有 8個(gè)字符，每個(gè)字符 的使用頻率分別為 {,, ,}， 現(xiàn)以此為例設(shè)計(jì)哈夫曼編碼。 為方便計(jì)算，將所有字符的頻度乘以 100，使 其轉(zhuǎn)換成整型數(shù)值集合，得到 {5,29,7,8,14,23, 3,11}； 哈夫曼編碼設(shè)計(jì)如下圖： 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。 Typedef char **Huffmancode。 哈夫曼編碼的存儲(chǔ)結(jié)構(gòu) 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ù)組 if(n=1) return。 m=2*n1。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。 求哈夫曼編碼的算法 : for(p=HT+1,i=1。i=n。++i,++p,++w) *p={*w,0,0,0} for(。i=m。++i,++p) *p={0,0,0,0} for(i=n+1； i=m； i++){ SelectMin(HT， i1， s1， s2)； HT[s1].parent=i。 HT[s2].parent=i； HTIi].1child=s1； HT[j].rchild=s2； HT[i].weight=T[s1].weight+T[s2].weight； } // end for void HuffmanCoding(HuffmanTree amp。HT, HuffmanCode amp。HC, int *w,int n){ //從葉子到根逆向求每個(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 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)行的遍歷。 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)的遍歷提供了 方便 。 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ù)和哈夫曼編碼 的方法。