最優二叉樹算法的構造算法

從上述算法中可以看出，F實際上是森林，該算法的思想是不斷地進行森林F中的二叉樹的“合並”，最終得到哈夫曼樹。

在構造哈夫曼樹時，可以設置壹個結構數組HuffNode保存哈夫曼樹中各結點的信息，根據二叉樹的性質可知，具有n個葉子結點的哈夫曼樹***有2n－1個結點，所以數組HuffNode的大小設置為2n－1，數組元素的結構形式如下： weight lchild rchild parent 其中，weight域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數組HuffNode中的序號，從而建立起結點之間的關系。為了判定壹個結點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時parent的值為－1，當結點加入到樹中時，該結點parent的值為其雙親結點在數組HuffNode中的序號，就不會是－1了。

構造哈夫曼樹時，首先將由n個字符形成的n個葉結點存放到數組HuffNode的前n個分量中，然後根據前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合並為壹個較大的子樹，每次構成的新子樹的根結點順序放到HuffNode數組中的前n個分量的後面。

下面給出哈夫曼樹的構造算法。

const maxvalue= 10000; {定義最大權值}

maxleat=30; {定義哈夫曼樹中葉子結點個數}

maxnode=maxleaf*2-1;

type HnodeType=record

weight: integer;

parent: integer;

lchild: integer;

rchild: integer;

end;

HuffArr:array[0..maxnode] of HnodeType;

var ……

procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造算法}

var i,j,m1,m2,x1,x2,n: integer;

begin

readln(n); {輸入葉子結點個數}

for i:=0 to 2*n-1 do {數組HuffNode[ ]初始化}

begin

HuffNode[i].weight=0;

HuffNode[i].parent=-1;

HuffNode[i].lchild=-1;

HuffNode[i].rchild=-1;

end;

for i:=0 to n-1 do read(HuffNode[i].weight); {輸入n個葉子結點的權值}

for i:=0 to n-1 do {構造哈夫曼樹}

begin

m1:=MAXVALUE; m2:=MAXVALUE;

x1:=0; x2:=0;

for j:=0 to n i-1 do

if (HuffNode[j].weight

begin m2:=m1; x2:=x1;

m1:=HuffNode[j].weight; x1:=j;

end

else if (HuffNode[j].weight

begin m2:=HuffNode[j].weight; x2:=j; end;

{將找出的兩棵子樹合並為壹棵子樹}

HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;

HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;

HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;

end;

end;