1、1 數據結構數據結構 深圳大學深圳大學 計算機與軟件學院計算機與軟件學院 白鑒聰白鑒聰 上節復習上節復習 n二叉樹的存儲結構二叉樹的存儲結構 p順序存儲，把普通二叉樹補全為完全二叉樹，再按層次遍歷順序保存順序存儲，把普通二叉樹補全為完全二叉樹，再按層次遍歷順序保存 p鏈式存儲，二叉鏈表、三叉鏈表鏈式存儲，二叉鏈表、三叉鏈表 p掌握存儲結構的畫圖方法掌握存儲結構的畫圖方法 n二叉樹的四種遍歷：二叉樹的四種遍歷： p前序、中序、后序，采用遞歸嵌套方式前序、中序、后序，采用遞歸嵌套方式 p層次遍歷，從上往下，從左到右，把二叉樹的鏈式存儲轉化為數組存儲層次遍歷，從上往下，從左到右，把二叉樹的鏈式存儲轉

2、化為數組存儲 3 n已知二叉樹結構如圖所示，求已知二叉樹結構如圖所示，求 n求先、中、后序遍歷結果求先、中、后序遍歷結果 n畫出順序存儲和鏈式存儲結果畫出順序存儲和鏈式存儲結果 練習練習 a de b fg c hi j k 4 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n赫夫曼樹又稱為最優樹，是一類帶權赫夫曼樹又稱為最優樹，是一類帶權 路徑長度最短的樹路徑長度最短的樹 n樹的路徑和路徑長度樹的路徑和路徑長度 q 路徑：從樹中一個結點到另一個結 點之間的分支構成這兩個結點之間 的路徑 q 路徑長度：路徑上的分支數目 q 樹的路徑長度：從樹根到每個結點 的路徑長度之和 樹路徑長度為：2

3、*1 + 3*2 + 1*3 = 11 A D B F C G E 5 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n帶權路徑長度：從結點到樹根之間的帶權路徑長度：從結點到樹根之間的 路徑長度與結點上權的乘積路徑長度與結點上權的乘積 n樹的帶權路徑長度樹的帶權路徑長度(WPL)(WPL)：樹中所有：樹中所有 葉子結點的帶權路徑長度之和葉子結點的帶權路徑長度之和 WPL = 2*5+3*3+2*4=27 A D B F C G E 5 6 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n具有具有n個葉子結點個葉子結點(每個結點的權值為每個結點的權值為wi) 的二叉樹不止一的二叉樹不

4、止一 棵，但在所有的這些二叉樹中，必定存在一棵棵，但在所有的這些二叉樹中，必定存在一棵WPL值最值最 小小的樹的樹，稱這棵樹為，稱這棵樹為Huffman樹樹(或稱最優樹或稱最優樹) n如圖如圖是權值分別為是權值分別為2、3、6、7，具有，具有4個葉子結點的二個葉子結點的二 叉樹叉樹 2367 3 67 2 6 7 2 3 (a) (b) (c) 具有相同葉子結點，不同帶權路徑長度的二叉樹具有相同葉子結點，不同帶權路徑長度的二叉樹 7 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n它們的帶權路徑長度分別為它們的帶權路徑長度分別為： (a) WPL=2 2+3 2+6 2+7 2=36 (

5、b) WPL=2 1+3 2+6 3+7 3=47 (c) WPL=7 1+6 2+2 3+3 3=34 n其中其中(c)的的 WPL值最小，稱這棵樹為最優二叉樹或值最小，稱這棵樹為最優二叉樹或 Huffman樹樹 8 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n赫夫曼樹的簡單應用百分制轉五級制 q將0100分轉變為不及格、及格、中等、良好、優良五個級別 q普通方法用四次判斷語句 q不同成績的分布規律構造赫夫曼樹，通過赫夫曼樹進行判定，大 大減少判斷次數 q構造二叉樹的思路：把分布比例數作為葉子權值，每個結點包含 一個判斷，把高權值結點放在路徑短的地方，低權值放在路徑長 的地方 9

6、6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n赫夫曼樹的簡單應用百分制轉五級制 q將0100分轉變為不及格、及格、中等、良好、優良五個級別 q分數的分布比例為： 10 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n赫夫曼樹的簡單應用百分制轉五級制 q采用普通方法用四次判斷語句 q若有10000個輸入數據，根據分數分布比例需要31500次 q80%以上數據需要經過3次以上的比較才能得到結果 11 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n赫夫曼樹的簡單應用百分制轉五級制 q把高比例數據先做比較，程序調整如下， 12 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹

7、n赫夫曼樹的簡單應用百分制轉五級制 q改進方法中每個比較有包含兩次判斷，再做細化，得到如下的判 定樹 q10000個輸入數據需要22000次判斷 13 6.6 赫夫曼樹赫夫曼樹 一一最優二叉樹最優二叉樹 n赫夫曼樹的簡單應用百分制轉五級制 q以5、15、40、30和10為權值，構造一顆有5個葉子的赫夫曼樹， 也就得到同樣的這顆二叉樹 14 6.6 赫夫曼樹赫夫曼樹 二二赫夫曼樹的構造赫夫曼樹的構造 n在在HuffmanHuffman樹中，權值最大的結點離根最近，權值最小的樹中，權值最大的結點離根最近，權值最小的 結點離根最遠結點離根最遠 n構造算法構造算法 根據給定的n個權值(w1, w2,

8、, wn)構成n棵二叉樹的集合F=T1, T2, , Tn，其中每棵二叉樹Ti中只有一個帶樹為Ti的根結點 在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新 的二叉樹，且置其根結點的權值為其左右子樹權值之和 在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中 重復2, 3，直到F只含一棵樹為止 15 6.6 赫夫曼樹赫夫曼樹 二二赫夫曼樹的構造赫夫曼樹的構造 n舉例舉例 F : 7 5 2 4F : 7 5 6 F : 7 11 7524 初始 合并2 4 75 24 6 F : 18 11 75 24 6 合并5 6 5 合并7 112 7 4 6 11 18 16 6.6 赫夫曼樹赫

