第八节 最优二叉树(哈夫曼树)

procedure hufm(w：wtype；var tree：treetype；var bt：integer)；
  function min (h：integer)：integer；{在前h个结点中选择父指针为0且权值最小的结点min}     begin
       ml:=∞；
       for p:=1 to h do
         if (tree[p]．prt=0)and(m1>tree[p]．data)
             then begin i:=p；m1:=tree[p]．data； end；
       min:=i；
    end；{min}
  begin
    fillchar (tree，sizeof(tree)，0)；{构造初始集合F}
    for i:=1 to n do
      read(tree[i]．Data)；
    for k:=n+1 to m do {构造最优二叉树}
      begin {计算k为根的左儿子和右儿子}
        i:=min(k-1)；
        tree[i]．prt:=k；
        tree[k]．lch:=i；
        j:=min(k-1)；
        tree[j]．prt:=k；
        tree[k]．rch:=j；
        tree[k]．data:=tree[i]．data+tree[j]．data；
      end；{for}
    bt:=m；
   end；{hufm}
{计算每一个叶结点的路径长度}
procedure ht(t:integer);{通过前序遍历计算每一个叶结点的路径长度}
  begin
    if t=m{若结点t为根，则路径长度为0；否则结点t的路径长度为其父结点的路径长度+1}
      then tree[t].lth:=0
      else tree[t].lth:=tree[tree[t].prt].lth+1；
    if tree[t].lch<>0
      then begin ht(tree[t].lch)；ht(tree[t].rch)；end；{then}{分别递归左右子树}
   end；{ht}
　

由此可见，叶结点t（1≤t≤5）的带权路径长度即为tree[t].lth*tree[t].data。