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

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

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

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

4、符出現(xiàn)的次數(shù)為 Wi ,其編碼長度為 Li ( i=1,2,…n)，則整個(gè)電文總長度為∑ Wi Li ，要得到最短的電文，即使得∑ Wi Li 最小。也就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵 Huffman 樹，并規(guī)定左分支編碼位 0，右分支編碼為 1，則字符的編碼就是從根到該字符所在的葉結(jié)點(diǎn)的路徑上的分支編號序列。用構(gòu)造 Huffman 樹編出來的碼，稱為 Huffman 編碼。2. 哈夫曼編碼的構(gòu)造方法（1）.構(gòu)造 Huffman 樹