C語(yǔ)言實(shí)現(xiàn)哈夫曼樹(shù)的方法

更新時(shí)間：2021年05月03日 10:46:05 作者：奮斗的龍貓

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)哈夫曼樹(shù)的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了C語(yǔ)言實(shí)現(xiàn)哈夫曼樹(shù)的具體代碼，供大家參考，具體內(nèi)容如下

準(zhǔn)備工作：

1、定義一個(gè)結(jié)構(gòu)體，表示一個(gè)節(jié)點(diǎn)。其中，這個(gè)結(jié)構(gòu)體有4個(gè)成員變量，分別表示是這個(gè)節(jié)點(diǎn)的權(quán)值，父節(jié)點(diǎn)及左右子節(jié)點(diǎn)的下標(biāo)
2、定義一個(gè)整形數(shù)組，用于存放各個(gè)節(jié)點(diǎn)的權(quán)值
3、定義一個(gè)整形數(shù)組，用于存放哈夫曼編碼，當(dāng)然也可以定義一個(gè)整形數(shù)組來(lái)存放哈夫曼編碼

構(gòu)建哈夫曼樹(shù)：

1、給這個(gè)哈夫曼樹(shù)創(chuàng)建一個(gè)結(jié)構(gòu)體數(shù)組，其中分配的空間是2 * n - 1，因?yàn)槲覀兌贾拦蚵鼧?shù)的性質(zhì)有一個(gè)是:給定n個(gè)葉子節(jié)點(diǎn)，那么由這n個(gè)葉子節(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)一共含有2 * n - 1個(gè)節(jié)點(diǎn)。
2、結(jié)構(gòu)體數(shù)組前面n個(gè)用于存放n個(gè)葉子節(jié)點(diǎn)，然后后面的n - 1個(gè)節(jié)點(diǎn)用于存放父節(jié)點(diǎn)。這時(shí)候，我們需要遍歷這個(gè)結(jié)構(gòu)體數(shù)組，將所有的節(jié)點(diǎn)的進(jìn)行初始化，即節(jié)點(diǎn)的權(quán)值就是結(jié)構(gòu)體數(shù)組各個(gè)下標(biāo)對(duì)應(yīng)的值，然后節(jié)點(diǎn)的父節(jié)點(diǎn)及子節(jié)點(diǎn)的下標(biāo)為-1，表示的是這個(gè)節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，同時(shí)也沒(méi)有子節(jié)點(diǎn)。
3、遍歷數(shù)組，將獲取數(shù)組中兩個(gè)最小的葉子節(jié)點(diǎn)，然后將他們的權(quán)值合并構(gòu)成一個(gè)新節(jié)點(diǎn)。在這一步中，我們同時(shí)需要知道這兩個(gè)最小節(jié)點(diǎn)在結(jié)構(gòu)體數(shù)組中的下標(biāo)，只有這樣，我們才可以知道它的父節(jié)點(diǎn)的左右子節(jié)點(diǎn)的下標(biāo)，在初始化父節(jié)點(diǎn)的時(shí)候需要用到。
4、如果已經(jīng)進(jìn)行了n - 1次數(shù)操作，表明已經(jīng)構(gòu)建完成了。

獲取哈夫曼編碼:

1、由于我們將所有節(jié)點(diǎn)的權(quán)值都賦值給了一個(gè)數(shù)組，并且哈夫曼樹(shù)中的節(jié)點(diǎn)的下標(biāo)和這個(gè)數(shù)組的下標(biāo)是一一對(duì)應(yīng)的，那么我們只需要首先在數(shù)組中獲取這個(gè)數(shù)字的下標(biāo)，就表示他在哈夫滿樹(shù)中的下標(biāo)也是這個(gè)，然后往它的父節(jié)點(diǎn)方向走，如果當(dāng)前節(jié)點(diǎn)時(shí)它父節(jié)點(diǎn)的右子節(jié)點(diǎn)，那么就將1存放到數(shù)組arr2中，否則字符將0存放到數(shù)組arr2中。重復(fù)這一步，直到當(dāng)前的節(jié)點(diǎn)的父節(jié)點(diǎn)為空，及已經(jīng)遍歷到了根節(jié)點(diǎn)。
2、重復(fù)步驟一，存放數(shù)字的數(shù)組已經(jīng)遍歷完了，這時(shí)候已經(jīng)將所有數(shù)字的哈夫曼編碼都已經(jīng)輸出了

