哈夫曼樹及其應(yīng)用教案

1、 數(shù)據(jù)結(jié)構(gòu) 教案授課時(shí)間11.9第17次課授課章節(jié)教學(xué)方法與手段使用教材和主要參考書6.6 哈夫曼樹及其應(yīng)用多媒體任課教師及職稱課時(shí)安排鄭志華2數(shù)據(jù)結(jié)構(gòu) （c 語言版）嚴(yán)蔚敏著，清華大學(xué)出版社教學(xué)目的與要求：哈夫曼樹及其應(yīng)用，構(gòu)造哈夫曼樹、哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算；教學(xué)重點(diǎn)，難點(diǎn)：哈夫曼樹及其應(yīng)用，構(gòu)造哈夫曼樹、哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算；教學(xué)內(nèi)容：66哈夫曼樹及其應(yīng)用6.6.1 最優(yōu)二叉樹（huffman 樹）哈夫曼樹又叫最優(yōu)二叉樹，它是由 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度wpl 最短的二叉樹。1、基本術(shù)語路徑和路徑長(zhǎng)度樹的路徑長(zhǎng)度結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度

2、樹的帶權(quán)路徑長(zhǎng)度 huffman 樹（最優(yōu)二叉樹）路徑：若在一棵樹中存在著一個(gè)結(jié)點(diǎn)序列 k1，k2 kj，使得 ki 是 k i+1(1ij) 的父親，則該結(jié)點(diǎn)序列是 k1 到 kj 的路徑路徑長(zhǎng)度:從 k1 到 kj 所經(jīng)過的分支數(shù)稱為這兩點(diǎn)間的路徑長(zhǎng)度 。 數(shù)據(jù)結(jié)構(gòu) 教案 樹的路徑長(zhǎng)度:樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 結(jié)點(diǎn)的權(quán)：樹中的結(jié)點(diǎn)賦予的一定意義上的實(shí)數(shù)稱之為該結(jié)點(diǎn)的權(quán) 樹的帶權(quán)路徑長(zhǎng)度定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 wpl(t) = swklk (對(duì)所有葉子結(jié)點(diǎn))。在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的 m 叉樹中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹，稱為“最優(yōu)樹”。

3、最優(yōu)二叉樹（也稱 huffman 樹）：它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度 wpl 最小的二叉樹。2、為何要構(gòu)造哈夫曼樹3、如何構(gòu)造哈夫曼樹哈夫曼算法：（1）根據(jù)給定的 n 個(gè)權(quán)值 w1, w2, , wn，構(gòu)造 n 棵二叉樹的集合 f = t1,t2, , tn，其中每棵二叉樹中均只含一個(gè)帶權(quán)值 為 wi 的根結(jié)點(diǎn)，其左、右子樹為空樹；（2）在 f 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；（3）從 f 中刪去這兩棵樹，同時(shí)加入剛生成的新樹；（4）重復(fù) (2) 和 (3) 兩

4、步，直至 f 中只含一棵樹為止。例 1: 已知權(quán)值 w= 6，7，2，3，5，11，12 ，試構(gòu)造一棵哈夫曼樹，并求加權(quán)路徑長(zhǎng)度6.6.2 哈夫曼編碼1 數(shù)據(jù)結(jié)構(gòu) 教案1、問題的提出通訊中常需要將文字轉(zhuǎn)換成二進(jìn)制字符串電文進(jìn)行傳送。文字電文，稱為編碼。反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，電文文字，稱為譯碼。反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，電文文字，稱為譯碼。設(shè)有 n 種字符，每種字符出現(xiàn)的次數(shù)為 wi ,其編碼長(zhǎng)度為 li ( i=1,2,n)，則整個(gè)電文總長(zhǎng)度為 wi li ，要得到最短的電文，即使得 wi li 最小。也就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵 huffman

