哈夫曼樹教學探討

杜敏　郭珊珊　潘鵬　陶駿

摘要：探討了哈夫曼樹的教學要點及教學方法，以哈夫曼樹的定義和意義為教學內(nèi)容的開端，分步介紹了哈夫曼樹的構造和運用方法，以典型的電文傳輸為例，剖析了哈夫曼樹的要點以及編碼過程的注意點。

關鍵詞：教學設計;哈夫曼樹;教學模式;問題驅(qū)動

中圖分類號：G642? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2020）02-0106-03

Abstract： This paper probes into the teaching points and teaching methods of Huffman tree. Taking the definition and significance of Huffman tree as the beginning of teaching content， it introduces the construction and application methods of Huffman tree step by step. Taking typical message transmission as an example， it analyses the main points of Huffman tree and the points for attention in coding process.

Key words： curriculum design; huffman tree; teaching model; problem driven

《數(shù)據(jù)結構與算法》課程是計算機學院學生所需要學習的一門重要必修課程。課程要求學生會把生活中大量的復雜問題簡單化，對問題進行抽象建模，繼而以特定的數(shù)據(jù)類型和存儲結構把他們存儲到計算機中去，從而可以實現(xiàn)某種操作。數(shù)據(jù)結構的研究范圍主要涉及各種邏輯結構和物理結構，運用算法對數(shù)據(jù)進行有規(guī)則的操作。比如排序和查找，實現(xiàn)這些操作的具體步驟就稱之為算法，算法就是對特定的數(shù)據(jù)類型進行某些操作，從而達到某種目的的過程。

《數(shù)據(jù)結構與算法》中以樹形結構為非線性結構代表展開教學。樹形結構是有層次的嵌套結構，它在計算機科學中具有廣泛的應用，反映了數(shù)據(jù)元素之間的層次結構。本文選擇了樹形結構中的哈夫曼樹，以課件的形式進行教學，能有效開展案例教學，實現(xiàn)學習過程控制的教學策略，強化學習效果。

1 教學目標

教學目標是指在教學活動中教學者所期待的所有學生反饋的學習結果，是課堂教學的出發(fā)點，教學目標始終是教學活動的過程主線。教師以教學目標為中心，制定能夠引導學生學習的教學策略，學生以教師的教學目標為目標，積極展開學習。根據(jù)學生學習結果的反饋，心理學家概括出不同的學習結果，代表之一就是智力技能目標。從以上幾種分類的結果可以看到一點，哈夫曼樹一課中的教學目標主要為智力技能目標。那么哈夫曼樹的教學目標即是學生學完本課件的內(nèi)容之后，能夠根據(jù)給定的條件構造哈夫曼樹，并且能夠?qū)懗銎渥疃痰膸嗦窂介L度。

2 學習者特征

傳播學原理闡釋了有效的訊息傳遞的條件，傳播者必須了解接受者對訊息的態(tài)度、有關的知識基礎和傳播技能。教學活動也是一樣，教學者設計的一切教學活動都是圍繞學生的學習?？梢姡瑢W習者學習特征的分析是很有必要的，有效針對學習者的學習風格和學習能力，制定切合該類學習者學習特點的教學策略，從而有效闡明學習目標，達到教學效果。因此有效的教學設計必定要考慮到學習者的學習特征。學習者學習的一個重要特征就是學習的初始能力，學生學習結果的性質(zhì)極大部分是由于學生對學習認知的準備狀態(tài)所影響的。學習者原本儲備的知識基礎是自身學習新知識的重要內(nèi)部條件，哈夫曼樹面向的學習者在學習數(shù)據(jù)結構與算法這一課程的內(nèi)容以前已經(jīng)學習了C++程序設計語言及計算機導論等前導課程的內(nèi)容，并且在之前就已經(jīng)學習了數(shù)據(jù)結構中的樹的知識。因此學生通過學習此前的教學內(nèi)容以及前導課程的學習已經(jīng)具備了一定的解決問題的能力和計算機程序的編寫能力。

3 教學內(nèi)容

觀察一個例子—判定樹：

判定樹指的是在處理事件的詳細分析中，用樹形邏輯圖對單個功能與活動的一種詳細分析方法。大多數(shù)問題的解決都會用到判定樹，這些判斷結構的設計直接影響著程序的執(zhí)行效率。例如，編制一個將百分制轉(zhuǎn)換成60分以下，70分以下，80分以下，90分以下，90分以上這五個等級輸出的程序，用下列簡單形式可以快速編寫：

if（score < 60）

System.out.print（“bad”）;

else if（score <70）

System.out.print（“pass”）;

else if（score <80）

System.out.print（“general”）;

else if（score <90）

System.out.print（“good”）;

else

System.out.print（“pretty good”）;