9、夫曼樹 三三赫夫曼編碼赫夫曼編碼 n通過赫夫曼樹把電文縮短，減少傳送時間 n編碼前GOOD_G q設給出一段報文： GOOD_GOOD_GOOD_GOOOOOOOO_OFF q字符集合是 O, G, _, D, F，各個字符出現的頻度(次數)是 W 15, 4, 4, 3, 2。 q若給每個字符以等長編碼 qO: 000 G: 001 _: 010 D: 011 F: 100 q則總編碼長度為 (15+4+4+3+2) * 3 = 84. 17 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼編碼赫夫曼編碼 n編碼后 q若按各個字符出現的概率不同而給予不等長 編碼，可望減少總編碼長度。 q各字符 O, G

10、, _, D, F 出現概率為 15/28, 4/28, 4/28, 3/28, 2/28 ,化整 為 15, 4, 4, 3, 2 q各字符出現概率取整數為15, 4, 4, 3, 2 q如果規定，Huffman樹的左子樹小于右子樹， 則可構成右圖所示Huffman樹 4 15 423 G _ FD O 18 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼編碼赫夫曼編碼 n編碼后 q 令左孩子分支為編碼0，右孩子分支 為編碼1 q 將根結點到葉子結點路徑上的分支編碼， 組合起來，作為該字符的Huffman碼， 則可得到： O:1 _:011 G:010 D:001 F:000 4 15 423 0 0

11、 00 1 1 11 G _ FD O 19 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼編碼赫夫曼編碼 n則總編碼長度為 15*1+(2+3+4+4)*3 = 54 84 nHuffman是一種前綴編碼，解碼時不會混淆，如GOOD編 碼為：01011001 4 15 423 0 0 00 1 1 11 G _ FD O 20 n 已知字符已知字符A、B、C、D、E、F，對應權值為，對應權值為13、4、22、38、6、 17，若進行赫夫曼編碼，請完成以下要求：，若進行赫夫曼編碼，請完成以下要求： p 構建赫夫曼樹，要求左孩子權值不大于右孩子權值構建赫夫曼樹，要求左孩子權值不大于右孩子權值 p 寫出每個

12、字符對應的編碼，分支編碼對應寫出每個字符對應的編碼，分支編碼對應0或或1 p 對以下三個編碼串進行解碼，若解碼異常則直接輸出對以下三個編碼串進行解碼，若解碼異常則直接輸出error 01010011101，110101，010011011 練習練習 21 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹的實現 typedef struct unsigned int weight; unsigned int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char * * HuffmanCode; 22 6.6 赫夫曼樹赫

13、夫曼樹 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹的實現 void HuffmanCoding(HuffmanTree m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號單元未用號單元未用 for (i=1; i=n; i+) /初始化初始化 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /end for for (i=n+1; i=m; i+) /初始化初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0;

14、HTi.rchild=0; /end for 23 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹的實現 for (i=n+1; i=m; i+) / for (i=n+1; i=m; i+) / 建哈夫曼樹建哈夫曼樹 / / 在在HT1.i-1HT1.i-1中選擇中選擇parentparent為為0 0且且weightweight最小的兩個結點，最小的兩個結點， / / 其序號分別為其序號分別為s1s1和和s2s2。 Select(HT, i-1, s1, s2);Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent =

15、i; HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; HTi.weight = HTs1.weight + HTs2.weight; /end for 24 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹的實現赫夫曼樹的實現 /- /- 從葉子到根逆向求每個字符的哈夫曼編碼從葉子到根逆向求每個字符的哈夫曼編碼 - - cd = (char cd

16、= (char * *)malloc(n)malloc(n* *sizeof(char); / sizeof(char); / 分配求編碼的工作空間分配求編碼的工作空間 cdn-1 = 0; / cdn-1 = 0; / 編碼結束符。編碼結束符。 for (i=1; i=n; +i) / for (i=1; i=n; +i) / 逐個字符求哈夫曼編碼逐個字符求哈夫曼編碼 start = n-1; / start = n-1; / 編碼結束符位置編碼結束符位置 for (c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) for (c=i, f=HTi.par

17、ent; f!=0; c=f, f=HTf.parent) / / 從葉子到根逆向求編碼從葉子到根逆向求編碼 if (HTf.lchild=c) cd-start = 0; if (HTf.lchild=c) cd-start = 0; else cd-start = 1; else cd-start = 1; HCi = (char HCi = (char * *)malloc(n-start)malloc(n-start)* *sizeof(char); sizeof(char); / / 為第為第i i個字符編碼分配空間個字符編碼分配空間 strcpy(HCi, / strcpy(HCi, / 從從cdcd復制編碼復制編碼( (串串) )到到HCHC free(cd); / free(cd); / 釋放工作空間釋放工作空間 /end function/end function 25 6.6 赫夫曼樹赫夫曼樹 三三赫夫曼解碼赫夫曼解碼 n算法流程 n定義指針p指向赫夫曼樹結點，實際