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

1、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)用,,2,提前介紹：二叉樹(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ù)，又稱 Hu

2、ffman樹(shù)，用途之一是通信中的壓縮編碼。,3,路 徑：路徑長(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)度之和。,結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積,,預(yù)備知識(shí)：若干術(shù)語(yǔ),樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和,帶權(quán)路徑長(zhǎng)度最小的樹(shù)。,a→e的路徑長(zhǎng)度＝,樹(shù)長(zhǎng)度

3、＝,2,10,4,Huffman樹(shù)簡(jiǎn)介：,樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？,經(jīng)典之例：,WPL=36,WPL=46,WPL= 35,哈夫曼樹(shù)則是：WPL 最小的樹(shù)。,Huffman樹(shù),,Weighted Path Length,,5,(1) 由給定的 n 個(gè)權(quán)值{w0, w1, w2, …, wn-1}，構(gòu)造具有 n 棵擴(kuò)充二叉樹(shù)的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵擴(kuò)充二叉樹(shù) Ti 只有一個(gè)帶有權(quán)值 wi

4、的根結(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)

5、用長(zhǎng)路徑。,,先舉例！,6,例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)實(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)造Huf

6、fman樹(shù)！,7,操作要點(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)值）。,,8,操作要點(diǎn)2：按左0右1對(duì)Huffman樹(shù)的所有分支編號(hào)！,Huffman編碼結(jié)果：d=0, i=10, a=110, n=111WPL=1bit×7＋2bit×5+3b

7、it(2+4)=35,,,,特點(diǎn)：每一碼都不是另一碼的前綴，絕不會(huì)錯(cuò)譯! 稱為前綴碼,——將 Huffman樹(shù) 與 Huffman編碼 掛鉤,9,例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ì)哈夫曼編碼。如果用0～7的二

8、進(jìn)制編碼方案又如何？,,霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長(zhǎng)碼。由于霍夫曼樹(shù)的WPL最小，說(shuō)明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。,解：先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。權(quán)值集合 w={7, 19, 2, 6, 32, 3, 21, 10}，按哈夫曼樹(shù)構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹(shù)。,10,w4={19, 21, 28, 32},為清晰起見(jiàn)，重新排序?yàn)?w={2, 3,

9、 6, 7, 10, 19, 21, 32},5,6,w1={5, 6, 7, 10, 19, 21, 32},w2={7, 10, 11, 19, 21, 32},w3={11, 17, 19, 21, 32},11,17,28,w5={28,32,40},w6={40,60},w7={100},哈夫曼樹(shù),,11,對(duì)應(yīng)的哈夫曼編碼（左0右1）：,Huffman碼的WPL＝2(0.19+0.32+0.21) + 4(0.07+0.06+

10、0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61,WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 但哈夫曼編碼不唯一,,二進(jìn)制碼,12,,另一種結(jié)果表示：,13,哈夫曼譯碼,譯碼過(guò)程是分解電文中字符串，從根出發(fā)，按字母‘0’或‘1’確定找左孩子或右孩子，（即遇‘0’向左，遇‘1’向右）直到葉子結(jié)點(diǎn)

11、，便求得該子串相應(yīng)的子串。,14,例3（實(shí)驗(yàn)二方案3）：設(shè)字符集為26個(gè)英文字母，其出現(xiàn)頻度如下表所示。,,先建哈夫曼樹(shù)，再利用此樹(shù)對(duì)報(bào)文“This program is my favorite”進(jìn)行編碼和譯碼。,要求編程實(shí)現(xiàn)：,15,提示1：霍夫曼樹(shù)中各結(jié)點(diǎn)的結(jié)構(gòu)可以定義為如下5個(gè)分量：,將整個(gè)霍夫曼樹(shù)的結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中：HT[1..n]; 將結(jié)點(diǎn)的編碼存儲(chǔ)在HC[1..n]中。,,提示3：霍夫曼樹(shù)如何構(gòu)造？構(gòu)造好之后又如何求得

12、各結(jié)點(diǎn)對(duì)應(yīng)的霍夫曼編碼？——算法參見(jiàn)教材P147。,提示2：霍夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)結(jié)構(gòu)：,16,小結(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é)的基礎(chǔ)。,補(bǔ)充1：構(gòu)造Huffman樹(shù)的過(guò)程描述,1

13、7,怎樣生成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ù)