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