資源描述：
《嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu) (11).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、1第6章樹(shù)和二叉樹(shù)（Tree&BinaryTree）6.1樹(shù)的基本概念6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.5赫夫曼樹(shù)及其應(yīng)用6.5Huffman樹(shù)及其應(yīng)用一、Huffman樹(shù)二、Huffman編碼最優(yōu)二叉樹(shù)Huffman樹(shù)Huffman編碼帶權(quán)路徑長(zhǎng)度最短的樹(shù)不等長(zhǎng)編碼是通信中最經(jīng)典的壓縮編碼2樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？WPL=?wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：WPL=WPL=WPL=Huffman樹(shù)是WPL最小的樹(shù)樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和3646353一、Huff
2、man樹(shù)（最優(yōu)二叉樹(shù)）路徑：路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度：帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度：Huffman樹(shù)：由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑上的分支數(shù)目。從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積（WPL）若干術(shù)語(yǔ)：debacfg即樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和帶權(quán)路徑長(zhǎng)度最小的樹(shù)。例如：a→e的路徑長(zhǎng)度＝樹(shù)長(zhǎng)度＝210Huffman常譯為赫夫曼、霍夫曼、哈夫曼、胡夫曼等WeightedPathLength41.構(gòu)造Huffman樹(shù)的基本思想：例：設(shè)有4個(gè)字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2,4，怎樣編碼才能使它們組成
3、的報(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樹(shù)討論：Huffman樹(shù)有什么用？權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。WPL最小的樹(shù)頻度高的信息用短碼，低的用長(zhǎng)碼，傳輸效率肯定高！WPL2=1bit×7＋2bit×5+3bit×(2+4)=35最小冗余編碼、信息高效傳輸52.構(gòu)造Huffman樹(shù)的步驟（即Huff
4、man算法）：(1)由給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,…,Tn}（即森林），其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。(2)在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)做為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且讓新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值等于其左右子樹(shù)的根結(jié)點(diǎn)權(quán)值之和。(3)在F中刪去這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。(4)重復(fù)(2)和(3),直到F只含一棵樹(shù)為止。這棵樹(shù)便是Huffman樹(shù)。怎樣證明它就是WPL最小的最優(yōu)二叉樹(shù)？參考《信源編碼》總之，每次合并當(dāng)前值最小的兩個(gè)權(quán)。(此樹(shù)特征：沒(méi)有度為1的結(jié)點(diǎn))6
5、step1：對(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}誰(shuí)左誰(shuí)右？不規(guī)定就不會(huì)惟一7step2：按左“0”右“1”對(duì)Huffman樹(shù)的所有分支編號(hào)dain111000Huffman編碼結(jié)果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等長(zhǎng)碼的WPL=36）特征：每一碼不會(huì)是另一碼的前綴，譯碼時(shí)可惟一復(fù)原Huffm
6、an編碼也稱為前綴碼——將Huffman樹(shù)與Huffman編碼掛鉤8二、Huffman編碼哈夫曼編碼的基本思想是——出現(xiàn)概率大的信息用短碼，概率小的用長(zhǎng)碼,最小冗余Huffman編碼不等長(zhǎng)編碼是通信中最經(jīng)典的壓縮編碼按左“0”右“1”對(duì)Huffman樹(shù)的所有分支編號(hào)如何將Huffman樹(shù)與Huffman編碼掛鉤?9本節(jié)重點(diǎn)：如何編程實(shí)現(xiàn)Huffman編碼？建議1：Huffman樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成4或5分量形式：charweightparentlchildrchild將整個(gè)Huffman樹(shù)的結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組HT[1..n..m]中;（Huffman樹(shù)內(nèi)
7、外結(jié)點(diǎn)總數(shù)m=2n-1）各葉子結(jié)點(diǎn)的編碼存儲(chǔ)在另一“復(fù)合”數(shù)組HC[1..n]中。(n個(gè)權(quán)值就是n個(gè)葉子,將對(duì)應(yīng)n個(gè)不同碼串)建議2：Huffman樹(shù)的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)結(jié)構(gòu)：即：先構(gòu)造Huffman樹(shù)HT再求出n個(gè)權(quán)值/字符的Huffman編碼HC參見(jiàn)教材P14710m=n0+n2=n+(n-1)=2n-1Huffman編碼舉例解：先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。放大后的權(quán)值集合w={7,19,2,6,32,3,21,10}，按哈夫曼樹(shù)構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹(shù)。例1【嚴(yán)題集6.26③】：假設(shè)用于通信的電文僅由8個(gè)字母{a
8、,b,c,d,e,f,g,h}構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別為{
