程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 哈夫曼樹的代碼實現

哈夫曼樹的代碼實現

編輯：C++入門知識

定義
哈夫曼樹，又稱最優樹，是一類帶權路徑長度最短的樹。

樹的帶權路徑長度，是樹中所有葉子節點的帶權路徑長度之和。通常記做WPL=W1*L1+W2*L2+...+Wn*Ln。

例如：

節點ABCDE的權值分別為：1，2，4，5，6。對於圖1，WPL=4*3+2*3+1*3+5*3+6*1=42。對於圖2，WPL=1*3+2*3+4*2+5*2+6*2=39。以上節點還可以列出其他的樹，並計算WPL，可以看出，圖2的WPL值是最小的，這顆樹即稱為最優二叉樹或哈夫曼樹。

如何建立二叉樹呢？
1、將所有節點看成獨立的樹，且左右子樹都為空，沒有父節點；

2、挑選兩棵根節點權值最小的沒有父節點的樹，生成一個節點作為它們的父節點，父節點的權值等於他們的權值之和；

3、重復第2步，直到最後變成一棵樹。

比如以上ABCDE節點，首先選擇A和B形成的父節點（且記為A‘）權值為3，接下來從權值為3，4，5，6中選取，當然就是選3，4，也即A‘和C節點，形成父節點（且記為C’）權值為7，接下來從權值5，6，7中選取最小的兩個，當然是5，6.也即是D和E，形成父節點（且記為D‘）的權值為11，最後將D’和C‘形成父節點即為最後的根節點。哈夫曼樹就建成了。

如何構建哈夫曼編碼？
從葉節點往根掃描，若為左子樹則標記為0，為右子樹則標記為1。如圖2，A的編碼即為：000，B的編碼100，等等。

具體代碼實現如下：

[cpp]
//huffmanCoding.c
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#define N 6

typedef struct huffNode
{
    unsigned int weight;   //權重
    unsigned int lchild,rchild,parent; //左右子節點和父節點
}HTNode,*HuffTree;
typedef char **HuffCode;

//找出數組中無父節點且權值最小的兩個節點下標,分別用s1和s2保存
void select(const HuffTree &HT,int n,int &s1,int &s2);
//HT:哈夫曼樹，HC:哈夫曼編碼，w:構造哈夫曼樹節點的權值，n:構造哈夫曼樹節點的個數
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n);

int main()
{
    int i;
    char key[N] = {'0','A','B','C','D','E'};//第0個元素保留不用
    int w[N] = {0,1,2,4,5,6}; //第0個元素保留不用
    HuffTree HT;
    HuffCode HC;
    HuffmanCode(HT,HC,w,N - 1);
    for ( i = 1; i < N; i++ )
    printf("%c:%s\n",key[i],HC[i]);

    printf("\n");
    return 0;
}

//找出數組中權值最小的兩個節點下標,分別用s1和s2保存
void select(const HuffTree &HT,int n,int &s1,int &s2)
{
    int i;
    s1 = s2 = 0;
    int min1 = INT_MAX;//最小值，INT_MAX在<limits.h>中定義的
    int min2 = INT_MAX;//次小值

    for ( i = 1; i <= n; ++i )
    {
    if ( HT[i].parent == 0 )
    {//篩選沒有父節點的最小和次小權值下標
        if ( HT[i].weight < min1 )
        {//如果比最小值小
        min2 = min1;
        s2 = s1;
        min1 = HT[i].weight;
        s1 = i;
        }
        else if ( (HT[i].weight >= min1) && (HT[i].weight < min2) )
        {//如果大於等於最小值，且小於次小值
        min2 = HT[i].weight;
        s2 = i;
        }
        else
        {//如果大於次小值，則什麼都不做
        ;
        }
    }
    }
}