#include<stdio.h>
#define MAX_SIZE 1000
typedef struct NODE Node;
struct NODE{
   int weight;//節(jié)點(diǎn)的權(quán)值
   int parent,lchild,rchild;
};
/*
初始化或者更改節(jié)點(diǎn)的信息，比如，如果這個(gè)節(jié)點(diǎn)是一個(gè)新節(jié)點(diǎn)，那么
就需要將這個(gè)節(jié)點(diǎn)初始化成一個(gè)葉子節(jié)點(diǎn)，否則需要修改這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
*/
void initNode(Node &node,int weight,int parent,int lchild,int rchild){
    node.weight = weight;
    node.lchild = lchild;
    node.rchild = rchild;
    node.parent = parent;
}
/*
1、有n個(gè)葉子節(jié)點(diǎn)，那么構(gòu)建哈夫曼樹(shù)的時(shí)候，需要分配n * 2 - 1個(gè)內(nèi)存空間，前n
個(gè)表示的是新輸入的葉子節(jié)點(diǎn)，后面n - 1表示的是葉子節(jié)點(diǎn)的父節(jié)點(diǎn)
2、遍歷這個(gè)數(shù)組，將進(jìn)行初始化，即給這些節(jié)點(diǎn)的權(quán)值賦值，并且將他的左右子節(jié)
點(diǎn)、父節(jié)點(diǎn)賦初始值為-1，從而構(gòu)建了n個(gè)葉子節(jié)點(diǎn)
3、遍歷數(shù)組，從而將從這個(gè)數(shù)組中跳出兩個(gè)值最小的葉子節(jié)點(diǎn)，同時(shí)需要標(biāo)記他們的下標(biāo)，從而可以知道當(dāng)前最小值節(jié)點(diǎn)的父節(jié)點(diǎn)的左右子節(jié)點(diǎn)的下標(biāo)，方便下次尋找
最小值的葉子結(jié)點(diǎn)的時(shí)候不會(huì)再找到已經(jīng)找過(guò)的葉子節(jié)點(diǎn)
4、將新節(jié)點(diǎn)插入到數(shù)組的最后。
5、重復(fù)3，4的操作，直到只有一個(gè)節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是哈夫曼樹(shù)的根節(jié)點(diǎn)
*/
void createHuffmanTree(Node *node,int *arr,int n){
    //n表示有n個(gè)葉子節(jié)點(diǎn)，arr數(shù)組存放的是所有葉子節(jié)點(diǎn)的值
   int i,j,min1,min2,x1,x2,total;//min1:第一個(gè)最小值，min2:第二個(gè)最小值,x1:第一個(gè)最小值的下標(biāo)，x2:第二個(gè)最小值的下標(biāo)
   for(i = 0; i < n; i++){
       initNode(node[i],arr[i],-1,-1,-1);//調(diào)用initNode方法，從而將節(jié)點(diǎn)進(jìn)行初始化
   }
   total = n * 2 - 1;//total表示的是哈夫曼所有節(jié)點(diǎn)的個(gè)數(shù)
   for(i = n; i < total; i++){
        //i之所以從n開(kāi)始，是因?yàn)榈谝粋€(gè)父節(jié)點(diǎn)這個(gè)下標(biāo)（前n個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)）
        min1 = 65432;//定義兩個(gè)最小值
        min2 = min1;
        x1 = x2 = 0;//假設(shè)兩個(gè)最小值的下標(biāo)都是0
        for(j = 0; j < i; j++){
            //判斷當(dāng)前下標(biāo)的節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)
           if(node[j].parent == -1){
          //如果當(dāng)前節(jié)點(diǎn)的parent等于-1，表示這個(gè)節(jié)點(diǎn)是一個(gè)葉子節(jié)點(diǎn)，那么我們需要判斷他是否一個(gè)最小節(jié)點(diǎn)
                if(node[j].weight < min1){
         //如果當(dāng)前這個(gè)節(jié)點(diǎn)的值比min1小，那么我們需要更新min2，min1，同時(shí)需要更新兩者對(duì)應(yīng)的下標(biāo)
                    min2 = min1;
                    x2 = x1;
                    min1 = node[j].weight;
                    x1 = j;
                }else if(node[j].weight < min2){
                 /*
                 如果當(dāng)前這個(gè)節(jié)點(diǎn)比第一個(gè)最小值要大，那么我們需要判斷
                 他是否比第二個(gè)最小值小，如果是，那么更新min2,并且更新x2
                 */
                   min2 = node[j].weight;
                   x2 = j;
                }
           }
        }
        /*
        找到兩個(gè)最小節(jié)點(diǎn)之后，我們需要將這兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指向i，
        然后將i這個(gè)節(jié)點(diǎn)進(jìn)行初始化,并且新節(jié)點(diǎn)的左子節(jié)點(diǎn)比右子節(jié)點(diǎn)小
        從而構(gòu)建唯一的哈夫曼樹(shù)
        */
        node[x1].parent = i;
        node[x2].parent = i;
        initNode(node[i],min1 + min2,-1,x1,x2);//初始化合并之后的新節(jié)點(diǎn)
   }
}
void huffmanCode(Node *node,int child,int *str){
    //str表示的是這個(gè)葉子節(jié)點(diǎn)的哈夫曼編碼
    int i,parent,j = 0,e;
    parent = node[child].parent;//獲取當(dāng)前這個(gè)葉子節(jié)點(diǎn)的父節(jié)點(diǎn)
    while(parent != -1){
        if(node[parent].lchild == child){
            //如果當(dāng)前這個(gè)節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么就將0壓入到數(shù)組中,否則將1壓入數(shù)組中
            str[j++] = 0;
        }else{
            str[j++] = 1;
        }
        child = parent;
        parent = node[child].parent;
    }
    e = j;//當(dāng)退出循環(huán)的時(shí)候，j表示的是這個(gè)數(shù)的哈夫曼編碼的長(zhǎng)度，所以需要從下標(biāo)為j - 1開(kāi)始逆序輸出，才是這個(gè)數(shù)的哈夫曼編碼
    for(j = e - 1; j>= 0; j--)
        printf("%d",str[j]);
    printf("\n");
}
int main(){
  Node node[MAX_SIZE];
  int arr[MAX_SIZE];//定義一個(gè)整形數(shù)組，用于存放所有葉子節(jié)點(diǎn)的權(quán)值
  int arr2[MAX_SIZE];//arr2用于存放一個(gè)數(shù)字的哈夫曼編碼
  int n,i,j,e;
  printf("請(qǐng)輸入葉子節(jié)點(diǎn)的個(gè)數(shù):");
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
  createHuffmanTree(node,arr,n);//構(gòu)建哈夫曼樹(shù)
  /*
  獲取哈夫曼編碼:
  1、將遍歷數(shù)組arr，從而獲得各個(gè)葉子節(jié)點(diǎn)的權(quán)值以及下標(biāo)
  2、通過(guò)這個(gè)下標(biāo)，我們從這個(gè)節(jié)點(diǎn)向根節(jié)點(diǎn)走去，如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子
  節(jié)點(diǎn)，那么將0壓入到數(shù)組中，否則將1壓入到數(shù)組arr2中
  3、逆序輸出arr2
  */
  for(i = 0; i < n; i++){
    huffmanCode(node,i,arr2);//調(diào)用這個(gè)方法，將當(dāng)前下標(biāo)對(duì)應(yīng)的數(shù)字的哈夫曼編碼輸出
  }
  return 0;
}