【正文】 b， c兩步 ， 直到 F中只剩下一棵二叉樹 。 、最優(yōu)二叉樹 (赫夫曼樹 ) 127 a b c d e .12 .40 .15 .08 .25 .12 0 0 0 .40 0 0 0 .15 0 0 0 .08 0 0 0 .25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 HT 1 2 3 4 5 6 7 8 9 weight parent lchild rchild 、最優(yōu)二叉樹 (赫夫曼樹 ) 128 a b c d e .12 .40 .15 .08 .25 .12 6 0 0 .40 0 0 0 .15 0 0 0 .08 6 0 0 .25 0 0 0 .20 0 4 1 0 0 0 0 0 0 0 0 0 0 0 0 HT 1 2 3 4 5 6 7 8 9 10 weight parent lchild rchild 、最優(yōu)二叉樹 (赫夫曼樹 ) 129 a b c d e .12 .40 .15 .08 .25 .12 6 0 0 .40 9 0 0 .15 7 0 0 .08 6 0 0 .25 8 0 0 .20 7 4 1 .35 8 3 6 .60 9 5 7 1 0 2 8 HT 1 2 3 4 5 6 7 8 9 weight parent lchild rchild 、最優(yōu)二叉樹 (赫夫曼樹 ) *** 130 (1)編碼的長短 （ 等長編碼 ） 在英文通信中 ， 在計(jì)算機(jī)中經(jīng)常需要將字符轉(zhuǎn)化為二進(jìn)制編碼 。 例：設(shè)電文中只用了 A,B,C,D四個(gè)字母； 采用二位編碼為 00， 01， 10， 11； 電文為 “ ACDACAB” 的二進(jìn)制代碼串：00101100100001； 總長為 14位，對方接收后可按二位一分進(jìn)行譯碼。 、赫夫曼編碼 131 不等長編碼： 在實(shí)際應(yīng)用中，由于字符出現(xiàn)的頻率不同，可采用不等長編碼降低編碼的長度； 在 “ ACDACAB” 中 A， C出現(xiàn)的次數(shù)較多， A,C編碼要短 例如 0(A),00(B),1(C),01(D)，電文的二進(jìn)制代碼串： 010101000，總長為 9位。 (2)譯碼唯一性 采用不等長編碼出現(xiàn)的問題 ， 譯碼唯一性 。 即要采用不等長編碼 ， 又要保證譯碼唯一性 ， 就必須采用 前綴編碼 。 、赫夫曼編碼 132 (3)前綴編碼 。 要求任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴 ， 這種編碼稱做前綴編碼 。 A,B,C,D的編碼為： 0， 00， 1， 01 A,B,C,D的編碼為： 00， 01， 10， 11 A,B,C,D的編碼為： 0， 10， 110， 111 、赫夫曼編碼 133 (4)電文長度與哈夫曼樹 。 假 設(shè) 組 成 電 文 的 字 符 集 合 是D={d1,d2,...dn},每個(gè)字符出現(xiàn)的次數(shù)是c1,c2,...,di對應(yīng)的編碼長度是 li。 ??niiilc1 通常我們用 di出現(xiàn)的概率來代替出現(xiàn)的次數(shù) ， 設(shè) di出現(xiàn)的概率為 wi。 ??niiilw1 、赫夫曼編碼 134 (1)赫夫曼編碼舉例 利用赫夫曼樹對句子 “ it is a tree” 進(jìn)行編碼 。 句子中有字符： {i， t， ?， s， a， r， e}共七個(gè)字符 。 七個(gè)字符的權(quán)值分別為： {2， 2， 3， 1，1， 1， 2}。 編碼過程 編碼結(jié)果： 見圖 i t ? i s ? a ? t r e e 011 10 11 011 001 11 0000 11 10 0001 010 010 、赫夫曼編碼 135 赫夫曼編碼 —— 利用赫夫曼樹得到的前綴編碼。 (2)赫夫曼編碼的方法 ： b. 設(shè)計(jì)赫夫曼編碼：在有了赫夫曼樹之后 ， 將樹中每個(gè)結(jié)點(diǎn)的左分支用 “ 0” 代表 ， 右分支用“ 1” 代表 。 則從根結(jié)點(diǎn)到葉結(jié)點(diǎn)之間 ， 沿途路徑上的分支組成的 “ 0” 或 “ 1” 代碼串就是該葉子結(jié)點(diǎn)所代表的字符編碼 ， 稱為赫夫曼編碼 。 、赫夫曼編碼 136 (3)赫夫曼編碼的特點(diǎn) 由赫夫曼樹的構(gòu)成可知權(quán)大的結(jié)點(diǎn)靠近根結(jié)點(diǎn) ， 其路徑短 。 電文的總長度最短 赫夫曼樹是帶權(quán)路徑長度最短的二叉樹 。 前綴碼 赫夫曼編碼對應(yīng)終點(diǎn)為葉子的路徑，相互不完全重疊。 、赫夫曼編碼 137 .12 6 0 0 .40 9 0 0 .15 7 0 0 .08 6 0 0 .25 8 0 0 .20 7 4 1 .35 8 3 6 .60 9 5 7 1 0 2 8 1 2 3 4 5 6 7 8 9 weight parent lchild rchild HC \0 cd 1 1 1 1 \0 、赫夫曼編碼 1 1 1 1 138 .12 6 0 0 .40 9 0 0 .15 7 0 0 .08 6 0 0 .25 8 0 0 .20 7 4 1 .35 8 3 6 .60 9 5 7 1 0 2 8 1 2 3 4 5 6 7 8 9 weight parent lchild rchild HC \0 cd 1 1 1 1 \0 0 \0 、赫夫曼編碼 0 139 赫夫曼樹和赫夫曼編碼的存儲表示 typedef struct{ unsigned int weight。 unsigned int parent,lchild,rchild。 }HTNode,*HuffmanTree。 Typedef char **huffmanCode。 、赫夫曼編碼 140 void HuffmanCoding(HuffmanTree amp。HT, HuffmanCode amp。HC, float *w, int n) {if (n=1) return。 m = 2 * n 1。 HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode))。 for (p=HT,i=1。i=n。 ++i,++p,++w) *p={*w,0,0,0}。 //初始化 for (。i=m。++i。++p) { //初始化 *p={0,0,0,0}。 、赫夫曼編碼 141 for (i=n+1。i=m。++i) {select(HT,i1,s1,s2)。 HT[s1].parent=i。 HT[s2].parent=i。 HT[i].lchild=s1。 HT[i].rchild=s2。 HT[i].weight=HT[s1].weight+HT[s2].weight。 } 、赫夫曼編碼 142 void HuffmanCoding(HuffmanTree amp。HT, HuffmanCode amp。HC, int *w, int n) {HC = (HuffmanCode)malloc((n+1) * sizeof(char *))。 cd = (char *)malloc(n*sizeof(char))。 cd[n1] = 39。\039。 // 編碼結(jié)束符。 for (i=1。 i=n。 ++i) { start = n1。 // 編碼結(jié)束符位置 *** 、赫夫曼編碼 143 for (c=i, f=HT[i].parent。 f!=0。 c=f, f=HT[f].parent) if (HT[f].lchild==c) cd[start] = 39。039。 else cd[start] = 39。139。 HC[i] = (char *)malloc((nstart)* sizeof(char))。 strcpy(HC[i], amp。cd[start])。 } free(cd)。 // 釋放工作空間 } // HuffmanCoding *** 、赫夫曼編碼 144 赫夫曼譯碼 *** 145 返回 赫夫曼編碼 146 例 3 利用棧實(shí)現(xiàn)先序遍歷的非遞歸算法 void PreOrder( BiTree T) {BiTNode *q,*p=T。 STACK S。InitStack(S)。 //遞歸工作棧 if (p!=NULL) PUSH (S,p)。 while (!IsEmpty(S)) {POP(S,q)。 visit(q)。 if (qrchild) PUSH(S,qrchild )。 if (qlchild) PUSH(S,plchild)。 //進(jìn)左子樹 }} 例題 *** 147 例 4：假設(shè)二叉樹 T中至多有一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域值為 x,試編寫算法拆去以該結(jié)點(diǎn)為根的子樹，使原樹中分成兩棵子樹。 A B C x D F I H E A B C x D F I H E 例題 148 采用前序遞歸算法： 如果 tlchilddata==x。 p=tlchild。tlchild=null。 返回 p。 如果 trchilddata==x。 p=trchild。trchild=null。 返回 p。 否則在左子樹中查找； 如果在左子樹中沒有找到，則在右子樹中查找。 如果樹中沒等于 x的結(jié)點(diǎn)，返回空值。 例題 149 BiTree p=null。//全局變量；新樹的根結(jié)點(diǎn)。 void Dissect(Bitree t,ElemType x) {if (t!=nullamp。amp。tlchild!=null) {if (tlchilddata==x) {p=tlchild。tlchild=NULL。} } else if (t!=nullamp。amp。trchild!=null) {if (trchilddata==x) {p=trchild。trchild=NULL。} } if (t!=nullamp。amp。!p) Dissect(tlchild,x)。 if (t!=nullamp。amp。!p) Dissect(trchild,x)。 } // 算法結(jié)束 例題