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

1、《 數(shù)據(jù)結(jié)構(gòu) 》教案授課時(shí)間 11.9 第 17 次課 授課章節(jié) 6.6 哈夫曼樹(shù)及其應(yīng)用 任課教師及職稱 鄭志華教學(xué)方法與手段 多媒體 課時(shí)安排 2使用教材和主要參考書(shū)《數(shù)據(jù)結(jié)構(gòu)》（C 語(yǔ)言版）嚴(yán)蔚敏著，清華大學(xué)出版社教學(xué)目的與要求：哈夫曼樹(shù)及其應(yīng)用，構(gòu)造哈夫曼樹(shù)、哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算；教學(xué)重點(diǎn)，難點(diǎn)：哈夫曼樹(shù)及其應(yīng)用，構(gòu)造哈夫曼樹(shù)、哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算；教學(xué)內(nèi)容：6．6．哈夫曼樹(shù)

2、及其應(yīng)用6.6.1 最優(yōu)二叉樹(shù)（Huffman 樹(shù)）哈夫曼樹(shù)又叫最優(yōu)二叉樹(shù)，它是由 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度WPL 最短的二叉樹(shù)。1、基本術(shù)語(yǔ)?路徑和路徑長(zhǎng)度?樹(shù)的路徑長(zhǎng)度? 結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度? 樹(shù)的帶權(quán)路徑長(zhǎng)度? Huffman 樹(shù)（最優(yōu)二叉樹(shù)）《 數(shù)據(jù)結(jié)構(gòu) 》教案2二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；（3）從 F 中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù)；（4）重復(fù) (2)

3、 和 (3) 兩步，直至 F 中只含一棵樹(shù)為止。例 1: 已知權(quán)值 W={ 6，7，2，3，5，11，12 }，試構(gòu)造一棵哈夫曼樹(shù)，并求加權(quán)路徑長(zhǎng)度6.6.2 哈夫曼編碼1、問(wèn)題的提出通訊中常需要將文字轉(zhuǎn)換成二進(jìn)制字符串電文進(jìn)行傳送。文字 電文，稱為編碼。反之，收到電文后要將電文轉(zhuǎn)換成原來(lái)的文字，電文 文字，稱為譯碼。反之，收到電文后要將電文轉(zhuǎn)換成原來(lái)的文字，電文 文字，稱為譯碼。設(shè)有 n 種字符，每種字

4、符出現(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 樹(shù)，并規(guī)定左分支編碼位 0，右分支編碼為 1，則字符的編碼就是從根到該字符所在的葉結(jié)點(diǎn)的路徑上的分支編號(hào)序列。用構(gòu)造 Huffman 樹(shù)編出來(lái)的碼，稱為 Huffman 編碼。2. 哈夫曼編碼的構(gòu)造方法（1）.構(gòu)造 Huffman 樹(shù)