大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第五章：樹和二叉樹-第六節(jié)-哈夫曼樹及其應(yīng)用

第六節(jié)哈夫曼樹及其應(yīng)用

一、最優(yōu)二叉樹(哈夫曼樹)

1.樹的路徑長(zhǎng)度

樹的路徑長(zhǎng)度是從樹根到樹中每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。在結(jié)點(diǎn)數(shù)

目相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。

2.樹的帶權(quán)路徑長(zhǎng)度(WPL)

結(jié)點(diǎn)的權(quán)：在一些應(yīng)用中，賦予樹中結(jié)點(diǎn)的一個(gè)有某種意義的實(shí)

數(shù)。

結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的

乘積。

樹的帶權(quán)路徑長(zhǎng)度(WPL):定義為樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度

之和。

3.最優(yōu)二叉樹或哈夫曼樹

帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。

【例】給定4個(gè)葉子結(jié)點(diǎn)a,b,c和d,分別帶權(quán)8,5,4和2。

構(gòu)造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權(quán)路徑長(zhǎng)度分別

為：

(a):WPL=8x3+5x3+2xl+4x2=49

(b):WPL=8x3+5x2+2x3+4xl=44

(c):WPL=8xl+5x2+2x3+4x3=36

其中(c)樹的WPL最小，可以驗(yàn)證，它就是哈夫曼樹。

二、哈夫曼算法

1、構(gòu)造哈夫曼樹的方法：

①將給定的權(quán)值按照從小到大排列成{WI,W2,Wm}，并

且構(gòu)造出樹林F={T|,T2,...,Tm}o此時(shí)，其中的每棵樹TiQwE

m）為左、右子樹均為空的二叉樹，二叉樹的根結(jié)點(diǎn)的權(quán)值為Wi。

②把F中樹根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹1和T2合并為一棵新

的二叉樹T（T的左子樹為Ti,右子樹為T2），并令T的根結(jié)點(diǎn)的權(quán)

值為Ti和T2的根結(jié)點(diǎn)的權(quán)值之和，然后將T按其根結(jié)點(diǎn)的權(quán)值大小

依次加入到樹林F中。同時(shí)，從F中刪去Ti和T2這兩棵二叉樹。

③重復(fù)步驟②，直到構(gòu)造成一棵哈夫曼樹。

【真題選解】

（例題?填空題）用6個(gè)權(quán)值分別為6、13、18、30、7和16的結(jié)

點(diǎn)構(gòu)造一棵哈夫曼（Huffman）樹，該樹的帶權(quán)路徑長(zhǎng)度為。

隱藏答案

【解析】用6個(gè)權(quán)值構(gòu)造的過(guò)程如下圖

90

構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度=(16+18+30)*2+13*3+

(6+7)*4=219

2、哈夫曼樹的特點(diǎn)：

①在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近。

②若有no個(gè)權(quán)值，需要進(jìn)行no-1次合并，構(gòu)造成為哈夫曼樹。

③哈夫曼樹沒(méi)有度為1的結(jié)點(diǎn)。

④由no個(gè)權(quán)值構(gòu)成的哈夫曼樹，葉結(jié)點(diǎn)數(shù)為no,度為2的結(jié)點(diǎn)數(shù)

為no-1，結(jié)點(diǎn)總數(shù)為no+ri2=no+no-l=2no-l0

⑤給定一組權(quán)值，構(gòu)造出的哈夫曼樹的形態(tài)可能不唯一，但它們

的帶權(quán)路徑長(zhǎng)度都一樣。

三、哈夫曼編碼

1、編碼的概念

(1)編碼和解碼

數(shù)據(jù)壓縮過(guò)程稱為編碼。即將文件中的每個(gè)字符均轉(zhuǎn)換為一個(gè)唯一

的二進(jìn)制位串。

數(shù)據(jù)解壓過(guò)程稱為解碼。即將二進(jìn)制位串轉(zhuǎn)換為對(duì)應(yīng)的字符。

(2)前綴碼方案

對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其它字

符的編碼的前綴，這種編碼稱為前綴(編)碼。

【真題選解】

(例題?單選題)下述編碼中不是前綴碼的是()

A.(00,01,10,11)

B.(0,1,00,11)

C.(0,10,110,111)

D.(l,01,000,001)

隱藏答案

【答案】B

【解析】四個(gè)選項(xiàng)中除選項(xiàng)B外，其它三個(gè)選項(xiàng)的編碼滿足任一字

符的編碼都不是其它字符的編碼的前綴。

2、哈夫曼編碼

設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率

作為權(quán)構(gòu)造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。

【真題選解】

(例題?算法題)假設(shè)通信電文使用的字符集為{a,b,c,d,e,

f,g,h},各字符在電文中出現(xiàn)的頻度分別為：7,26,2,28,13,

10,3,11,試為這8個(gè)字符設(shè)計(jì)哈夫曼編碼。要求：

(1)畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點(diǎn)的權(quán)值不大于右

孩子結(jié)點(diǎn)的權(quán)值)；

(2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個(gè)字符對(duì)應(yīng)的

編碼。

隱藏答案

【解析】先按照權(quán)值構(gòu)造哈夫曼樹，注意要滿足題目的要求：樹中

左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值。構(gòu)造過(guò)程如下圖：

2CgCgC

(1)(2)(3)(4)

到這里就很容易寫出每個(gè)字符的哈夫曼編碼了。

【答案】

(2)各字符的編碼：a(0101),b(10),c(01000),d

(11),e(Oil),f(000)

g(01001)h(001)

注意：每個(gè)字符的編碼都不是另外一個(gè)編碼的前綴。

當(dāng)前講授

本章小結(jié)