若考慮上述程序所耗費的時間，就會發(fā)現(xiàn)該程序的缺陷。60分以下的情況程序只需要判斷一次，而60～70分的情況程序需要判斷兩次，以此類推，若是分數(shù)情況較多那判斷的次數(shù)豈不是更多，況且實際應用中在五個等級上所分布的學生成績是不均勻的。當學生百分制成績的錄入量很大時，上述判定過程需要反復調(diào)用，此時程序的執(zhí)行效率將成為一個嚴重問題。

如表1的表格就是在一次考試中數(shù)學課程的各分數(shù)段的分布情況：

現(xiàn)按照表格條件利用哈夫曼樹來尋找一顆最佳判定樹，即總的比較次數(shù)最少的判定樹。

第一種構造方式：

第二種構造方式：

顯然后者的判定效率要比前者高。

所以稱判定過程最優(yōu)的二叉樹為最優(yōu)二叉樹，即哈夫曼樹。

3.1 概念

路徑：樹中一個結點到達其子孫所經(jīng)過的結點集合。

路徑長度：在樹的一條路徑中，每走過一個結點路徑長度都要加一。

權值：每個樹結點所在的數(shù)值，通常指字符對應的二進制編碼出現(xiàn)的概率。

結點的帶權路徑長度：指的是在一棵樹中，結點到樹根之間的路徑長度與該結點上權的乘積。

3.2 哈夫曼樹的構造

哈夫曼樹被定義為一種帶權路徑長度最短的樹。要使得二叉樹的WPL值最小，那么該二叉樹的根結點以下的葉子結點為所有權值中較大的值，而所有權值中較小的值都會遠離該二叉樹的根結點。哈夫曼善于總結，他根據(jù)這一特點，提出了一種構造最優(yōu)二叉樹的方法——哈夫曼算法：

給定n個數(shù)值為權值，要求構造一棵最優(yōu)二叉樹即哈夫曼樹。給出哈夫曼樹的構造規(guī)則：

（1） 在給定的n個權值中選出兩個最小的值，讓它們構成一棵新的二叉樹，新二叉樹的左右葉子結點的值就是它們的值，新樹的根結點的權值就是這兩個葉子結點權值的和;

（2） 在原來給定的所有n個權值中刪除上一步已用的兩個最小權值，并將新二叉樹的權值加入n-2個權值中去;

（3） 重復上面兩個步驟，當所有權值都出現(xiàn)在這一棵二叉樹上時，這棵樹就是所需要構造的哈夫曼樹。

這里要注意幾點：

（1） 哈夫曼樹不唯一;

（2） 哈夫曼樹的子樹也是哈夫曼樹;

（3） 哈夫曼樹中無度為1的結點;

（4） 有n個葉子結點的哈夫曼樹，其總結點數(shù)為2n-1。

在處理問題時，我們設立的目標不同，解決問題的過程中使用的方法也就有所不同。但是解決方法一定是要符合處理條件的。比如上述的二叉樹，要使得構造的樹帶權路徑長度最小，那么它所涉及的處理方法可能要求達到某種空間資源的最小化，或者時間的最小化，于是哈夫曼樹在理論上便有了應用價值。

3.3 哈夫曼樹在編碼中的應用

用于通信編碼：

在電報通訊中，電文是需要在字符和二進制編碼之間相互轉(zhuǎn)換從而進行傳送的，電文以二進制的0，1序列傳送。在發(fā)送端需要將電文中的字符序列轉(zhuǎn)換成二進制的0，1序列，而在接收端又需要把接收的0，1序列轉(zhuǎn)換成對應的字符序列。

例如給出的這段電文：WRGPWPRGGRPPGPWRGP

電文中使用了W，P，G，R這四種字符，每個字符出現(xiàn)的頻率分別對應3，6，5，4，將它們進行二進制等長編碼，則編碼依次為W：00? P：01R：10? G：11

所發(fā)電文為：

00101101 00011011 111001 0111 01? ?00101101

采用不等長編碼容易產(chǎn)生二義性或者多義性。這里有一個例子，A：010，B：0101，C：001，D：1010字符A的編碼010與字符B的編碼0101的前一部分重合。在這種情況下，0101010，同樣表示了BBA的代碼和AD的代碼，這種情況的編碼就產(chǎn)生了譯碼的二義性。

所以，采用不等長編碼容易出現(xiàn)二義性。為了解決這個問題，可以將字符集里的每個字符賦予葉子結點的含義，這樣就能生成一顆編碼二叉樹，使該字符結點的權值表示的是字符出現(xiàn)頻率的含義，有了這些條件之后便能求出樹的最小帶權路勁長度，其表示的含義就是傳送電文的最短長度。這里就存在以頻率賦予權值所出現(xiàn)的哈夫曼樹的問題。

比如此處存在7個字符{H，I，J，K，L，M，N}，這7個字符的出現(xiàn)頻率為{5，24，7，17，34，5，13}，若將它們存入至文件中去，可使用哈夫曼樹構造不等長編碼進行存儲，并且符合前綴編碼的要求。

