樹(shù)轉(zhuǎn)為二叉樹(shù)的方法

1、第6章 樹(shù)和二叉樹(shù)（ Tree & Binary Tree ）6.1 樹(shù)的基本概念6.2 二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)6.4 樹(shù)和森林6.5 赫夫曼樹(shù)及其應(yīng)用1提前介紹：二叉樹(shù)的應(yīng)用平衡樹(shù)排序樹(shù)字典樹(shù)帶權(quán)樹(shù)最優(yōu)樹(shù)特點(diǎn)：左右子樹(shù)深度差 1特點(diǎn)：“左小右大”由字符串構(gòu)成的二叉樹(shù)排序樹(shù)特點(diǎn)：路徑長(zhǎng)度帶權(quán)值 帶權(quán)路徑長(zhǎng)度最短的樹(shù)，又稱 Huffman樹(shù)，用途之一是通信中的壓縮編碼。2路 徑：路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度：帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度：霍 夫 曼 樹(shù)：6.5 Huffman樹(shù)及其應(yīng)用一、最優(yōu)二叉樹(shù)（霍夫曼樹(shù)）由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑上的分支數(shù)目從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之

2、和。結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積預(yù)備知識(shí)：若干術(shù)語(yǔ)debacf g樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和帶權(quán)路徑長(zhǎng)度最小的樹(shù)。ae的路徑長(zhǎng)度樹(shù)長(zhǎng)度2103Huffman樹(shù)簡(jiǎn)介：樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？WPL = wklk k=1nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：WPL=36WPL=46WPL= 35哈夫曼樹(shù)則是：WPL 最小的樹(shù)。Huffman樹(shù)Weighted Path Length4(1) 由給定的 n 個(gè)權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有 n 棵擴(kuò)充二叉樹(shù)的森林F = T0, T1, T2, , Tn-1 ，其中每一棵擴(kuò)充二

3、叉樹(shù) Ti 只有一個(gè)帶有權(quán)值 wi 的根結(jié)點(diǎn)，其左、右子樹(shù)均為空。 (2) 重復(fù)以下步驟, 直到 F 中僅剩下一棵樹(shù)為止： 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹(shù), 做為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)。置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。 在 F 中刪去這兩棵二叉樹(shù)。 把新的二叉樹(shù)加入 F。構(gòu)造霍夫曼樹(shù)的基本思想：構(gòu)造Huffman樹(shù)的步驟（即Huffman算法）：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。先舉例！5例1：設(shè)有4個(gè)字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2, 4，怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法1：等長(zhǎng)編碼。例如用二進(jìn)制編碼來(lái)

4、實(shí)現(xiàn)。 取 d=00，i=01，a=10，n=11怎樣實(shí)現(xiàn)Huffman編碼？法2：不等長(zhǎng)編碼，例如用哈夫曼編碼來(lái)實(shí)現(xiàn)。 取 d=0; i=10, a=110, n=111最快的編碼是哪個(gè)？是非等長(zhǎng)的Huffman碼！先要構(gòu)造Huffman樹(shù)！6操作要點(diǎn)1：對(duì)權(quán)值的合并、刪除與替換在權(quán)值集合7,5,2,4中，總是合并當(dāng)前值最小的兩個(gè)權(quán)構(gòu)造Huffman樹(shù)的步驟：注：方框表示外結(jié)點(diǎn)（葉子，字符對(duì)應(yīng)的權(quán)值）， 圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。7操作要點(diǎn)2：按左0右1對(duì)Huffman樹(shù)的所有分支編號(hào)！dain111000Huffman編碼結(jié)果：d=0, i=10, a=110, n=111WPL=1

5、bit72bit5+3bit(2+4)=35特點(diǎn)：每一碼都不是另一碼的前綴，絕不會(huì)錯(cuò)譯! 稱為前綴碼將 Huffman樹(shù) 與 Huffman編碼 掛鉤8例2（嚴(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ì)哈夫曼編碼。如果用07的二進(jìn)制編碼方案又如何？霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長(zhǎng)碼。由于霍夫曼樹(shù)的WPL最小，說(shuō)明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。解：先

6、將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹(shù)構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹(shù)。9w4=19, 21, 28, 32為清晰起見(jiàn)，重新排序?yàn)?w=2, 3, 6, 7, 10, 19, 21, 322356w1=5, 6, 7, 10, 19, 21, 32w2=7, 10, 11, 19, 21, 32w3=11, 17, 19, 21, 32111071728211940w5=28,32,403260w6=40,60w7=100100bcadegfh哈夫曼樹(shù)10對(duì)應(yīng)的哈夫曼編碼（左0右1）：235611107

7、32172821194060100bcadegfh00000111111100符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman碼的WPL2(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 WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 但哈夫曼編碼不唯一11000011110111010111110111010

8、00001010011100101110111二進(jìn)制碼11另一種結(jié)果表示：12哈夫曼譯碼譯碼過(guò)程是分解電文中字符串，從根出發(fā)，按字母0或1確定找左孩子或右孩子，（即遇0向左，遇1向右）直到葉子結(jié)點(diǎn)，便求得該子串相應(yīng)的子串。13例3（實(shí)驗(yàn)二方案3）：設(shè)字符集為26個(gè)英文字母，其出現(xiàn)頻度如下表所示。51481156357203251頻度zyxwvut字符11611882380頻度p21fq15gr47hsonmlkj字符5710332221364186頻度iedcba空格字符先建哈夫曼樹(shù)，再利用此樹(shù)對(duì)報(bào)文“This program is my favorite”進(jìn)行編碼和譯碼。要求編程實(shí)現(xiàn)：14提

9、示1：霍夫曼樹(shù)中各結(jié)點(diǎn)的結(jié)構(gòu)可以定義為如下5個(gè)分量：charweightparentlchildRchild將整個(gè)霍夫曼樹(shù)的結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中：HT1.n; 將結(jié)點(diǎn)的編碼存儲(chǔ)在HC1.n中。提示3：霍夫曼樹(shù)如何構(gòu)造？構(gòu)造好之后又如何求得各結(jié)點(diǎn)對(duì)應(yīng)的霍夫曼編碼？算法參見(jiàn)教材P147。提示2：霍夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)結(jié)構(gòu)：15小結(jié)：哈夫曼樹(shù)及其應(yīng)用1.Huffman算法的思路：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。2.構(gòu)造Huffman樹(shù)的步驟： 對(duì)權(quán)值的合并、刪除與替換3. Huffman編碼規(guī)則： 左“0” 右“1”，是一種前綴碼也稱為最小冗余編碼、緊致碼，等等，它是數(shù)據(jù)壓縮學(xué)

10、的基礎(chǔ)。補(bǔ)充1：構(gòu)造Huffman樹(shù)的過(guò)程描述16怎樣生成Huffman樹(shù)？ 步驟如下：(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ù)便是赫夫曼樹(shù)。17二叉樹(shù)小結(jié)1、定義和性質(zhì)2、存儲(chǔ)結(jié)構(gòu)3、遍歷4、線索化：線索樹(shù)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)二叉鏈表三叉鏈表先序線索樹(shù)中序線索樹(shù)后