哈夫曼樹(shù)在排序算法中的案例教學(xué)研究

吐?tīng)柕亍ね泻咸?，崔青，劉淑?/p>

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

0 引言

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

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

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

1 基于哈夫曼樹(shù)的排序算法思路

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

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

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

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

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

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

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

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

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

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

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

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

2.2 基于哈夫曼樹(shù)層序遍歷的排序算法

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

3 結(jié)語(yǔ)

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