哈夫曼樹的構造

主講教師：尹紅麗《數(shù)據(jù)結構》課程哈夫曼樹及其應用目錄CONTENTS

哈夫曼樹的定義

哈夫曼編碼

哈夫曼樹的構造哈夫曼樹的定義1路徑：從一個結點到另一個結點間的分支路徑長度：路徑上的分支數(shù)目。結點的權：結點被賦予的有著某種意義的實數(shù)結點的帶權路徑長度：從根到該結點間的路徑長度與該結點的權的乘積。二叉樹的帶權路徑長度：二叉樹中所有葉子結點的帶權路徑長度之和。WPL=2×3+2×2+2×4+2×5=28A→E的路徑長度＝DABCEFG23245D結點的帶權路徑長度=2×3=6哈夫曼樹的定義1哈夫曼樹：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹。例：給定4個葉子結點，其權值分別為{2，3，4，7}，可以構造出形狀不同的多個二叉樹。WPL=2×2+3×2+4×2+7×2=32WPL=2×3+3×3+4×2+7×1=30324723477423WPL=2×1+3×2+4×3+7×3=41特點：權值越大的葉子結點越靠近根結點，權值越小的葉子結點越遠離根結點。第1步：初始化3524第2步：選取與合并325第3步：刪除與加入5432

5哈夫曼樹的構造2⑴初始化：由給定的n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結點的權值最小的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；給定4個葉子結點，其權值分別為{2，4，5，3}構造一棵哈夫曼樹W＝{2，4，5，3}哈夫曼樹的構造過程重復第2步：選取與合并5432

554

9重復第3步：刪除與加入

554

932哈夫曼樹的構造2⑷重復⑵、⑶兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。

554

932

554

93214哈夫曼樹的構造2W＝{2，4，5，3}哈夫曼樹的構造過程重復第2步：選取與合并重復第3步：刪除與加入⑷重復⑵、⑶兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。1454

9325等長編碼：不等長編碼：A

B

C

D00

01

10

11發(fā)送：AB

ACCCCD

AB00

010010

10

10

10

110001—長度為20為了縮短傳送信息的總長度，讓出現(xiàn)頻率高的字符具有較短的編碼，出現(xiàn)頻率低的字符具有較長的編碼A

B

C

D

1

10

0

01發(fā)送：ABACCCCDAB1

1010

0

0

0

01110—長度為131101可以譯為AACA、ABA、AAD

為此引入前綴編碼的概念哈夫曼編碼3利用二叉樹進行前綴編碼01abcd1100從根結點到葉子結點的路徑上以分支字符組成的字符串作為葉子節(jié)點的編碼——前綴編碼哈夫曼編碼3約定左分支表示字符‘0’

右分支表示字符‘1’

哈夫曼編碼：以字符出現(xiàn)的頻率作權，構造一棵哈夫曼樹，由此得到的前綴編碼稱哈夫曼編碼——總長最短的二進制前綴編碼前綴編碼：任一字符的編碼都不能是其他字符編碼的前綴的不等長編碼。例：一組字符{A,B,C,D,E,F,G}出現(xiàn)的頻率分別是{9,11,5,7,8,2,3}，設計最經(jīng)濟的編碼方案。95235101911268715450000001111