5、樹，并規(guī)定左分支編碼位 0，右分支編碼為 1，則字符的編碼就是從根到該字符所在的葉結(jié)點(diǎn)的路徑上的分支編號(hào)序列。用構(gòu)造 huffman 樹編出來的碼，稱為 huffman 編碼。2. 哈夫曼編碼的構(gòu)造方法（1）.構(gòu)造 huffman 樹（2）.產(chǎn)生 huffman 編碼2 數(shù)據(jù)結(jié)構(gòu) 教案復(fù)習(xí)思考題、作業(yè)題：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn) 8 種字符，其概率分別為0.05, 0.29, 0.07, 0.08,0.14, 0.23, 0.03, 0.11試設(shè)計(jì)哈夫曼編碼下次課預(yù)習(xí)要點(diǎn)圖實(shí)施情況及教學(xué)效果分析按預(yù)定計(jì)劃順利進(jìn)行，效果良好學(xué)院審核意見該教案教學(xué)目的明確，教學(xué)內(nèi)容先進(jìn)，課時(shí)設(shè)計(jì)合理， 重

6、點(diǎn)那點(diǎn)把握準(zhǔn)確，符合信息學(xué)院教學(xué)要求，同意實(shí)施。學(xué)院負(fù)責(zé)人簽字劉方愛年月日哈夫曼樹的構(gòu)造過程中應(yīng)注意的問題哈夫曼樹的構(gòu)造過程中應(yīng)注意的問題2007-07-182007-07-18哈夫曼樹（huffman 樹）是帶權(quán)路徑長(zhǎng)度最小的二叉樹。根據(jù)哈夫曼樹的定義，一棵二叉樹要使其帶權(quán)路徑長(zhǎng)度最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。哈夫曼依據(jù)這一特點(diǎn)提出了哈夫曼算法，其基本思想是： 初始化：由給定的 n 個(gè)權(quán)值w1，w2，wn構(gòu)造 n 棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合 ft1，t2，tn；3 數(shù)據(jù)結(jié)構(gòu) 教案 選取與合并：在 f 中選取根結(jié)點(diǎn)的權(quán)值最小

7、的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和； 刪除與加入：在集合 f 中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合 f 中； 重復(fù)、兩步，當(dāng)集合 f 中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。通過上述 huffman 樹的構(gòu)造過程，我們可以得到如下要點(diǎn)： 當(dāng)有 n 個(gè)權(quán)值（相應(yīng)的 huffman 樹中有 n 個(gè)葉子），共需合并 n-1 次； 每合并一次產(chǎn)生一個(gè)分支結(jié)點(diǎn)，經(jīng)過 n-1 次合并后得到的 huffman 樹中共有 2n-1 個(gè)結(jié)點(diǎn)，其中有 n-1 個(gè)分支結(jié)點(diǎn)； 在 huffman 樹中只有度為 0（葉

8、子結(jié)點(diǎn)）和度為 2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為 1 的結(jié)點(diǎn)； 算法要求選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹作為左右子樹構(gòu)造一棵新的二叉樹，但并沒有要求哪一棵作左子樹，哪一棵作右子樹，所以左右子樹的順序是任意的； 對(duì)同一組權(quán)值可以構(gòu)造出不同的 huffman 樹，但是他們的帶權(quán)路徑長(zhǎng)度相同。在建立 huffman 樹的過程中有以下三種常見的錯(cuò)誤： 在合并中不是選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹（包括已合并的和未合并的），而是選取未合并的根結(jié)點(diǎn)權(quán)值最小的一棵二叉樹與已經(jīng)合并的二叉樹合并，如圖 5-10 所示。 每次都是在未合并的二叉樹中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵子樹，如圖 5-11 所示。 有時(shí)沒有嚴(yán)格按照哈夫曼算法也構(gòu)造出帶權(quán)路徑長(zhǎng)度與哈夫曼樹相同的二叉樹，但那只是巧合，沒有規(guī)律性， 而沒有規(guī)律性的解法不利于用計(jì)算機(jī)進(jìn)行處理。4 數(shù)據(jù)結(jié)構(gòu) 教案哈夫曼樹就是最優(yōu)二叉查找樹,對(duì)于帶權(quán)的二叉樹的查找,權(quán)值最大的離根結(jié)點(diǎn)最近,按照這一思路,帶權(quán)結(jié)點(diǎn)所構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度 wpl 最小的二叉樹,將其應(yīng)用于計(jì)算機(jī)通信中數(shù)據(jù)編碼技術(shù)可大大縮短電文