樹轉為二叉樹的方法

1、1,第6章 樹和二叉樹（ Tree & Binary Tree ）,,6.1 樹的基本概念6.2 二叉樹6.3 遍歷二叉樹和線索二叉樹6.4 樹和森林6.5 赫夫曼樹及其應用,,2,提前介紹：二叉樹的應用,,平衡樹——排序樹——字典樹——帶權樹——最優(yōu)樹——,特點：左右子樹深度差 ≤1特點：“左小右大”由字符串構成的二叉樹排序樹特點：路徑長度帶權值 帶權路徑長度最短的樹，又稱 Hu

2、ffman樹，用途之一是通信中的壓縮編碼。,3,路 徑：路徑長度：樹的路徑長度：帶權路徑長度：樹的帶權路徑長度：霍 夫 曼 樹：,6.5 Huffman樹及其應用,一、最優(yōu)二叉樹（霍夫曼樹）,由一結點到另一結點間的分支所構成,路徑上的分支數目,從樹根到每一結點的路徑長度之和。,結點到根的路徑長度與結點上權的乘積,,預備知識：若干術語,樹中所有葉子結點的帶權路徑長度之和,帶權路徑長度最小的樹。,a→e的路徑長度＝,樹長度

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

4、的根結點，其左、右子樹均為空。 (2) 重復以下步驟, 直到 F 中僅剩下一棵樹為止： ① 在 F 中選取兩棵根結點的權值最小的擴充二叉樹, 做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。 ② 在 F 中刪去這兩棵二叉樹。 ③ 把新的二叉樹加入 F。,構造霍夫曼樹的基本思想：,構造Huffman樹的步驟（即Huffman算法）：,權值大的結點用短路徑，權值小的結點

5、用長路徑。,,先舉例！,6,例1：設有4個字符d,i,a,n，出現的頻度分別為7,5,2, 4，怎樣編碼才能使它們組成的報文在網絡中傳得最快？,法1：等長編碼。例如用二進制編碼來實現。 取 d=00，i=01，a=10，n=11,,怎樣實現Huffman編碼？,法2：不等長編碼，例如用哈夫曼編碼來實現。 取 d=0; i=10, a=110, n=111,最快的編碼是哪個？,,是非等長的Huffman碼！,先要構造Huf

6、fman樹！,7,操作要點1：對權值的合并、刪除與替換——在權值集合{7,5,2,4}中，總是合并當前值最小的兩個權,構造Huffman樹的步驟：,注：方框表示外結點（葉子，字符對應的權值）， 圓框表示內結點（合并后的權值）。,,8,操作要點2：按左0右1對Huffman樹的所有分支編號！,Huffman編碼結果：d=0, i=10, a=110, n=111WPL=1bit×7＋2bit×5+3b

7、it(2+4)=35,,,,特點：每一碼都不是另一碼的前綴，絕不會錯譯! 稱為前綴碼,——將 Huffman樹 與 Huffman編碼 掛鉤,9,例2（嚴題集6.26③）：假設用于通信的電文僅由8個字母 {a, b, c, d, e, f, g, h} 構成，它們在電文中出現的概率分別為{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，試為這8個字母設計哈夫曼編碼。如果用0～7的二

8、進制編碼方案又如何？,,霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長碼。由于霍夫曼樹的WPL最小，說明編碼所需要的比特數最少。這種編碼已廣泛應用于網絡通信中。,解：先將概率放大100倍，以方便構造哈夫曼樹。權值集合 w={7, 19, 2, 6, 32, 3, 21, 10}，按哈夫曼樹構造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。,10,w4={19, 21, 28, 32},為清晰起見，重新排序為: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},哈夫曼樹,,11,對應的哈夫曼編碼（左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 但哈夫曼編碼不唯一,,二進制碼,12,,另一種結果表示：,13,哈夫曼譯碼,譯碼過程是分解電文中字符串，從根出發(fā)，按字母‘0’或‘1’確定找左孩子或右孩子，（即遇‘0’向左，遇‘1’向右）直到葉子結點

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

12、各結點對應的霍夫曼編碼？——算法參見教材P147。,提示2：霍夫曼樹的存儲結構可采用順序存儲結構：,16,小結：哈夫曼樹及其應用,,1.Huffman算法的思路：——權值大的結點用短路徑，權值小的結點用長路徑。,2.構造Huffman樹的步驟： 對權值的合并、刪除與替換,3. Huffman編碼規(guī)則： 左“0” 右“1”，是一種前綴碼也稱為最小冗余編碼、緊致碼，等等，它是數據壓縮學的基礎。,補充1：構造Huffman樹的過程描述,1

13、7,怎樣生成Huffman樹？ 步驟如下：,(1) 由給定的 n 個權值{w1, w2, …, wn}構成n棵二叉樹的集合（即森林）F = { T1, T2, …, Tn }，其中每棵二叉樹 Ti 中只有一個帶權為 wi 的根結點，其左右子樹均空。(2) 在F 中選取兩棵根結點的權值最小的樹 做為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。(3) 在F 中刪去這兩棵樹，同時將新得到的二叉樹