使用C語言詳解霍夫曼樹數(shù)據(jù)結(jié)構(gòu)

更新時(shí)間：2015年08月16日 15:59:20 作者：yaoowei2012

這篇文章主要介紹了使用C語言詳解霍夫曼樹數(shù)據(jù)結(jié)構(gòu),包括一道AMC相關(guān)的例題演示需要的朋友可以參考下

1、基本概念

a、路徑和路徑長度

若在一棵樹中存在著一個(gè)結(jié)點(diǎn)序列 k1，k2，……，kj，使得 ki是ki+1 的雙親（1<=i<j），則稱此結(jié)點(diǎn)序列是從 k1 到 kj 的路徑。

從 k1 到 kj 所經(jīng)過的分支數(shù)稱為這兩點(diǎn)之間的路徑長度，它等于路徑上的結(jié)點(diǎn)數(shù)減1.

b、結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度

在許多應(yīng)用中，常常將樹中的結(jié)點(diǎn)賦予一個(gè)有著某種意義的實(shí)數(shù)，我們稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)，(如下面一個(gè)樹中的藍(lán)色數(shù)字表示結(jié)點(diǎn)的權(quán))

結(jié)點(diǎn)的帶權(quán)路徑長度規(guī)定為從樹根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。

c、樹的帶權(quán)路徑長度

樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，公式為：

2015816155922684.jpg (314×123)

其中，n表示葉子結(jié)點(diǎn)的數(shù)目，wi 和 li 分別表示葉子結(jié)點(diǎn) ki 的權(quán)值和樹根結(jié)點(diǎn)到 ki 之間的路徑長度。

如下圖中樹的帶權(quán)路徑長度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122

d、哈夫曼樹

哈夫曼樹又稱最優(yōu)二叉樹。它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中，帶權(quán)路徑長度 WPL 最小的二叉樹。

如下圖為一哈夫曼樹示意圖。

2015816155310262.png (672×652)

2、構(gòu)造哈夫曼樹

假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：

(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))；

(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；

(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

如：對下圖中的六個(gè)帶權(quán)葉子結(jié)點(diǎn)來構(gòu)造一棵哈夫曼樹，步驟如下：

2015816155522204.png (1140×1318)

注意：為了使得到的哈夫曼樹的結(jié)構(gòu)盡量唯一，通常規(guī)定生成的哈夫曼樹中每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)。

具體算法如下：

 //2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹，返回樹根指針 
  struct BTreeNode* CreateHuffman(ElemType a[], int n) 
  { 
    int i, j; 
    struct BTreeNode **b, *q; 
    b = malloc(n*sizeof(struct BTreeNode)); 
    for (i = 0; i < n; i++) //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對應(yīng)的元素結(jié)點(diǎn) 
    { 
      b[i] = malloc(sizeof(struct BTreeNode)); 
      b[i]->data = a[i]; 
      b[i]->left = b[i]->right = NULL; 
    } 
    for (i = 1; i < n; i++)//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹 
    { 
      //k1表示森林中具有最小權(quán)值的樹根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo) 
      int k1 = -1, k2; 
      for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹，k2指向第二棵 
      { 
        if (b[j] != NULL && k1 == -1) 
        { 
          k1 = j; 
          continue; 
        } 
        if (b[j] != NULL) 
        { 
          k2 = j; 
          break; 
        } 
      } 
      for (j = k2; j < n; j++)//從當(dāng)前森林中求出最小權(quán)值樹和次最小 
      { 
        if (b[j] != NULL) 
        { 
          if (b[j]->data < b[k1]->data) 
          { 
            k2 = k1; 
            k1 = j; 
          } 
          else if (b[j]->data < b[k2]->data) 
            k2 = j; 
        } 
      } 
      //由最小權(quán)值樹和次最小權(quán)值樹建立一棵新樹，q指向樹根結(jié)點(diǎn) 
      q = malloc(sizeof(struct BTreeNode)); 
      q->data = b[k1]->data + b[k2]->data; 
      q->left = b[k1]; 
      q->right = b[k2]; 
   
      b[k1] = q;//將指向新樹的指針賦給b指針數(shù)組中k1位置 
      b[k2] = NULL;//k2位置為空 
    } 
    free(b); //刪除動(dòng)態(tài)建立的數(shù)組b 
    return q; //返回整個(gè)哈夫曼樹的樹根指針 
  }

3、哈夫曼編碼

在電報(bào)通信中，電文是以二進(jìn)制的0、1序列傳送的，每個(gè)字符對應(yīng)一個(gè)二進(jìn)制編碼，為了縮短電文的總長度，采用不等長編碼方式，構(gòu)造哈夫曼樹，

將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予葉子結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)的左右分支分別用0和1編碼，從樹根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑上

