最優(yōu)二叉樹(shù)哈夫曼樹(shù)-wenkub
2023-07-04 06:37:53 本頁(yè)面
【正文】 量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個(gè)小子樹(shù)合并為一個(gè)較大的子樹(shù)，每次構(gòu)成的新子樹(shù)的根結(jié)點(diǎn)順序放到HuffNode數(shù)組中的前n個(gè)分量的后面。4 第一步 第二步57135731 第三步 第四步16979475413513 哈夫曼樹(shù)的建立過(guò)程 7. 2 哈夫曼樹(shù)的構(gòu)造算法 從上述算法中可以看出，F(xiàn)實(shí)際上是森林，該算法的思想是不斷地進(jìn)行森林F中的二叉樹(shù)的“合并”，最終得到哈夫曼樹(shù)。哈夫曼（Haffman）依據(jù)這一特點(diǎn)于1952年提出了一種方法，這種方法的基本思想是： （1）由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)的集合F＝{T1，T2，…，Tn}； （2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和； （3）在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合F中；（4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。 在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹(shù)。如果二叉樹(shù)中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。假設(shè)有1000個(gè)鐵球，則各類(lèi)鐵球的個(gè)數(shù)分別為：100、200、300、400；：左圖右圖序號(hào)比較式比較次數(shù)序號(hào)比較式比較次數(shù)1a=2010001a10010002a=509002a506003a=1007003a=20300合計(jì)2600合計(jì)1900 兩種判斷二叉樹(shù)比較次數(shù)過(guò)上述分析可知。國(guó)內(nèi)快遞包裹資費(fèi) 單位：元（2004年1月1日起執(zhí)行）運(yùn)距（公里）首重1000克5000克以?xún)?nèi)續(xù)重每500克5001克以上續(xù)重每500克=500=1000 500=1500 1000=2000 1500=2500 2000=3000 2500=4000 3000=5000 4000=6000 50006000 國(guó)家郵政局制定的快遞包裹參考標(biāo)準(zhǔn)，但不同的二叉樹(shù)判定的次數(shù)可能不一樣，執(zhí)行的效率也不同。最優(yōu)二叉樹(shù)——哈夫曼樹(shù)【重點(diǎn)與難點(diǎn)】1． 帶權(quán)二叉樹(shù)與哈夫曼樹(shù)基本概念；2． 構(gòu)造哈夫曼樹(shù)；3． 哈夫曼編碼及其算法實(shí)現(xiàn)。 鐵球分類(lèi)現(xiàn)有一批球磨機(jī)上的鐵球，需要將它分成四類(lèi)：直徑不大于20的屬于第一類(lèi)。為了找出比較次數(shù)最少的判斷框，將涉及到樹(shù)的路徑長(zhǎng)度問(wèn)題。設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記為： n∑k=1 WPL＝ Wk例如，給出4個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù)。由于這種算法是哈夫曼最早提出的，所以將最優(yōu)二叉樹(shù)稱(chēng)為哈夫曼樹(shù)。在構(gòu)造哈夫曼樹(shù)時(shí)，可以設(shè)置一個(gè)結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹(shù)中各結(jié)點(diǎn)的信息，根據(jù)二叉樹(shù)的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有2n－1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n－1，數(shù)組元素的結(jié)構(gòu)形式如下：rchildweightlchildparent其中，weight域保存結(jié)點(diǎn)的權(quán)值，lchild和rchild域分別保存該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)在數(shù)組HuffNode中的序號(hào)，從而建立起結(jié)點(diǎn)之間的關(guān)系。下面給出哈夫曼樹(shù)的構(gòu)造算法。 type HnodeType=record weight: inte
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1