19哈夫曼樹

哈夫曼樹

定義：給定n個正實數w1至wn，使權WPL(T)達最小值的樹，稱為哈夫曼樹（最優二叉樹）。（其中n表示該樹中葉結點的數目，wk和lk(k=1,2,···,n)分别表示葉結點ik的權值和從樹根到葉結點ik之間的路徑長度。）

注意：哈夫曼樹必是正則二叉樹！

下面還要明白幾個重要的概念：

1. 葉的路徑長度：指從根結點到葉結點的路徑上的邊數。

2. 葉的權重路徑長度：設二叉樹T具有n片葉子，n個正實數w1至wn作為各葉的權，根到第i（1≤i≤n）片葉子的路徑長度為li，那麼，Wi*li稱為該葉的權重路徑長度。

3. 二叉樹T的權：n片葉子權重路徑長度之和稱為二叉樹T的權WPL(T)。

 計算公式：

此時，要注意, 權重路徑長度為最小的二叉樹不是唯一。在建構哈夫曼樹時，相同的數值，可能會出現不同的哈弗曼樹，但是都是最小路徑。

哈夫曼算法的描述：自底向上，逐漸合并。

具體步驟:

步驟1）構造n棵單葉結點的二叉樹，構成初始森林。将權w1~wn依次賦給各葉。

步驟2）按下述步驟，反複将森林中的兩棵樹合并成一棵樹，直到森林中隻有一棵樹，這棵樹就是哈夫曼樹。

①在森林中找出根的權最小的兩棵樹：T1和T2。

②将T1，T2合并成一棵樹T，使T1，T2分别作為T的左右子樹，且使T之根的權等于T1，T2之根的權之和。

③把合并樹T加入森林。

示例：

構造哈夫曼樹的源代碼：
（1）有關定義
#include  <stdio.h>
#define  n  XX    //XX為具體葉子數目
#define  MAX  YYY    //YYY代表無窮大值，用作監督元
#define  NULL  0        //空鍊域值
typedef  struct  Hfnode    //結點類型
{  int  data;            //權值域，假定為int類型
   struct  Hfnode  *Lson, *Rson, *next;  //兒子鍊域和森林鍊域
}  Hfnode,*Hfptr;

結點類型定義：
typedef  struct  Hfnode   //  結點類型
 {  
　　int  data;  //權值域，假定為int類型
   struct  Hfnode  *Lson, *Rson, *next; 
 } Hfnode,*Hfptr;
主要函數：
void  Hfmain( )  
 { 
　　 Hfptr Hroot,head; 
    head=inition( );  //調用初始化函數
    Hroot=creatHftree( );//調用造樹函數
   ……  //其它處理
  }
初始化函數：
Hfptr  inition( )
  { 
int i; 
Hfptr h,p;
   h=p=new Hfnode;
   h->data=MAX;   //構造監督元結點 
   for(i=1;i<=n;i++)
     {  
　　　　p->next=new Hfnode; 
        p=p->next;  //p始終指向目前尾結點 
        p->Lson=p->Rson=NULL; //做葉結點
        scanf("%d",&p->data); //讀入葉之權wi
      }
.   p->next=h;  //構成循環鍊
    return  h;
  }
構造哈夫曼樹的函數：
Hfptr  creatHftree(Hfptr  head) 
  {
　　int i;
　　Hfptr  p,q,r,t1,t2;  
    for(i=1;i<n;i++) //進行n-1遍合并
　　{
　　　　r=new Hfnode; // 申請新根
      t1=head->next; // t1，t2指向兩棵權最小的樹根
      t2=t1->next;   
      r->data=t1->data+ t2->data; //權值相加
      r->Lson=t1; // t1，t2作新根r的左右兒子
      r->Rson=t2;
      head->next=t2->next;  //森林中删去t1，t2
      q=head; //準備進行有序插入
      p=head->next; //p是搜尋指針，q是p的前趨
      while(1) //循環的為r尋找有序位置 
          {
　　　　　　　　if(p->data<r->data)
       　　　 { 
　　　　　　　　　　q=p;  
　　　　　　　　　　p=p->next; 
　　　　　　　　} //尚未找到時，繼續循環
    　　　　    else
     　　　　   { 
　　　　　　　　　　 r->next=p; //找到後，插入r
     　　　　      q->next=r;
      　　　　     break;
      　　　　   }   
　　　　　　}
    } //終止語句1 的for循環
 　　  p=head->next; 
 　　 delete  head;  //删去監督元
 　　  return  (p);  //傳回Huffmam樹之根
   }  //構造完畢