哈夫曼樹及其應用教案

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

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

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

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