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