//HT:哈夫曼樹，HC:哈夫曼編碼，w:構造哈夫曼樹節點的權值，n:構造哈夫曼樹節點的個數
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n)
{
    int s1;
    int s2;
    int m = 2 * n - 1;       //容易知道n個節點構造的哈夫曼樹是2n-1個節點
    int i,c,f,j;
    char *code; //暫存編碼的
    HT = (HuffTree)malloc((m+1)*sizeof(HTNode)); //0單元未使用


    for ( i = 1; i <= n; i++ )
        HT[i] = {w[i],0,0,0};//初始化前n個節點(構造哈夫曼樹的原始節點)

    for ( i = n + 1; i <= m; i++ )
    HT[i] = {0,0,0,0}; //初始化後n-1個節點

    //構建哈夫曼樹
    for ( i = n + 1; i <= m; i++)
    {
    select(HT,i-1,s1,s2);//找出前i-1個節點中權值最小的節點下標
    HT[s1].parent = i;
    HT[s2].parent = i;
    HT[i].lchild = s1;
    HT[i].rchild = s2;
    HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    //哈夫曼編碼
    HC = (char **)malloc((n)*sizeof(char *));
    //暫存編碼
    code = (char *)malloc(n*sizeof(char));//使用了第0單元
    for ( i = 1; i <= n; i++ )
    {
    for ( c = i, f = HT[c].parent, j = 0; f != 0; c = HT[c].parent, f = HT[c].parent, j++ )
    {//從葉子掃描到根
        if ( HT[f].lchild == c )
        {
        code[j] = '0';
        }
        else if(HT[f].rchild == c)
        {
        code[j] = '1';
        }
        else
        {//否則什麼也不做
        ;
        }
    }
    code[j] = '\0';
    HC[i] = (char *)malloc(strlen(code)*sizeof(char));
    strcpy(HC[i],code);
    }

}

//huffmanCoding.c
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#define N 6

typedef struct huffNode
{
unsigned int weight; //權重
unsigned int lchild,rchild,parent; //左右子節點和父節點
}HTNode,*HuffTree;
typedef char **HuffCode;

//找出數組中無父節點且權值最小的兩個節點下標,分別用s1和s2保存
void select(const HuffTree &HT,int n,int &s1,int &s2);
//HT:哈夫曼樹，HC:哈夫曼編碼，w:構造哈夫曼樹節點的權值，n:構造哈夫曼樹節點的個數
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n);

int main()
{
    int i;
    char key[N] = {'0','A','B','C','D','E'};//第0個元素保留不用
    int w[N] = {0,1,2,4,5,6}; //第0個元素保留不用
    HuffTree HT;
    HuffCode HC;
    HuffmanCode(HT,HC,w,N - 1);
    for ( i = 1; i < N; i++ )
printf("%c:%s\n",key[i],HC[i]);

    printf("\n");
    return 0;
}

//找出數組中權值最小的兩個節點下標,分別用s1和s2保存
void select(const HuffTree &HT,int n,int &s1,int &s2)
{
    int i;
    s1 = s2 = 0;
    int min1 = INT_MAX;//最小值，INT_MAX在<limits.h>中定義的
    int min2 = INT_MAX;//次小值

    for ( i = 1; i <= n; ++i )
    {
if ( HT[i].parent == 0 )
{//篩選沒有父節點的最小和次小權值下標
     if ( HT[i].weight < min1 )
     {//如果比最小值小
  min2 = min1;
   s2 = s1;
  min1 = HT[i].weight;
  s1 = i;
     }
     else if ( (HT[i].weight >= min1) && (HT[i].weight < min2) )
        {//如果大於等於最小值，且小於次小值
  min2 = HT[i].weight;
   s2 = i;
     }
     else
     {//如果大於次小值，則什麼都不做
  ;
     }
}
    }
}

//HT:哈夫曼樹，HC:哈夫曼編碼，w:構造哈夫曼樹節點的權值，n:構造哈夫曼樹節點的個數
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n)
{
    int s1;
    int s2;
    int m = 2 * n - 1;       //容易知道n個節點構造的哈夫曼樹是2n-1個節點
    int i,c,f,j;
    char *code; //暫存編碼的
    HT = (HuffTree)malloc((m+1)*sizeof(HTNode)); //0單元未使用

    for ( i = 1; i <= n; i++ )
        HT[i] = {w[i],0,0,0};//初始化前n個節點(構造哈夫曼樹的原始節點)

    for ( i = n + 1; i <= m; i++ )
HT[i] = {0,0,0,0}; //初始化後n-1個節點

    //構建哈夫曼樹
    for ( i = n + 1; i <= m; i++)
    {
select(HT,i-1,s1,s2);//找出前i-1個節點中權值最小的節點下標
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    //哈夫曼編碼
    HC = (char **)malloc((n)*sizeof(char *));
    //暫存編碼
    code = (char *)malloc(n*sizeof(char));//使用了第0單元
    for ( i = 1; i <= n; i++ )
    {
for ( c = i, f = HT[c].parent, j = 0; f != 0; c = HT[c].parent, f = HT[c].parent, j++ )
{//從葉子掃描到根
     if ( HT[f].lchild == c )
     {
  code[j] = '0';
     }
     else if(HT[f].rchild == c)
     {
  code[j] = '1';
     }
      else
     {//否則什麼也不做
  ;
     }
}
code[j] = '\0';
   HC[i] = (char *)malloc(strlen(code)*sizeof(char));
strcpy(HC[i],code);
    }

}