所經(jīng)分支的0、1編碼序列等于該葉子結(jié)點(diǎn)的二進(jìn)制編碼。如上文所示的哈夫曼編碼如下：

2015816155607502.png (672×652)

a 的編碼為：00

b 的編碼為：01

c 的編碼為：100

d 的編碼為：1010

e 的編碼為：1011

f 的編碼為：11

4、哈夫曼樹的操作運(yùn)算

以上文的哈夫曼樹作為具體實(shí)例，用詳細(xì)的程序展示哈夫曼樹的操作運(yùn)算

 #include<stdio.h> 
 #include<stdlib.h> 
 typedef int ElemType; 
 struct BTreeNode 
 { 
  ElemType data; 
  struct BTreeNode* left; 
  struct BTreeNode* right; 
 }; 
  
 //1、輸出二叉樹，可在前序遍歷的基礎(chǔ)上修改。采用廣義表格式，元素類型為int 
 void PrintBTree_int(struct BTreeNode* BT) 
 { 
  if (BT != NULL) 
  { 
   printf("%d", BT->data); //輸出根結(jié)點(diǎn)的值 
   if (BT->left != NULL || BT->right != NULL) 
   { 
    printf("("); 
    PrintBTree_int(BT->left); //輸出左子樹 
    if (BT->right != NULL) 
     printf(","); 
    PrintBTree_int(BT->right); //輸出右子樹 
    printf(")"); 
   } 
  } 
 } 
  
 //2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹，返回樹根指針 
 struct BTreeNode* CreateHuffman(ElemType a[], int n) 
 { 
  int i, j; 
  struct BTreeNode **b, *q; 
  b = malloc(n*sizeof(struct BTreeNode)); 
  for (i = 0; i < n; i++) //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對應(yīng)的元素結(jié)點(diǎn) 
  { 
   b[i] = malloc(sizeof(struct BTreeNode)); 
   b[i]->data = a[i]; 
   b[i]->left = b[i]->right = NULL; 
  } 
  for (i = 1; i < n; i++)//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹 
  { 
   //k1表示森林中具有最小權(quán)值的樹根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo) 
   int k1 = -1, k2; 
   for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹，k2指向第二棵 
   { 
    if (b[j] != NULL && k1 == -1) 
    { 
     k1 = j; 
     continue; 
    } 
    if (b[j] != NULL) 
    { 
     k2 = j; 
     break; 
    } 
   } 
   for (j = k2; j < n; j++)//從當(dāng)前森林中求出最小權(quán)值樹和次最小 
   { 
    if (b[j] != NULL) 
    { 
     if (b[j]->data < b[k1]->data) 
     { 
      k2 = k1; 
      k1 = j; 
     } 
     else if (b[j]->data < b[k2]->data) 
      k2 = j; 
    } 
   } 
   //由最小權(quán)值樹和次最小權(quán)值樹建立一棵新樹，q指向樹根結(jié)點(diǎn) 
   q = malloc(sizeof(struct BTreeNode)); 
   q->data = b[k1]->data + b[k2]->data; 
   q->left = b[k1]; 
   q->right = b[k2]; 
  
   b[k1] = q;//將指向新樹的指針賦給b指針數(shù)組中k1位置 
   b[k2] = NULL;//k2位置為空 
  } 
  free(b); //刪除動(dòng)態(tài)建立的數(shù)組b 
  return q; //返回整個(gè)哈夫曼樹的樹根指針 
 } 
  
 //3、求哈夫曼樹的帶權(quán)路徑長度 
 ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始為0 
 { 
  if (FBT == NULL) //空樹返回0 
   return 0; 
  else 
  { 
   if (FBT->left == NULL && FBT->right == NULL)//訪問到葉子結(jié)點(diǎn) 
    return FBT->data * len; 
   else //訪問到非葉子結(jié)點(diǎn)，進(jìn)行遞歸調(diào)用，返回左右子樹的帶權(quán)路徑長度之和，len遞增 
    return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1); 
  } 
 } 
  
 //4、哈夫曼編碼（可以根據(jù)哈夫曼樹帶權(quán)路徑長度的算法基礎(chǔ)上進(jìn)行修改） 
 void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值為0 
 { 
  static int a[10];//定義靜態(tài)數(shù)組a，保存每個(gè)葉子的編碼，數(shù)組長度至少是樹深度減一 
  if (FBT != NULL)//訪問到葉子結(jié)點(diǎn)時(shí)輸出其保存在數(shù)組a中的0和1序列編碼 
  { 
   if (FBT->left == NULL && FBT->right == NULL) 
   { 
    int i; 
    printf("結(jié)點(diǎn)權(quán)值為%d的編碼：", FBT->data); 
    for (i = 0; i < len; i++) 
     printf("%d", a[i]); 
    printf("\n"); 
   } 
   else//訪問到非葉子結(jié)點(diǎn)時(shí)分別向左右子樹遞歸調(diào)用，并把分支上的0、1編碼保存到數(shù)組a 
   { //的對應(yīng)元素中，向下深入一層時(shí)len值增1 
    a[len] = 0; 
    HuffManCoding(FBT->left, len + 1); 
    a[len] = 1; 
    HuffManCoding(FBT->right, len + 1); 
   } 
  } 
 } 
  
 //主函數(shù) 
 void main() 
 { 
  int n, i; 
  ElemType* a; 
  struct BTreeNode* fbt; 
  printf("從鍵盤輸入待構(gòu)造的哈夫曼樹中帶權(quán)葉子結(jié)點(diǎn)數(shù)n："); 
  while(1) 
  { 
   scanf("%d", &n); 
   if (n > 1) 
    break; 
   else 
    printf("重輸n值："); 
  } 
  a = malloc(n*sizeof(ElemType)); 
  printf("從鍵盤輸入%d個(gè)整數(shù)作為權(quán)值：", n); 
  for (i = 0; i < n; i++) 
   scanf(" %d", &a[i]); 
  fbt = CreateHuffman(a, n); 
  printf("廣義表形式的哈夫曼樹："); 
  PrintBTree_int(fbt); 
  printf("\n"); 
  printf("哈夫曼樹的帶權(quán)路徑長度："); 
  printf("%d\n", WeightPathLength(fbt, 0)); 
  printf("樹中每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼：\n"); 
  HuffManCoding(fbt, 0); 
 }

