最優(yōu)二叉樹哈夫曼樹-文庫吧
2025-06-04 06:37 本頁面
【正文】 的二叉樹由此可見，由相同權(quán)值的一組葉子結(jié)點所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點越遠(yuǎn)離根結(jié)點。哈夫曼（Haffman）依據(jù)這一特點于1952年提出了一種方法，這種方法的基本思想是： （1）由給定的n個權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個葉結(jié)點的二叉樹，從而得到一個二叉樹的集合F＝{T1，T2，…，Tn}； （2）在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和； （3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；（4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。由于這種算法是哈夫曼最早提出的，所以將最優(yōu)二叉樹稱為哈夫曼樹。＝{1，3，5，7}的哈夫曼樹的構(gòu)造過程。可以計算出其帶權(quán)路徑長度為29，由此可見，對于同一組給定葉結(jié)點所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但帶權(quán)路徑長度值是相同的，一定是最小的。4 第一步 第二步57135731 第三步 第四步16979475413513 哈夫曼樹的建立過程 7. 2 哈夫曼樹的構(gòu)造算法 從上述算法中可以看出，F(xiàn)實際上是森林，該算法的思想是不斷地進(jìn)行森林F中的二叉樹的“合并”，最終得到哈夫曼樹。在構(gòu)造哈夫曼樹時，可以設(shè)置一個結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹共有2n－1個結(jié)點，所以數(shù)組HuffNode的大小設(shè)置為2n－1，數(shù)組元素的結(jié)構(gòu)形式如下：rchildweightlchildparent其中，weight域保存結(jié)點的權(quán)值，lchild和rchild域分別保存該結(jié)點的左、右孩子結(jié)點在數(shù)組HuffNode中的序號，從而建立起結(jié)點之間的關(guān)系。為了判定一個結(jié)點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時parent的值為－1，當(dāng)結(jié)點加入到樹中時，該結(jié)點parent的值為其雙親結(jié)點在數(shù)組HuffNode中的序號，就不會是－1了。構(gòu)造哈夫曼樹時，首先將由n個字符形成的n個葉結(jié)點存放到數(shù)組HuffNode的前n個分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構(gòu)成的新子樹的根結(jié)點順序放到HuffNode數(shù)組中的前n個分量的后面。下面給出哈夫曼樹的構(gòu)造算法。 const maxvalue= 10000。 {定義最大權(quán)值} maxleat=30。 {定義哈夫曼樹中葉子結(jié)點個數(shù)} maxnode=maxleaf*21。 type HnodeType=record weight: integer。 parent: integer。 lchild: integer。 rchild: integer。 end。 HuffArr:array[0..maxnode] of HnodeType。var ……procedure CreatHaffmanTree(var HuffNode: HuffArr)。 {哈夫曼樹的構(gòu)造算法}var i,j,m1,m2,x1,x2,n: integer。begin readln(n)。 {輸入葉子結(jié)點個數(shù)} for i:=0 to 2*n1 do {數(shù)組HuffNode[ ]初始化} begin HuffNode
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1