并統(tǒng)計其葉子結(jié)點的個數(shù)。方案二：哈夫曼樹的建立和編(編輯修改稿)
2025-11-16 03:07 本頁面
【文章內(nèi)容簡介】 F中 。 (4) 重復(fù) (2) 和 (3) , 直到 F 只含一棵樹為止。這棵樹便是 Huffman樹。 怎樣證明它就是 WPL最小的最優(yōu)二叉樹？ 參考 《 信源編碼 》 Huffman樹的特點：沒有度為 1的結(jié)點。 15 step1： 對權(quán)值進行合并、刪除與替換 —— 在權(quán)值集合 {7,5,2,4}中，總是合并 當(dāng)前值最小 的兩個權(quán) 具體操作步驟： a. 初始 方框表示外結(jié)點（葉子，字符） 圓框表示內(nèi)結(jié)點（合并后的權(quán)值） b. 合并 {2} {4} c. 合并 {5} {6} d. 合并 {7} {11} 16 step2： 按左 “ 0”右 “ 1” 對 Huffman樹的所有分支編號 d a i n 1 1 1 0 0 0 Huffman編碼結(jié)果： d=0, i=10, a=110, n=111 WPL=1bit 7＋ 2bit 5+3bit(2+4)=35（小于等長碼的 WPL=36） 特征：每一碼不會是另一碼的前綴，譯碼時可惟一復(fù)原 Huffman編碼也稱為 前綴碼 —— 將 Huffman樹 與 Huffman編碼 掛鉤 17 二、 Huffman編碼 （ 1） 由于 Huffman樹的 WPL最小， 說明編碼所需要的 比特數(shù)最少 。 （ 4） Huffman編碼時是從葉子走到根；而譯碼時又要從根走到葉子，因此每個結(jié)點需要增開 雙親 指針分量（連同結(jié)點 權(quán)值共要開 5個分量） （ 5） 用計算機實現(xiàn)時，順序和鏈式兩種存儲結(jié)構(gòu)都要用到。 分析 Huffman樹和編碼的特點： 霍夫曼 編碼的基本思想是 —— 出現(xiàn)概率大的信息用短碼，概率小的用長碼 ,最小冗余 這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。 （ 2） Huffman樹 肯定沒有度為 1的結(jié)點； （ 3） 一棵有 n 0個葉子結(jié)點的 Huffman樹，共有 2n01個結(jié)點； （因為 n=n0+n1+n2=2n01) 18 如何編程實現(xiàn) Huffman編碼？ 建議 1： Huffman樹中結(jié)點的結(jié)構(gòu)可設(shè)計成 5分量形式： char weight parent lchild rchild 將整個 Huffman樹的 結(jié)點 存儲在一個數(shù)組 HT[1..n..m]中 。 各葉子結(jié)點的 編碼 存儲在另一 “ 復(fù)合 ” 數(shù)組 HC[1..n]中。 請參見教材 P149圖 （ a)和（ c) 建議 2： Huffman樹的 存儲結(jié)構(gòu)可采用 順序存儲 結(jié)構(gòu)： (1)教材 P147～ 149內(nèi)容； (2)嚴蔚敏 “ 數(shù)據(jù)結(jié)構(gòu) ” 演示程序 ； (3)習(xí)題集 P149 實習(xí) ； (4)自測卷第 6章上機方案二的源程序。 可參考： 19 typedef struct{ unsigned int weight； //權(quán)值分量（可放大取整） unsigned int parent， lchild， rchild； //雙親和孩子分量 }HTNode， *HuffmanTree； //用動態(tài)數(shù)組存儲 Huffman樹 typedef char**HuffmanCode； //動態(tài)數(shù)組存儲 Huffman編碼表 Huffman樹和 Huffman樹編碼的存儲表示： 0 0 0 r 0 9 2 0 0 19 0 0 7 l p w 3 2 1 雙親 *HuffmanTree或 HT向量 HT[3].parent=9 指針型指針 20 如何編程實現(xiàn) Huffman編碼？ 參見教材 P147 先構(gòu)造 Huffma
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1