第六章樹和二叉樹-資料下載頁
2025-07-21 00:02本頁面
【正文】 n}, 生成 n 棵二叉樹的集合 F= {T1,T2,.......Tm}。其中每棵二叉樹 Ti只有一個帶權(quán)為 Wi的根結(jié)點，左右子樹為空。 (2) 在 F 中選擇兩棵根結(jié)點值最小的樹 Ti ,Tj 作為左右子樹 ,構(gòu)成一棵新二叉樹 Tk , Tk根結(jié)點值為 Ti ,Tj根結(jié)點權(quán)值之和 。 (3) 在 F 中刪除 Ti ,Tj ,并把 Tk 加到 F中 。 (4) 重復 (2) (3),直到 F中只含一棵樹。 例： w={7， 5， 2， 4} 7 5 2 4 6 7 5 2 4 4 2 7 11 5 6 18 7 11 5 6 2 4 哈夫曼 編碼 數(shù)據(jù)的壓縮過程稱為編碼，解壓過程稱為解碼。 編碼：將文件中的字符轉(zhuǎn)換為唯一的一個二進制串。 解碼：將一個二進制串轉(zhuǎn)換為對應的字符。 定長編碼：設(shè)編碼字符個數(shù)為 n,碼長為 k，則 k= ?log2n+1?。 不等長編碼：使出現(xiàn)頻率最多的字符采用盡可能短的編碼。 前綴編碼：對不等長編碼，要求任一字符的編碼都不是另一個字符的編碼的前綴。 采用二叉樹設(shè)計前綴編碼：用二叉樹的葉結(jié)點表示待編碼的字符，并約定左分支表示字符 ‘ 0’，右分支表示字符 ‘ 1’，則從根結(jié)點到葉子結(jié)點的路徑上分支字符組成的字符串作為該葉子結(jié)點的編碼。由此得到的編碼必為二進制的前綴編碼。 方法：以 n種字符出現(xiàn)的頻率作權(quán)，設(shè)計一棵哈夫曼樹，由此得到字符的二進制前綴編碼為總長最短的二進制前綴編碼，這種編碼即為哈夫曼編碼。 哈夫曼 編碼實現(xiàn) 哈夫曼樹的存儲結(jié)構(gòu)：靜態(tài)鏈表 (連續(xù)存儲空間 )。 哈夫曼樹共有 2n1個結(jié)點，其中有 n個葉結(jié)點， n1個非葉結(jié)點。 typedef struc { unsigned int weight。 unsigned int parent,lchild,rchild。 }HTNode,*HuffmanTree。 typedef char **HuffmanCode。 算法的 C語言實現(xiàn)： 初始化：將樹 T的所有結(jié)點的三個指針均置為空（ 1），權(quán)值置為 0。 輸入：讀入 n個葉結(jié)點的權(quán)值存放于 T的前 n個分量中。 合并：進行 n1次合并，將產(chǎn)生的新結(jié)點 i依次放入 T的第 i個分量中（ n≤i≤m 1）。合并分兩步進行： （ 1）在當前森林 T[0..i1]的所有結(jié)點中，選取權(quán)最小和次小的兩個根結(jié)點 T[p1]和 T[p2]作為合并對象。（ 0≤p1,p2≤i 1） （ 2）將根為 T[p1]和 T[p2]的兩棵樹作為左右子樹合并為一棵新的樹。新樹的根為 T[i]，權(quán)值為 T[p1]和 T[p2]的權(quán)值之和。并且 T[p1]和 T[p2]的parent為 i， T[i]的 lchild和 rchild分別為 p1和 p2。 哈夫曼 編碼實現(xiàn) Void HuffmanCoding(HuffmanTree amp。HT,HuffmanCode amp。Hc,int *w,int n) { if(n=1) return。 m=2*n1 HT=(HuffmanTree)malloc(m*sizeof(HuTNode))。 for(p=HT,i=0。in。i++,p++) *p={w[i],1,1,1}。 for(i=n。im。i++,p++) *p={0,1,1,1}。 for(i=n。im。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。 } Hc=(Huffmancode*)malloc(n*sizeof(char *))。 cd=(char *)malloc(n*sizeof(char))。 cd[n1]=‘\0’。 for(i=0。in。i++) //哈夫曼編碼 { start=n1。 for(c=i, f=HT[i].parent。 f!=1。 c=f, f=HT[f].parent) if(HT[f].lchild==c) cd[strat]=‘0’。 else cd[start]=‘1’。 Hc[i]=(char *)malloc((nstart)*sizeof(char)) strcpy(HC[i],amp。cd[start])。 } free(cd)。 } 編碼過程：從葉結(jié)點開始向根結(jié)點逆向處理。 例：編碼字符 8個 概率 {,,} w={5,29,7,8,14,23,3,11} 5 1 1 1 29 1 1 1 7 1 1 1 8 1 1 1 14 1 1 1 23 1 1 1 3 1 1 1 11 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 8 1 1 29 13 1 1 7 9 1 1 8 9 1 1 14 11 1 1 23 12 1 1 3 8 1 1 11 10 1 1 8 10 6 0 15 11 2 3 19 12 8 7 29 13 4 9 42 14 10 5 58 14 1 11 100 1 12 13 5 0 01 1 29 1 0 7 1 1 1 0 8 1 1 1 1 14 1 1 0 23 0 1 3 0 01 0 11 0 0 0 23 3 5 11 8 7 14 29 0 0 0 0 0 0 0 1 1 1 1 1 1 1 哈夫曼 譯碼的實現(xiàn) 哈夫曼編碼是前綴編碼，即任何一個字符的編碼不是另一個字符的編碼的前綴。 譯碼方法：根據(jù)讀入的字符編碼順序與哈夫曼樹的分支進行匹配，直到達到某個葉子結(jié)點，即識別出一個字符。 作業(yè) 思考題： 作業(yè)題： 上機實驗 p149 哈夫曼編碼 /譯碼
法律信息相關(guān)推薦
鄂ICP備17016276號-1