从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F中的二叉树的"合并"，最终得到哈夫曼树。

在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，数组元素的结构形式如下:

其中，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.weight=0;

HuffNode.parent=-1;

HuffNode.lchild=-1;

HuffNode.rchild=-1;

end;

for i:=0 to n-1 do read(HuffNode.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;