使用C語言詳解霍夫曼樹數據結構

2020-01-26 14:58:29

字體：大中小

來源：轉載

供稿：網友

1、基本概念

a、路徑和路徑長度

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

從 k1 到 kj 所經過的分支數稱為這兩點之間的路徑長度，它等于路徑上的結點數減1.

b、結點的權和帶權路徑長度

在許多應用中，常常將樹中的結點賦予一個有著某種意義的實數，我們稱此實數為該結點的權，(如下面一個樹中的藍色數字表示結點的權)

結點的帶權路徑長度規定為從樹根結點到該結點之間的路徑長度與該結點上權的乘積。

c、樹的帶權路徑長度

樹的帶權路徑長度定義為樹中所有葉子結點的帶權路徑長度之和，公式為：

2015816155922684.jpg (314×123)

其中，n表示葉子結點的數目，wi 和 li 分別表示葉子結點 ki 的權值和樹根結點到 ki 之間的路徑長度。

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

d、哈夫曼樹

哈夫曼樹又稱最優二叉樹。它是 n 個帶權葉子結點構成的所有二叉樹中，帶權路徑長度 WPL 最小的二叉樹。

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

2015816155310262.png (672×652)

2、構造哈夫曼樹

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

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

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

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

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

如：對下圖中的六個帶權葉子結點來構造一棵哈夫曼樹，步驟如下：

2015816155522204.png (1140×1318)

注意：為了使得到的哈夫曼樹的結構盡量唯一，通常規定生成的哈夫曼樹中每個結點的左子樹根結點的權小于等于右子樹根結點的權。

具體算法如下：

 //2、根據數組 a 中 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指針數組，使每個指針元素指向a數組中對應的元素結點     {       b[i] = malloc(sizeof(struct BTreeNode));       b[i]->data = a[i];       b[i]->left = b[i]->right = NULL;     }     for (i = 1; i < n; i++)//進行 n-1 次循環建立哈夫曼樹     {       //k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標       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++)//從當前森林中求出最小權值樹和次最小       {         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;         }       }       //由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點       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指針數組中k1位置       b[k2] = NULL;//k2位置為空     }     free(b); //刪除動態建立的數組b     return q; //返回整個哈夫曼樹的樹根指針   }

3、哈夫曼編碼

在電報通信中，電文是以二進制的0、1序列傳送的，每個字符對應一個二進制編碼，為了縮短電文的總長度，采用不等長編碼方式，構造哈夫曼樹，

將每個字符的出現頻率作為字符結點的權值賦予葉子結點，每個分支結點的左右分支分別用0和1編碼，從樹根結點到每個葉子結點的路徑上

所經分支的0、1編碼序列等于該葉子結點的二進制編碼。如上文所示的哈夫曼編碼如下：

2015816155607502.png (672×652)

a 的編碼為：00

b 的編碼為：01

c 的編碼為：100

d 的編碼為：1010

e 的編碼為：1011

f 的編碼為：11

4、哈夫曼樹的操作運算

以上文的哈夫曼樹作為具體實例，用詳細的程序展示哈夫曼樹的操作運算

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

運行結果：

2015816155632294.png (555×288)

下面來看一道ACM題目

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

ac代碼

鏈表構建哈夫曼樹（插入排序）

 #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);  }

上一篇：貪心算法的C語言實現與運用詳解

下一篇：使用C語言求N的階乘的方法