6 6Huffman樹基本概念 構(gòu)造 編碼 1 基本概念路徑 從一個結(jié)點到另一個結(jié)點之間的分支 路徑長度 路徑上分支數(shù)目 結(jié)點的路徑長度 從根結(jié)點到該結(jié)點的路徑長度 樹的路徑長度 樹中每個結(jié)點的路徑長度之和 完全二叉樹這種長度最短的二叉樹 結(jié)點的帶權(quán)路徑長度 該結(jié)點的路徑長度 結(jié)點的權(quán)值樹的帶權(quán)路徑長度 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 記作 WPL wklk例如最優(yōu)二叉樹 在所有含n個葉子結(jié)點 并帶相同權(quán)值的二叉樹中 必存在WPL最小的二叉樹 又叫Huffman樹 W 7 2 4 5 9 A E D B C B C D A E 7 2 4 9 5 7 2 4 5 9 WPL1 wklk 7 2 5 2 2 3 4 3 9 2 60 WPL2 wklk 7 4 9 4 5 3 4 2 2 1 89 在解決某些判定問題時 利用Huffman樹可得到最佳判定算法例如 某廠生產(chǎn)螺釘 要求直徑為d 誤差 現(xiàn)測量某螺釘直徑 方法與標(biāo)準(zhǔn)的比較 判定樹 d d d d 5 10 50 25 10 WPL 5 3 10 3 50 2 25 2 10 2 概率最大的最靠近根判斷 2 Huffman樹的構(gòu)造 自底向上 A 7 D 5 E 9 F2 F3 W 7 2 4 5 9 接上頁 F4 F5 根的權(quán)值為27WPL 7 2 2 3 4 3 5 2 9 2 60 Huffman樹形態(tài)不唯一 構(gòu)造過程 Huffman算法 1 n個權(quán)值構(gòu)成n棵獨立二叉樹的森林F T1 Tn 2 在森林中選出兩棵根權(quán)值最小的二叉樹作為左右子樹 構(gòu)造二叉樹 根權(quán)值為左右子樹的和 3 在F中刪除這兩棵 新構(gòu)成的添加到F中 4 重復(fù) 2 和 3 直到F中含一棵二叉樹為止 兩個結(jié)論 1 在Huffman樹中沒有度為1的結(jié)點 2 一棵有n個葉子結(jié)點的Huffman樹共有2n 1個結(jié)點 證明 設(shè)總結(jié)點數(shù)為m個 葉子n個 度為1的n1個 度為2的n2個m n n1 n2由性質(zhì)3n n2 1所以n2 n 1m n n1 n2 n n1 n 1 2n n1 1有 1 得n1 0所以m 2n 0 1 2n 1 3 Huffman編碼 1 等長編碼 2 不等長編碼 出現(xiàn)多的字符采用短碼 總長短了 但出現(xiàn)二義性 3 前綴編碼 一個字符的編碼都不是另一個字符的編碼的前綴 ABCD00011011 兩位一分進(jìn)行譯碼 ABCD000111 用二叉樹實現(xiàn) 左分支0 右分支1 A 00B 01C 1 4 Huffman編碼 設(shè)計Huffman樹而得到的編碼 例如 有8種字符 概率如下 0 05 0 29 0 07 0 08 0 14 0 23 0 03 0 11 解 同時擴(kuò)大100倍 得權(quán)值集合 5 29 7 8 14 23 3 11 設(shè)計Huffman編碼 WPL 0 23 2 0 11 3 Huffman編碼0 05 01100 29 100 07 11100 08 11110 14 1100 23 000 03 01110 11 010 作業(yè) 本章小結(jié)1 掌握樹的定義 表示形式和術(shù)語 二叉樹通用 掌握樹的存儲結(jié)構(gòu) 孩子 兄弟表示 掌握樹與二叉樹的轉(zhuǎn)換了解樹的ADT定義與樹和森林遍歷2 掌握二叉樹的ADT定義 特點 結(jié)點的形態(tài) 性質(zhì) 存儲結(jié)構(gòu) 二叉鏈表 掌握二叉樹的遍歷 線索的方法掌握遍歷算法的應(yīng)用掌握二叉樹與樹和森林的轉(zhuǎn)換掌握Huffman樹概念 構(gòu)造和編碼