運(yùn)行結(jié)果：

2015816155632294.png (555×288)

下面來看一道ACM題目

    題目描述：
    哈夫曼樹，第一行輸入一個(gè)數(shù)n，表示葉結(jié)點(diǎn)的個(gè)數(shù)。需要用這些葉結(jié)點(diǎn)生成哈夫曼樹，根據(jù)哈夫曼樹的概念，這些結(jié)點(diǎn)有權(quán)值，即weight，題目需要輸出所有結(jié)點(diǎn)的值與權(quán)值的乘積之和。
    輸入：
    輸入有多組數(shù)據(jù)。
    每組第一行輸入一個(gè)數(shù)n，接著輸入n個(gè)葉節(jié)點(diǎn)（葉節(jié)點(diǎn)權(quán)值不超過100，2<=n<=1000）。
    輸出：
    輸出權(quán)值。
    樣例輸入：
    5
    1 2 2 5 9
    樣例輸出：
    37

ac代碼

鏈表構(gòu)建哈夫曼樹（插入排序）

 #include <stdio.h> 
 #include <stdlib.h> 
 #define max 1001 
  
 struct htree 
 { 
  int weight; 
  struct htree *lchild; 
  struct htree *rchild; 
  struct htree *next; 
 }; 
  
 void addNode(struct htree *, struct htree *); 
 struct htree* createHfmtree(int *, int); 
 int getWpl(struct htree *, int); 
  
 int main() 
 { 
  int w[max]; 
  int i, n, wpl; 
  struct htree *ht; 
  
  while(scanf("%d", &n) != EOF) 
  { 
   for(i = 0; i < n; i ++) 
   { 
    scanf("%d", &w[i]); 
   } 
    
   ht = createHfmtree(w, n); 
   wpl = getWpl(ht, 0); 
   printf("%d\n", wpl); 
  } 
  return 0; 
 } 
  
 struct htree* createHfmtree(int *w, int n) 
 { 
  int i; 
  struct htree *head, *pl, *pr, *proot; 
  head = (struct htree *)malloc(sizeof(struct htree)); 
  head->next = NULL; 
  
  for(i = 0; i < n; i ++) 
  { 
   struct htree *pnode = malloc(sizeof(struct htree)); 
   pnode->weight = *(w + i); 
   pnode->lchild = pnode->rchild = pnode->next = NULL; 
   addNode(head, pnode); 
  } 
  
  while(head->next) 
  { 
   if(head->next->next == NULL) 
    break; 
   pl = head->next; 
   pr = pl->next; 
   head->next = pr->next; 
   proot = (struct htree *)malloc(sizeof(struct htree)); 
   proot->weight = pl->weight + pr->weight; 
   proot->lchild = pl; 
   proot->rchild = pr; 
   addNode(head, proot); 
  } 
  return head->next; 
 } 
  
 void addNode(struct htree *head, struct htree *pnode) 
 { 
  struct htree *t = head; 
  
  while(t->next && t->next->weight < pnode->weight) 
   t = t->next; 
  pnode->next = t->next; 
  t->next = pnode; 
 } 
  
 int getWpl(struct htree *ht, int level) 
 { 
  if(ht == NULL) 
   return 0; 
  if(!ht->lchild && !ht->rchild) 
  { 
   return ht->weight * level; 
  } 
  
  return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1); 
 }

您可能感興趣的文章: