【正文】 J I 先序序列： 中序序列： A B C D E F G H I J B C D A F E H J I G A B C D E F G H J I 先序序列： 中序序列： A B C D E F G H I J B C D A F E H J I G 結(jié)論： 森林的先序和中序遍歷在兩種方式下的結(jié)果相同。 81 第 6章 樹和二叉樹（ Tree amp。 Binary Tree ） 樹的基本概念 二叉樹 遍歷二叉樹和線索二叉樹 樹和森林 赫夫曼樹及其應(yīng)用 82 路 徑 ： 路徑長度 ： 樹的路徑長度 ： 帶權(quán)路徑長度 ： 樹的帶權(quán)路徑長度 ： 霍 夫 曼 樹 ： 由一結(jié)點到另一結(jié)點間的分支所構(gòu)成 路徑上的分支數(shù)目 從樹根到 每一結(jié)點 的路徑長度之和。 結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積 預(yù)備知識：若干術(shù)語 d e b a c f g 樹中所有 葉子結(jié)點 的帶權(quán)路徑長度之和 帶權(quán)路徑長度最小的樹。 a→e 的路徑長度＝ 樹長度＝ 2 10 Huffman樹及其應(yīng)用 ——最優(yōu)二叉樹（霍夫曼樹） 83 Huffman樹簡介： 樹的帶權(quán)路徑長度如何計算？ WPL = ?wklk k=1 n a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) 經(jīng)典之例： WPL=36 WPL=46 WPL= 35 哈夫曼 樹 則 是 ： WPL 最小的樹。 WPL最小 Weighted Path Length 84 (1) 由給定的 n 個權(quán)值 {w0, w1, w2, …, wn1}，構(gòu)造具有 n 棵擴(kuò)充二叉樹的 森林 F = { T0, T1, T2, …, Tn1 }，其中每一棵擴(kuò)充二叉樹 Ti 只有一個帶有權(quán)值 wi 的根結(jié)點，其左、右子樹均為空。 (2) 重復(fù)以下步驟 , 直到 F 中僅剩下一棵樹為止： ① 在 F 中 選取兩棵根結(jié)點的權(quán)值最小 的擴(kuò)充二叉樹 , 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的 根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和 。 ② 在 F 中刪去這兩棵二叉樹。 ③ 把新的二叉樹加入 F。 構(gòu)造霍夫曼樹的基本思想： 構(gòu)造 Huffman樹的步驟（即 Huffman算法）： 權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。 85 例 1： 設(shè)有 4個字符 d,i,a,n，出現(xiàn)的頻度分別為 7,5,2, 4，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？ 法 1： 等長編碼 。例如用二進(jìn)制編碼來實現(xiàn)。 取 d=00， i=01， a=10， n=11 怎樣實現(xiàn) Huffman編碼？ 法 2： 不等長編碼 ，例如用哈夫曼編碼來實現(xiàn)。 取 d=0。 i=10, a=110, n=111 最快的編碼是哪個？ 是非等長的 Huffman碼！ 先要構(gòu)造 Huffman樹！ 86 操作要點 1： 對權(quán)值的合并、刪除與替換 —— 在權(quán)值集合 {7,5,2,4}中，總是合并 當(dāng)前值最小 的兩個權(quán) 構(gòu)造 Huffman樹的步驟： 注：方框表示外結(jié)點（葉子，字符對應(yīng)的權(quán)值）， 圓框表示內(nèi)結(jié)點（合并后的權(quán)值）。 87 操作要點 2： 按左 0右 1對 Huffman樹的所有分支編號！ d a i n 1 1 1 0 0 0 Huffman編碼結(jié)果： d=0, i=10, a=110, n=111 WPL=1 7＋ 2 5+3*(2+4)=35 特點：每一碼都不是另一碼的前綴，絕不會錯譯 ! 稱為前綴碼 —— 將 Huffman樹 與 Huffman編碼 掛鉤 88 例 2（嚴(yán)題集 ③ ） ： 假設(shè)用于通信的電文僅由 8個字母 {a, b, c, d, e, f, g, h} 構(gòu)成，它們在電文中出現(xiàn)的概率分別為 { , , , , , , , }，試為這 8個字母設(shè)計哈夫曼 編碼。 如果用 0～ 7的二進(jìn)制編碼方案又如何？ 霍夫曼 編碼的基本思想是： 概率大的字符用短碼，概率小的用長碼 。由于 霍夫曼樹的 WPL最小， 說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。 解： 先將概率放大 100倍，以方便構(gòu)造哈夫曼樹。 權(quán)值集合 w={7, 19, 2, 6, 32, 3, 21, 10}， 按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。 89 w4={19, 21, 28, 32} 為清晰起見，重新排序為 : w={2, 3, 6, 7, 10, 19, 21, 32} 2 3 5 6 w1={5, 6, 7, 10, 19, 21, 32} w2={7, 10, 11, 19, 21, 32} w3={11, 17, 19, 21, 32} 11 10 7 17 28 21 19 40 w5={28,32,40} 32 60 w6={40,60} w7={100} 100 b c a d e g f h 哈夫曼樹 90 對應(yīng)的哈夫曼編碼（左 0右 1）： 2 3 5 6 11 10 7 32 17 28 21 19 40 60 100 b c a d e g f h 0 0 0 0 0 1 1 1 1 1 1 1 0 0 符 編碼 頻率 a b c d e f g h 符 編碼 頻率 a b c d e f g h Huffman碼的 WPL＝ 2(++) + 4(++) +5(+) =++= WPL＝ 3(+++++++)=3 1100 00 11110 1110 10 11111 01 1101 000 001 010 011 100 101 110 111 二進(jìn)制碼 91 上機(jī)練習(xí)： 設(shè)字符集為 26個英文字母，其出現(xiàn)頻度如下表所示。 51 48 1 15 63 57 20 32 5 1 頻度 z y x w v u t 字符 1 16 1 18 8 23 80 頻度 p 21 f q 15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 頻度 i e d c b a 空格 字符 先建哈夫曼樹，再利用此樹對報文“ This program is my favorite”進(jìn)行編碼和譯碼。 92 提示 1： 霍夫曼樹中各結(jié)點的結(jié)構(gòu) 可以定義為如下5個分量 ： char weight parent lchild Rchild 將整個 霍夫曼樹的 結(jié)點 存儲在一個數(shù)組中： HT[1..n]。 將結(jié)點的 編碼 存儲在 HC[1..n]中。 提示 3： 霍夫曼樹如何構(gòu)造？ 構(gòu)造好之后又如何求得各結(jié)點對應(yīng)的霍夫曼編碼？ ——算法參見教材 P147。 提示 2： 霍夫曼樹的 存儲結(jié)構(gòu) 可采用 順序存儲 結(jié)構(gòu)： 93 小結(jié)：哈夫曼樹及其應(yīng)用 ： —— 權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。 Huffman樹的步驟： 對權(quán)值的合并、刪除與替換 3. Huffman編碼規(guī)則： 左 “ 0” 右 “ 1”，是一種前綴碼 也稱為最小冗余編碼、緊致碼，等等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。 補(bǔ)充 1： 構(gòu)造 Huffman樹的過程描述 補(bǔ)充 2： 對 Huffman編碼器程序的解釋 94 怎樣生成 Huffman樹？ 步驟如下： (1) 由給定的 n 個權(quán)值 {w1, w2, …, wn}構(gòu)成 n棵二叉樹的集合（即森林） F = { T1, T2, …, Tn }，其中每棵二叉樹 Ti 中 只有一個帶權(quán)為 wi 的根結(jié)點，其左右子樹均空。 (2) 在 F 中 選取兩棵根結(jié)點的權(quán)值最小的樹 做為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的 權(quán)值之和 。 (3) 在 F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F中 。 (4) 重復(fù) (2) 和 (3) , 直到 F 只含一棵樹為止。這棵樹便是赫夫曼樹。 95 本章小結(jié) 定義和性質(zhì) 存儲結(jié)構(gòu) 遍歷 線索化 ：線索樹 順序結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu) 二叉鏈表 三叉鏈表 先序線索樹 中序線索樹 后序線索樹 樹 二叉樹 森林 先 序 遍 歷 后 序 遍 歷 遍歷 存儲結(jié)構(gòu) 遍歷 雙親表示 孩子表示 孩子兄弟 先序遍歷 后序遍歷 中序遍歷 后序遍歷 先序遍歷 霍夫曼樹 霍夫曼編碼