第八节 最优二叉树(哈夫曼树)
一、概念
    在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使
（Wk—第k个叶结点的权值；Pk—第k个叶结点的带权路径长度）达到最小。
二、最优二叉树的构造方法
   假定给出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。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。