6.6哈夫曼編碼.ppt

先介紹二叉樹的典型應(yīng)用 平衡樹 排序樹 字典樹 帶權(quán)樹 最優(yōu)樹 由字符串構(gòu)成的二叉排序樹特點(diǎn) 路徑帶權(quán)值 例如長(zhǎng)度 是帶權(quán)路徑長(zhǎng)度最短的樹 又稱Huffman樹 用途之一是通信中的壓縮編碼 特點(diǎn) 所有結(jié)點(diǎn)左右子樹深度差 1 特點(diǎn) 所有結(jié)點(diǎn) 左小右大 什么是平衡二叉樹 又稱AVL樹 性質(zhì) 所有結(jié)點(diǎn)左 右子樹深度之差的絕對(duì)值 1若定義結(jié)點(diǎn)的 平衡因子 BF 左子樹深度 右子樹深度則 平衡二叉樹中所有結(jié)點(diǎn)的BF 1 0 1 a 平衡樹 b 不平衡樹 例 判斷下列二叉樹是否AVL樹 1 1 1 1 2 1 1 什么是二叉排序樹 a b 例 下列2種圖形中 哪個(gè)不是二叉排序樹 或是一棵空樹 或者是具有如下性質(zhì)的非空二叉樹 1 左子樹的所有結(jié)點(diǎn)均小于根的值 2 右子樹的所有結(jié)點(diǎn)均大于根的值 3 它的左右子樹也分別為二叉排序樹 想一想 對(duì)它中序遍歷之后是什么效果 什么是帶權(quán)樹 即路徑帶有權(quán)值 例如 6 5Huffman樹及其應(yīng)用 一 Huffman樹二 Huffman編碼 最優(yōu)二叉樹 Huffman樹 Huffman編碼 帶權(quán)路徑長(zhǎng)度最短的樹 不等長(zhǎng)編碼 是通信中最經(jīng)典的壓縮編碼 一 Huffman樹 最優(yōu)二叉樹 路徑 路徑長(zhǎng)度 樹的路徑長(zhǎng)度 帶權(quán)路徑長(zhǎng)度 樹的帶權(quán)路徑長(zhǎng)度 Huffman樹 由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成 路徑上的分支數(shù)目 從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和 結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積 WPL 若干術(shù)語 即樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 帶權(quán)路徑長(zhǎng)度最小的樹 例如 a e的路徑長(zhǎng)度 樹長(zhǎng)度 2 10 Huffman常譯為赫夫曼 霍夫曼 哈夫曼等 WeightedPathLength 樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算 經(jīng)典之例 WPL WPL WPL Huffman樹是WPL最小的樹 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 36 46 35 2 構(gòu)造Huffman樹的步驟 即Huffman算法 1 由給定的n個(gè)權(quán)值 w1 w2 wn 構(gòu)成n棵二叉樹的集合F T1 T2 Tn 即森林 其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn) 其左右子樹均空 2 在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹做為左右子樹構(gòu)造一棵新的二叉樹 且讓新二叉樹根結(jié)點(diǎn)的權(quán)值等于其左右子樹的根結(jié)點(diǎn)權(quán)值之和 3 在F中刪去這兩棵樹 同時(shí)將新得到的二叉樹加入F中 4 重復(fù) 2 和 3 直到F只含一棵樹為止 這棵樹便是Huffman樹 1 構(gòu)造Huffman樹的基本思想 權(quán)值大的結(jié)點(diǎn)用短路徑 權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑 WPL最小的樹 舉例 對(duì)權(quán)值進(jìn)行合并 刪除與替換 在權(quán)值集合 7 5 2 4 中 總是合并當(dāng)前值最小的兩個(gè)權(quán) a 初始 方框表示外結(jié)點(diǎn) 葉子 字符 圓框表示內(nèi)結(jié)點(diǎn) 合并后的權(quán)值 b 合并 2 4 c 合并 5 6 d 合并 7 11 Huffman樹的特點(diǎn) 沒有度為1的結(jié)點(diǎn) 二 Huffman編碼 假設(shè)我們發(fā)送的電文為 ABACCD 它只有四個(gè)字符 只需要2位二進(jìn)制編碼A 00B 01C 10D 11發(fā)送電文的序列為000100101011在傳送電文時(shí) 希望總長(zhǎng)度盡量短 因此出現(xiàn)次數(shù)多的字符適用短的編碼 A 0B 00C 1D 11發(fā)送電文的序列為00001111可以解釋為AAAACCCC AABDD BBCCCC 我們必須使用前綴編碼 PrefixCode PrefixCode前綴碼 任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴 如ABCD四個(gè)字符的前綴編碼分別為A 0B 10C 110D 111 可以利用二叉樹來設(shè)計(jì)前綴編碼 假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi 其編碼長(zhǎng)度為li 電文中只有n種字符 則電文總長(zhǎng)為 若置wi為葉子結(jié)點(diǎn)的權(quán) li恰為從根到葉子的路徑長(zhǎng)度 則恰為二叉樹上帶權(quán)路徑長(zhǎng)度 如何得到使電文總長(zhǎng)最短的前綴編碼 利用赫夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼 并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼 即使所傳電文的總長(zhǎng)度最短 按左 0 右 1 對(duì)Huffman樹的所有分支編號(hào) Huffman編碼結(jié)果 d 0 i 10 a 110 n 111WPL 1bit 7 2bit 5 3bit 2 4 35 小于等長(zhǎng)碼的WPL 36 特征 每一碼不會(huì)是另一碼的前綴 譯碼時(shí)可惟一復(fù)原 Huffman編碼也稱為前綴碼 將Huffman樹與Huffman編碼掛鉤 例 設(shè)有4個(gè)字符d i a n 出現(xiàn)的頻度分別為7 5 2 4 怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快 法1 等長(zhǎng)編碼 如二進(jìn)制編碼 令d 00 i 01 a 10 n 11 則 WPL1 2bit 7 5 2 4 36法2 不等長(zhǎng)編碼 如Huffman編碼 令d 0 i 10 a 110 n 111 則 明確 要實(shí)現(xiàn)Huffman編碼 就要先構(gòu)造Huffman樹 討論 Huffman樹有什么用 頻度高的信息用短碼 反之用長(zhǎng)碼 傳輸效率肯定高 WPL2 1bit 7 2bit 5 3bit 2 4 35 最小冗余編碼 信息高效傳輸 A 1B 00C 011D 0101E 0100 例 假設(shè)字符A B C D E的出現(xiàn)概率為42 28 15 10 5 求電文的總長(zhǎng)度最短的一種編碼 首先構(gòu)建赫夫曼樹 根據(jù)概率 1 由于Huffman樹的WPL最小 說明編碼所需要的比特?cái)?shù)最少 4 Huffman編碼時(shí)是從葉子走到根 而譯碼時(shí)又要從根走到葉子 因此每個(gè)結(jié)點(diǎn)需要增開雙親指針分量 連同結(jié)點(diǎn)權(quán)值共要開5個(gè)分量 5 用計(jì)算機(jī)實(shí)現(xiàn)時(shí) 順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)都要用到 分析Huffman樹和編碼的特點(diǎn) 霍夫曼編碼的基本思想是 出現(xiàn)概率大的信息用短碼 概率小的用長(zhǎng)碼 最小冗余 這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中 2 Huffman樹肯定沒有度為1的結(jié)點(diǎn) 3 一棵有n0個(gè)葉子結(jié)點(diǎn)的Huffman樹 共有2n0 1個(gè)結(jié)點(diǎn) 因?yàn)閚 n0 n1 n2 2n0 1 如何編程實(shí)現(xiàn)Huffman編碼 建議1 Huffman樹中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成5分量形式 將整個(gè)Huffman樹的結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組HT 1 n m 中 各葉子結(jié)點(diǎn)的編碼存儲(chǔ)在另一 復(fù)合 數(shù)組HC 1 n 中 建議2 Huffman樹的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)結(jié)構(gòu) typedefstruct unsignedintweight 權(quán)值分量 可放大取整 unsignedintparent lchild rchild 雙親和孩子分量 HTNode HuffmanTree 用動(dòng)態(tài)數(shù)組存儲(chǔ)Huffman樹typedefchar HuffmanCode 動(dòng)態(tài)數(shù)組存儲(chǔ)Huffman編碼表 Huffman樹和Huffman樹編碼的存儲(chǔ)表示 雙親 HuffmanTree或HT向量 HT 3 parent 9 指針型指針 如何編程實(shí)現(xiàn)Huffman編碼 參見教材P147 先構(gòu)造Huffman樹HT 再求出N個(gè)字符的Huffman編碼HC VoidHuffmanCoding HuffmanTree HT HuffmanCode HC int w intn if n 1 return m 2 n 1 n0個(gè)葉子的HuffmanTree共有2n0 1個(gè)結(jié)點(diǎn) HT HuffmanTree malloc m 1 sizeof HTNode 0單元未用 w存放n個(gè)字符的權(quán)值 for p HT i 1 i n i p w p w 0 0 0 給前n0個(gè)單元初始化for i m i p p 0 0 0 0 對(duì)葉子之后的存儲(chǔ)單元清零for i n 1 i m i 建Huffman樹 從葉子后開始存內(nèi)結(jié)點(diǎn) Select HT i 1 s1 s2 在HT 1 i 1 選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn) 其序號(hào)分別為S1和s2 教材未給出此函數(shù)源碼 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight 續(xù)前 再求出n個(gè)字符的Huffman編碼HC HC HuffmanCode malloc n 1 sizeof char 分配n個(gè)字符編碼的頭指針向量 一維數(shù)組 cd char malloc n sizeof char 分配求編碼的工作空間 n cd n 1 0 編碼結(jié)束符 從cd 0 cd n 1 為合法空間 for i 1 i n i 逐個(gè)字符求Huffman編碼start n 1 編碼結(jié)束符位置for c i f HT i parent f 0 c f f HT f parent 從葉子到根逆向求編碼if HT f lchild c cd start 0 elsecd start 1 HC i char malloc n start sizeof char 為第i個(gè)字符編碼分配空間strcpy HC i 釋放工作空間 HuffmanCoding Huffman編碼舉例 解 先將概率放大100倍 以方便構(gòu)造哈夫曼樹 放大后的權(quán)值集合w 7 19 2 6 32 3 21 10 按哈夫曼樹構(gòu)造規(guī)則 合并 刪除 替換 可得到哈夫曼樹 例1 嚴(yán)題集6 26 假設(shè)用于通信的電文僅由8個(gè)字母 a b c d e f g h 構(gòu)成 它們?cè)陔娢闹谐霈F(xiàn)的概率分別為 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼 如果用0 7的二進(jìn)制編碼方案又如何 類同P148例2 b c a d e g f h 5 11 17 28 40 60 100 1415 w 7 19 2 6 32 3 21 10 請(qǐng)注意 哈夫曼樹樣式不惟一 w 7 19 2 6 32 3 21 10 在機(jī)內(nèi)存儲(chǔ)形式為 b a d e g f h 5 11 17 28 40 60 100 0 1415 如何形成編碼 例如 c的編碼 從葉結(jié)點(diǎn)開始 找到其雙親 判定是雙親的左孩子或右孩子 確定編碼 直到根結(jié)束 0 0 1 1 1 c 對(duì)應(yīng)的哈夫曼編碼 Huffman碼的WPL 2 0 19 0 32 0 21 4 0 07 0 06 0 10 5 0 02 0 03 1 44 0 92 0 25 2 61 3 0 19 0 32 0 21 0 07 0 06 0 10 0 02 0 03 3 二進(jìn)制等長(zhǎng)碼的WPL c 按左0右1標(biāo)注 另一種表示 小結(jié) 哈夫曼樹及其應(yīng)用 1 Huffman算法的思路 權(quán)值大的結(jié)點(diǎn)用短路徑 權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑 2 構(gòu)造Huffman樹的步驟 對(duì)權(quán)值的合并 刪除與替換 3 Huffman編碼規(guī)則 左 0 右 1 又稱為前綴碼 最小冗余編碼 緊致碼等等 它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ) 上機(jī)實(shí)驗(yàn)說明 設(shè)字符集為26個(gè)英文字母 其出現(xiàn)頻度如下表所示 注 若在規(guī)定時(shí)間內(nèi)圓滿實(shí)現(xiàn) 平時(shí)成績(jī)將以滿分計(jì) 要求 先建Huffman樹 再利用此樹對(duì)任一字符串文件進(jìn)行編碼和譯碼 即設(shè)計(jì)一個(gè)Huffman編 譯碼器 本章小結(jié) 1 定義和性質(zhì) 2 存儲(chǔ)結(jié)構(gòu) 3 遍歷 4 線索化 1 2 性質(zhì)有3 2條 孩子 兄弟 線索樹 第6章結(jié)束 1 熟練掌握二叉樹的結(jié)構(gòu)特性 了解相應(yīng)的證明方法 2 熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍 3 遍歷二叉樹是二叉樹各種操作的基礎(chǔ) 實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān) 掌握各種遍歷策略的遞歸算法 靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作 層次遍歷是按另一種搜索策略進(jìn)行的遍歷 本章重點(diǎn) 4 理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系 熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法 二叉樹的線索化過程是基于對(duì)二叉樹進(jìn)行遍歷 而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便 5 熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn) 掌握樹和森林與二叉樹的轉(zhuǎn)換方法 建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提 因此應(yīng)掌握1至2種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法 6 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法 7 了解最優(yōu)樹的特性 掌握建立最優(yōu)樹和哈夫曼編碼的方法 判定一個(gè)結(jié)構(gòu)是否為二叉樹給出二叉樹的遍歷序列畫出某樹的線索二叉樹樹 二叉樹 森林的相互轉(zhuǎn)換 并由一個(gè)結(jié)構(gòu)的特點(diǎn)推到出其余結(jié)構(gòu)的特點(diǎn)由已知的某個(gè)權(quán)值序列求出Huffman樹并計(jì)算其帶權(quán)路徑長(zhǎng)度由已知的某個(gè)權(quán)值序列求其Huffman編碼相關(guān)算法的編寫 2 如何按層次輸出二叉樹中所有結(jié)點(diǎn) 算法思路 既然要求從上到下 從左到右 則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法 此時(shí)絕不能用遞歸算法 技巧 當(dāng)根結(jié)點(diǎn)入隊(duì)后 令其左 右孩子結(jié)點(diǎn)入隊(duì) 而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì) 由此便可產(chǎn)生按層次輸出的效果 附 二叉樹若干典型算法 習(xí)題課 1 如何求二叉樹的深度 或從某個(gè)結(jié)點(diǎn)開始的子樹深度 算法思路 只查各結(jié)點(diǎn)后繼鏈表指針 若左 右 孩子的左 右 指針非空 則層次數(shù)加1 否則函數(shù)返回 算法見附1 算法見附2 算法思路 若不用遞歸 則要實(shí)現(xiàn)二叉樹遍歷的 嵌套 規(guī)則 必用堆棧 迭代方式 可直接用while語句和push pop操作 參見教材P130 131程序 4中序遍歷的非遞歸算法如何實(shí)現(xiàn) 3 如何判別給定二叉樹是否為完全二叉樹 算法思路 完全二叉樹的特點(diǎn)是 沒有左子樹空而右子樹單獨(dú)存在的情況 前k 1層都是滿的 且第k層左邊也滿 技巧 按層次遍歷方式 先把所有結(jié)點(diǎn) 不管當(dāng)前結(jié)點(diǎn)是否有左右孩子 都入隊(duì)列 若為完全二叉樹 則層次遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列 如果序列中出現(xiàn)了空指針 則說明不是完全二叉樹 算法見附3 算法見附4 VoidABC Bitreep intl int 法1 從根開始向下計(jì)算層次 比從葉子往上計(jì)算更簡(jiǎn)單 l h分別表示二叉樹的層次數(shù)和深度 想一想 l和h的初始值應(yīng)設(shè)為多少 開始調(diào)用時(shí) 應(yīng)當(dāng)用ABC p 0 0 若去掉h形參中的 號(hào) 則h不變化 算出的更深層數(shù)不能正確返回 h將永遠(yuǎn)為0 附1 求二叉樹的深度的算法嚴(yán)題集6 44 intBTreeDepth Btree BT BT為二叉樹某結(jié)點(diǎn)的指針 intleftdep rightdep 設(shè)左右兩個(gè)深度 層次計(jì)數(shù)器if BT NULL return 0 當(dāng)前結(jié)點(diǎn)指針為空則立即返回else leftdep BTreeDepth BT left 遍歷當(dāng)前結(jié)點(diǎn)左子樹rightdep BTreeDepth BT right 遍歷當(dāng)前結(jié)點(diǎn)右子樹if leftdep rightdep return leftdep 1 從葉子起計(jì)數(shù)elsereturn rightdep 1 BTreeDepth 法2 遞歸時(shí)從葉子開始向上計(jì)數(shù) 層深者保留 voidLayerOrder BitreeT 層序遍歷二叉樹 InitQueue Q 建一個(gè)空隊(duì) 初始化隊(duì)列 EnQueue Q T 將一個(gè)結(jié)點(diǎn)插入隊(duì)尾的函數(shù)while QueueEmpty Q DeQueue Q p的右孩子入隊(duì) LayerOrder 附2 層次遍歷算法 需要利用隊(duì)列 嚴(yán)題集6 47 當(dāng)孩子為空時(shí)不要將空指針入隊(duì) 附3 判別給定二叉樹是否為完全二叉樹嚴(yán)題集6 49 intIsFull Bitree BitreeT 是完全二叉樹返回1 否則返0 InitQueue Q 建隊(duì) 初始化隊(duì)列 flag 0 標(biāo)志初始化EnQueue Q T 結(jié)點(diǎn)T入隊(duì) 空指針也要入隊(duì) while QueueEmpty Q DeQueue Q 執(zhí)行至此必為隊(duì)空且中間無空指針 完全二叉 IsFull Bitree StatusInOrderTrav BiTreeT Status Visit TElemTypee 此處Visit意思是對(duì)元素e的一種操作InitStack S p T 初始化棧while p StackEmpty S 樹不空或棧不空則開始遍歷 if p Push S p p p lchild 根指針進(jìn)棧 遍歷左子樹else Pop S p 根指針退棧if Visit p data returnERROR 訪問根結(jié)點(diǎn)p p rchild 遍歷右子樹 else whilereturnOK InOrderTrav 附4 中序遍歷的非遞歸算法 或稱迭代算法 見教材P131 1 設(shè)高度為h的二叉樹上只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn) 則此類二叉樹所包含的結(jié)點(diǎn)數(shù)至少為 至多為 2h 1 2h 1 2 如圖所示的二叉樹的中序遍歷序列是 dfebagc 3 已知某二叉樹的后序遍歷序列是dabec 中序遍歷序列是debac 則它的前序遍歷序列是 cedba 4 已知某二叉樹的前序遍歷序列是abdgcefh 中序遍歷序列是dgbaechf 則其后序遍歷序列是 gdbehfca 5 某二叉樹的前序序列為stuwv 中序序列為uwtvs 則其后序序列為 wuvts 6 任何一棵二叉樹的葉結(jié)點(diǎn)在先序 中序和后序遍歷序列中的相對(duì)次序 A不發(fā)生改變B發(fā)生改變C不能確定 A 7 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu) 最佳方案是二叉樹采用 存儲(chǔ)結(jié)構(gòu)A二叉鏈表B廣義表C三叉鏈表D順序存儲(chǔ) C 8 線索二叉樹是一種 結(jié)構(gòu)A邏輯B邏輯和存儲(chǔ)C物理D線性 C 9 一棵二叉樹的結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)采用順序存儲(chǔ) 見數(shù)組t 則其二叉鏈表表示形式為 10 按自上而下 從左到右的次序給深度為k的完全二叉樹的結(jié)點(diǎn)編號(hào) 根結(jié)點(diǎn)編號(hào)為1 則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)為 2k 2 1 11 一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹總共有 個(gè)葉子 有 個(gè)非終端結(jié)點(diǎn) 2h 1 其中 n 2h 1 2h 1 1 12 現(xiàn)有某二叉樹的中序遍歷序列為abc 問可以有 種不