【正文】 112 \0 1 1 0 \0 0 0 \0 0 1 \0 1 1 \0 0 1 0 hc[1] hc[2] hc[3] hc[4] hc[5] 5 7 3 2 8 cd 0 …… n 3 n2 n1 \0 0 0 1 10 2 3 5 7 8 15 5 10 25 0 0 0 0 1 1 1 1 00 010 011 10 11 9 8 7 6 5 4 3 2 1 RChild LChild parent weight 0 0 0 0 0 0 8 0 0 2 0 0 3 0 0 7 0 0 5 8 7 25 5 2 9 15 61 9 10 3 4 7 5 8 6 6 8 7 4. 哈夫曼算法的實現(xiàn) —編碼 113 作業(yè) P1354 , 5 P13620 20題附加問題： 1. 計算哈夫曼樹的帶權路徑長度 2. 寫出每一個權值對應的編碼。 設 w={5,29,7, 8, 14, 23, 3, 11} 3 5 8 ,8} 7 8 15 ,15} 11 19 ,19} 14 29 ,29} 23 42 ,42} 29 58 ,58} 100 ,100} 0 1 0 1 0 1 0 1 0 1 0 1 0 1 10 110 1110 1111 01 001 0000 0001 哈夫曼編碼應用舉例 哈夫曼編碼算法 利用哈夫曼樹求編碼時，編碼是由后向前生成的，需要走一條從葉子到根的路徑： 當前結點若是其雙親的左子樹時，則置當前編碼位為 0，否則置為 1。 用字符出現(xiàn)的頻率 (Pi)為權值構造哈夫曼樹 ,并以此來構造字符的哈夫曼編碼，由于哈夫曼樹的 WPL最?。? 所以傳輸?shù)膱笪拈L度： 必定最小。 結論二 : 哈夫曼編碼是最優(yōu)前綴碼。 108 7 2 3 5 15 8 5 10 25 0 0 0 0 1 1 1 1 00 10 010 011 編碼 :左分支 :0\右分支 :1； 根到葉子路徑上的 值構成葉子的編碼。 107 哈夫曼編碼 : 對 哈夫曼樹 中每個左分支賦予 0，右分支賦予 1，則從根到每個葉子的路徑上，各分支的值構成該葉子的 哈夫曼編碼。 前綴碼： 同一字符集中任何一個字符的編碼都不是另一個字符編碼的前綴（最左子串） 。 } } } 106 哈夫曼樹最典型的應用是在編碼，利用哈夫曼樹，可以得到平均長度最短的編碼。 ht[j].parent==0) { *s2 = j。 } else if(ht[j].weightm2 amp。 *s1=j。 ht[j].parent==0) { m2 = m1。j++) { if (ht[j].weightm1 amp。 /*m2存放 次小權值 ,s2是 m2在數(shù)組的 下標 */ for(j=1。 } 4. 哈夫曼算法的實現(xiàn) —創(chuàng)建哈夫曼樹 2 3 5 105 4. Huffman算法實現(xiàn) —選擇函數(shù) define MAXINT 32767 select(HuffmanTree ht, int pos, int *s1, int *s2 ) { int j , m1, m2。 ht[i].LChild=s1。 ht[s1].parent=i。s2)。i++) { select(ht,i1,amp。 } /*選擇 合并 */ } 104 /*選擇、合并 n1次 */ for(i=n+1。 ht[i].LChild=0。i++) /*分支結點初始化 */ { ht[i].weight=0。 for(i=n+1。 ht[i].RChild=0。 ht[i].Parent=0。i=n。 102 i i s2 i i s1 s1 s2 s1 s2 5 7 3 2 8 F: 2 3 5 5 7 8 15 10 5 10 15 25 25 1 2 3 4 5 6 7 8 9 √ √ √ √ √ √ √ √ 9 8 7 6 5 4 3 2 1 RChild LChild parent weight 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 2 0 0 0 3 0 0 0 7 0 0 0 5 87 25 5 2 9 15 6 1 9 10 3 4 7 5 8 6 6 8 7 4. 哈夫曼算法的實現(xiàn) —創(chuàng)建哈夫曼樹 s1 s2 葉子結點 分支結點 初始化完畢 選擇、合并 n1次 直至只含一棵樹為止 4. 哈夫曼算法的實現(xiàn) —創(chuàng)建哈夫曼樹 void CrtHuffmanTree(HuffmanTree ht,int w[ ],int n) { int i, j ,k , s1 , s2。 101 哈夫曼算法 初始化：先將 n個元素都視為根結點，即孩子和雙親指針全置 0。 }HTNode, HuffmanTree[M+1]。 weight parent Lchild Rchild 權值 雙親序號 左孩子序號 右孩子序號 100 靜態(tài)三叉鏈表結構定義 define N 20 define M 2*N1 typedef struct { int weight 。 98 例如 : 已知權值 W={ 5, 6, 2, 9, 7 } 9 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 構造哈夫曼樹如下： 9 5 2 7 16 6 7 13 29 哈夫曼算法的實現(xiàn) n個葉子結點 的哈夫曼樹共有 2n1個結點 ,因此可用有 2n1個元素的 數(shù)組 來存儲哈夫曼樹 , 結點間的 關系用游標表示 ，即采用 靜態(tài)鏈表 來存儲哈夫曼樹。 最優(yōu)二叉樹的構造方法最早由哈夫曼研究，所以又稱為“哈夫曼樹”。 特征： 在最優(yōu)二叉樹中沒有度數(shù)為 1 的結點 (可用反證法證明 )。 結點的權： 給樹中每個結點賦予一個具有實際意義的數(shù)值，我們稱該數(shù)值為這個結點的權。 a 例： PL(a)=1+1+2+2+2+2=10 b PL(b)=1+1+2+2+3+3=12 一、基本概念： 93 帶權路徑長度： 在樹形結構中，我們把從樹根到某一結點的路徑長度與該結點權的乘積，稱做該結點的帶權路徑長度。 路徑長度： 從一個結點到另一個結點所經(jīng)過 的分支條數(shù)。 計算機程序操作碼的優(yōu)化也可以利用哈夫曼樹實現(xiàn)。 A B D C F E G H I J G H I J A B C D E F 90 哈夫曼樹與哈夫曼編碼 ?哈夫曼樹的定義 ?如何構造最優(yōu)樹 ?前綴編碼 91 哈夫曼樹 哈夫曼樹最典型、最廣泛的應用是在編碼技術上，利用哈夫曼樹，可以得到平均長度最短的編碼。 89 二叉樹 → 森林 舉例： 抹線： 將 二叉樹的根結點 與其右孩子 i的連線當且僅當連續(xù)地沿著 i的 右鏈 不斷搜索到的所有右孩子間的連線全部抹掉 ,這樣得到若干棵孤立的二叉樹。 A B D C E G F H 88 二叉樹轉(zhuǎn)化成森林 前提：二叉樹的根結點必 有右孩子 抹線： 將 二叉樹的根結點 與其右孩子 i的連線及連續(xù)地沿著 i的 右鏈 不斷搜索到的所有右孩子間的連線全部抹掉，這樣得到若干 棵孤立的二叉樹。 抹線 ：抹掉原二叉樹中所有雙親結點與右孩子的連線。 歸整化 ：將圖形歸整化，使各結點 按層次 排列且將加上去的虛線變成實線。 84 森林轉(zhuǎn)化成二叉樹 ① 將森林中的每棵樹轉(zhuǎn)換成對應的二叉樹； ② 按照給出的森林中樹的次序，依次將 后一棵 二叉樹插入 為前一棵 二叉樹根結點 的右子樹 ； 85 森林 → 二叉樹 舉例：