吐爾地·托合提，崔青，劉淑嫻

（新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046）

0 引言

哈夫曼樹（Huffman Tree），又被稱為最優(yōu)二叉樹，是一種帶權(quán)路徑長度最小的二叉樹，其應(yīng)用也很廣泛，如基于哈夫曼樹的編碼[1]、壓縮[2-3]、加密[4-5]、數(shù)據(jù)采樣[6]等。在教學(xué)中，一般我們重點講解帶權(quán)路徑長度的概念、哈夫曼樹的性質(zhì)、哈夫曼樹的構(gòu)造，以及哈夫曼編碼[8]。其實，哈夫曼樹也可以用來對于數(shù)據(jù)元素序列進(jìn)行排序。

從哈夫曼樹的性質(zhì)可知，權(quán)重越大的葉子結(jié)點越靠近根結(jié)點，而權(quán)重越小的葉子結(jié)點離根結(jié)點越遠(yuǎn)。因此，將待排序序列中的每一個元素看成一個葉子結(jié)點，將元素關(guān)鍵碼看成其權(quán)重（關(guān)鍵碼為整形情況下），構(gòu)造一棵哈夫曼樹，然后層序遍歷并依次輸出葉子結(jié)點，就能得到基本有序（降序）序列。如果，在哈夫曼樹的構(gòu)造、遍歷和輸出過程中增設(shè)一些約束，那么也完全可以做到對數(shù)據(jù)元素的降序或升序排序。

本文在數(shù)據(jù)結(jié)構(gòu)教學(xué)中，針對內(nèi)部排序提出一個教學(xué)案例，在排序方法中引入哈夫曼樹、二叉樹的遍歷、棧和隊列等綜合內(nèi)容，通過講解一些啟發(fā)思路的知識點，一方面加深了學(xué)生對于哈夫曼樹的性質(zhì)、構(gòu)造方法、二叉樹遍歷算法，以及哈夫曼樹、棧和隊列應(yīng)用的理解和掌握，另一方面引導(dǎo)學(xué)生要認(rèn)識到解決問題有多種方案可選，鼓勵學(xué)生從知識中體會和掌握算法設(shè)計的思維方式和技巧，這有助于使學(xué)生分析問題和解決問題的能力得到提升。

1 基于哈夫曼樹的排序算法思路

在待排序序列中數(shù)據(jù)元素關(guān)鍵碼為整形（int 形）情況下，我們可以將每一個數(shù)據(jù)元素看成一個葉子結(jié)點，將數(shù)據(jù)元素關(guān)鍵碼看成其權(quán)重構(gòu)造一棵哈夫曼樹。設(shè)待排序數(shù)據(jù)元素關(guān)鍵字序列為{5，9，15，30，18，27，10，13}，在構(gòu)造哈夫曼樹的過程中我們給一個約束：將權(quán)重大的結(jié)點作為左孩子，將權(quán)重小的結(jié)點作為右孩子，然后按照哈夫曼樹的構(gòu)造方法就能生成得到如圖1 所示的一棵哈夫曼樹。

我們仔細(xì)觀察圖1 哈夫曼樹中葉子結(jié)點（待排序元素結(jié)點）分布，第一層為根，從第二層開始，發(fā)現(xiàn)處在第i 層上元素關(guān)鍵字均小于第i-1 層元素關(guān)鍵字，而均大于第i+1 層元素關(guān)鍵字，最底層上的元素關(guān)鍵字是最小。再觀察同一個層上的元素關(guān)鍵字大小，從左到右，關(guān)鍵字大小依次變小。因此，我們對此哈夫曼樹進(jìn)行層序遍歷并輸出葉子結(jié)點關(guān)鍵字，就能得到一個關(guān)鍵字有序（降序）序列{30，27，18，15，13，10，9，5}，這樣就可以做到降序排序。如果，需要進(jìn)行升序排序，我們可以借助一個棧來暫存層序遍歷輸出序列，最后依次出棧就能得到升序排序結(jié)果。

圖1 由待排序元素關(guān)鍵字構(gòu)建的哈夫曼樹

2 基于哈夫曼樹的排序算法實現(xiàn)

