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

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

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

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

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

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

6、將概率放大100倍，以方便構(gòu)造哈夫曼樹。權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。9w4=19, 21, 28, 32為清晰起見，重新排序為: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哈夫曼樹10對應(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二進制碼11另一種結(jié)果表示：12哈夫曼譯碼譯碼過程是分解電文中字符串，從根出發(fā)，按字母0或1確定找左孩子或右孩子，（即遇0向左，遇1向右）直到葉子結(jié)點，便求得該子串相應(yīng)的子串。13例3（實驗二方案3）：設(shè)字符集為26個英文字母，其出現(xiàn)頻度如下表所示。51481156357203251頻度zyxwvut字符11611882380頻度p21fq15gr47hsonmlkj字符5710332221364186頻度iedcba空格字符先建哈夫曼樹，再利用此樹對報文“This program is my favorite”進行編碼和譯碼。要求編程實現(xiàn)：14提

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

10、的基礎(chǔ)。補充1：構(gòu)造Huffman樹的過程描述16怎樣生成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) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。這棵樹便是赫夫曼樹。17二叉樹小結(jié)1、定義和性質(zhì)2、存儲結(jié)構(gòu)3、遍歷4、線索化：線索樹順序結(jié)構(gòu)鏈式結(jié)構(gòu)二叉鏈表三叉鏈表先序線索樹中序線索樹后