6.6哈夫曼編碼.ppt

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