普通树的遍历

二、最优二叉树的构造方法
   假定给出n个结点ki(i=1‥n)，其权值分别为Wi(i=1‥n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：
    首先，将给定的n个结点构成n棵二叉树的集合F={T1，T2，……，Tn}。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步
    ⑴ 在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；
    ⑵ 在F中删除这两棵二叉树，同时将新得到的二叉树加入F 重复⑴、⑵，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。

三、最优二叉树的数据类型定义
    在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。
    Const n=叶结点数的上限；
          m=2*n-1；{最优二叉树的结点数}
    Type
         node=record{结点类型}
           data：<数据类型>；{权值}
           prt，lch，rch,lth：0‥m；{父指针、左、右指针和路径长度}
         end；
         wtype=array[1‥n] of <数据类型> ；{n个叶结点权值的类型}
         treetype=array[1‥m] of node；{最优二叉树的数组类型}
    Var tree：treetype；
                {其中tree [1‥n]为叶结点，tree [n+1‥2n-1]为中间结点，根为tree [2n-1]}

四、构造最优二叉树的算法

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。

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

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