H：111? I：01 J：111K：00 L：0M：11 N：11構造樹形如圖3所示：

哈夫曼樹構造完成以后，須從葉子結點出發(fā)走到根部從而求出編碼。

構造過程總結：

（1） 對兩個最小者的選擇為雙親下標為0的結點;

（2） 對選出的兩個最小者，修改雙親下標為新結點的下標;

（3） 新結點的左右孩子修改為所選的兩個新結點的下標;

（4） 新結點的權值為兩個結點權值之和。

最后給出哈夫曼編碼的簡要算法：

//結點的結構體類型

public class HTNode

{public int weight;? //結點的權值

public int parent;? //結點的雙親

public intlchild;? ?//結點左孩子的下標

public intrchild;? //結點右孩子的下標

};

voidCreateHuffmanTree（ListHT，int n）

{

if（n<=1）return;

m=2*n-1;

HT=new HTNode[m+1];

//0單元未使用，此處需要動態(tài)分配m+1個單元，HT[m]為根結點

for（i=1;i<=m;i++）

//將1～m的結點雙親，左右孩子的下標都初始化為0

{

HT[i].parent=0;

HT[I].lchild=0;

HT[i].rchild=0;

//輸入n個葉結點的權值

for（i=1;i<=n;i++）

{

System.out.print（HT[i].weight）;

}}}

4 教學策略

教學設計是一個系統(tǒng)過程。 在哈夫曼樹教學設計中有如下的教學策略。

概念的教學策略。該教學設計中必須講解的概念有：路徑、路徑長度、樹的路徑長度、帶權的路徑長度、樹的帶權的路徑長度、空心二叉樹和哈夫曼樹等。該教學設計中的概念的講解使用如下的組織方式。講解概念所用方法：使用文本直接呈現(xiàn)哈夫曼樹所涉及的知識概念。使用動畫圖表演示概念的簡單實例。介紹完概念后，普及哈夫曼樹在編碼中的實際應用，用以鍛煉學習者的思考能力，進而保持對哈夫曼樹知識的注意。給出相關概念的練習題，類型為填空題以及選擇題。給出進階應用編程題，用以鍛煉學習者的思維能力以及編程能力。

規(guī)則的教學策略。該教學設計的規(guī)則為哈夫曼樹的構造算法。采用的教學方法是規(guī)則—實例的方法。為了使學生能有效地學習哈夫曼樹知識，采用圖形與文本相結合的方式，交錯傳遞哈夫曼樹的知識概念及應用。即先以文本的形式呈現(xiàn)哈夫曼樹的構造算法，接著再以圖形動畫演示用構造算法構造哈夫曼樹及求哈夫曼樹的帶權路徑長度的過程。講解完后提供習題小測驗，類型為填空題以及選擇題。學生回答問題之后，教學者對學生的答案進行檢查，如果學生的答題情況很差即沒有答對所列題目中的百分之八十，下次課程則應繼續(xù)鞏固基礎概念，調(diào)整學習進度從而達到教學效果。

5 總結

完整的教學設計應包含教學目標、學習者特征的分析以及教學內(nèi)容形式的確定。學生是教學活動的關鍵，教學設計應圍繞學生的理解能力來開展。對于哈夫曼樹教學設計來說，它所涉及的思維傳達方式尤其重要。因哈夫曼樹一課中的學習內(nèi)容多且知識點間的關系復雜，所以要將這種抽象的邏輯理念表示成超文本的形式是非常困難的，但是在教學設計中編排圖片、動畫極大優(yōu)化了學習效果。

參考文獻：

[1] 火旺.數(shù)據(jù)結構與算法[M].西安：西安電子科技大學出版社，2005：125-127.

[2] 克抗.計算機輔助教育[M].北京：高等教育出版社，1997.

[3] 齊超.哈夫曼編碼及其應用[J].鄭州市電子信息工程學校學報，2014，12（1）：256.

[4] 太山，郭觀七，李文彬.課堂設問的技巧及其在《數(shù)據(jù)結構》課程教學中的應用[J].湖南理工學院學報：自然科學版，2015（1）：81-83.

[5] 哈夫曼算法在分類優(yōu)化應用中方的缺陷及修正[J]東華大學計算機科學與技術學院學報，2010，9（7）：60-62.

[6] 孟凡榮，賈杰，王興偉.網(wǎng)絡工程專業(yè)創(chuàng)新性實踐課程體系構建與實施[J].計算機教育，2013（14）：104-108.

[7] 逯鵬，張贊.數(shù)據(jù)結構課程教學方法的研究和實踐[J].教育教學論壇，2015（18）：121-123.

[8] 瑩.哈夫曼樹遍歷算法的優(yōu)化[J].安徽電子信息技術學院學報，2009，25（5）：7235.

【通聯(lián)編輯：王力】