根據(jù)以上分析，我們可以設(shè)計一套用來排序的哈夫曼樹構(gòu)造算法和排序算法。為了簡單討論，以下假設(shè)關(guān)鍵碼為整形，而且只考慮關(guān)鍵碼，暫不考慮數(shù)據(jù)元素其他數(shù)據(jù)項。

構(gòu)造哈夫曼樹時，常用一個結(jié)構(gòu)數(shù)組（如Huff_Nodes）來存儲哈夫曼樹中每一個結(jié)點的信息。我們從二叉樹的性質(zhì)可知，由n 個葉子結(jié)點構(gòu)建的哈夫曼樹中總共有2n-1 個結(jié)點，所以結(jié)構(gòu)數(shù)組Huff_Nodes 大小可設(shè)置為2n-1，其元素結(jié)構(gòu)可定義如圖2 所示形式。

圖2 結(jié)構(gòu)數(shù)組元素結(jié)構(gòu)形式

其中，key 域是用來保存待排序數(shù)據(jù)元素關(guān)鍵字（傳統(tǒng)算法中的結(jié)點權(quán)值weight），l_child 域和r_child域是分別用來保存該結(jié)點的左孩子和右孩子結(jié)點在數(shù)組中的下標(biāo)（序號），算法中我們通過下標(biāo)在結(jié)點之間建立聯(lián)系。parent 域保存當(dāng)前結(jié)點在哈夫曼樹中的雙親結(jié)點在數(shù)組中的序號，其初始值為-1。

2.1 哈夫曼樹的構(gòu)造算法

開始構(gòu)造哈夫曼樹之前，首先把n 個關(guān)鍵字形成的n 個葉子結(jié)點存放在結(jié)構(gòu)數(shù)組Huff_Nodes 的前n 個分量中，然后根據(jù)哈夫曼樹構(gòu)造基本思想和本文給出的約束條件，不斷將兩個根結(jié)點權(quán)重最小的子樹合并為一個較大的子樹，并把被生成的新子樹的根結(jié)點依次按順序存放到Huff_Nodes 數(shù)組前n 個分量后面。具體實現(xiàn)算法描述如下：

算法初始化Huff_Nodes 數(shù)組并依次向數(shù)組填寫新生成的子樹信息（子樹根結(jié)點關(guān)鍵字、根結(jié)點左右孩子在數(shù)組中的序號），同時，還不斷修改與已有子樹之間的關(guān)聯(lián)信息。當(dāng)算法結(jié)束時，用來存儲圖2 所示哈夫曼樹的結(jié)構(gòu)數(shù)組Huff_Nodes 的最終狀態(tài)如圖3 所示。

圖3 數(shù)組Huff_Nodes的最終狀態(tài)

2.2 基于哈夫曼樹層序遍歷的排序算法

已構(gòu)建好的哈夫曼樹的根結(jié)點在數(shù)組Huff_Nodes的最后一個單元中，我們從根結(jié)點出發(fā)進(jìn)行層序遍歷（從上到下，從左到右），并把那些葉子結(jié)點依次暫存到一個棧中，等遍歷結(jié)束就出棧所有元素，此時的出棧序列就是一個升序排序序列。如果要進(jìn)行降序排序，那就不需要經(jīng)過棧來改變次序，在遍歷中直接輸出葉子結(jié)點即可。升序排序具體實現(xiàn)算法描述如下：

3 結(jié)語

排序是數(shù)據(jù)結(jié)構(gòu)課程最后一章內(nèi)容，一般我們主要講解各種典型內(nèi)部排序算法思路，分析其性能和優(yōu)缺點，然后要求學(xué)生通過運行、調(diào)試排序程序去掌握多種排序算法，但很少有拓展內(nèi)容。本文針對內(nèi)部排序設(shè)計一個教學(xué)案例，將棧、隊列、哈夫曼樹等重要內(nèi)容綜合應(yīng)用到排序方法中。其目的不僅僅是提出一個排序算法，而更重要的是鼓勵學(xué)生敢于創(chuàng)新，引導(dǎo)學(xué)生從知識中體會和掌握算法設(shè)計的思維方式和技巧，從而培養(yǎng)學(xué)生創(chuàng)造性思維能力及解決實際問題的能力。