一、概念

給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫做Huffman編碼（有時(shí)也稱為霍夫曼編碼）

二、構(gòu)建哈夫曼樹

由權(quán)值分別為5，15，40，30，10的字符ABCDE構(gòu)建哈夫曼樹
1、將權(quán)值最小的A，E作為樹的左右孩子，生成一棵樹，頂點(diǎn)為N1且權(quán)值為A和E的權(quán)值和15

BCA97988-F869-4C3B-A61C-1BD7F493FB49.png

2、繼續(xù)遍歷未加入到樹中的字符和樹的頂點(diǎn)，將權(quán)值最小的兩個(gè)字符按左右孩子生成樹，頂點(diǎn)為N2，權(quán)值是左右孩子權(quán)值和

截屏2020-05-10下午10.23.07.png

截屏2020-05-10下午10.28.00.png

截屏2020-05-10下午10.31.04.png

代碼實(shí)現(xiàn)

const int MaxValue = 10000;//初始設(shè)定的權(quán)值最大值

//設(shè)定哈夫曼樹為順序存儲
//哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)
typedef struct HuffNode{
  int weight;       //權(quán)值
  int flag;         //標(biāo)記是否已加入到樹中 0為沒加入，1為已加入
  int parent;       //該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)
  int leftChild;    //該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的下標(biāo)
  int rightChild;   //該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的下標(biāo)
}HuffNode;

構(gòu)建哈夫曼樹

void huffmanTree(int weight[], int n, HuffNode *h){
  //有n個(gè)葉子結(jié)點(diǎn)的樹共有2*n-1個(gè)結(jié)點(diǎn)
  for (int i = 0; i<2*n-1; i++) {
      if (i<n) {
          h[i].weight = weight[i];
      }else{
          h[i].weight = 0;
      }
      h[i].parent = 0;
      h[i].flag = 0;
      h[i].leftChild = -1;
      h[i].rightChild = -1;
  }
  int m1,m2,x1,x2;
  for (int i = 0; i<n-1; i++) {
      m1 = MaxValue;  //存儲權(quán)值最小的值
      m2 = MaxValue;  //存儲權(quán)值第二小的值
      x1 = 0;   //存儲權(quán)值最小的值的下標(biāo)
      x2 = 0;   //存儲權(quán)值第二小的值的下標(biāo)
      for (int j = 0; j<n+i; j++) {
          if (h[j].weight<m1 && h[j].flag == 0) {
              m2 = m1;
              x2 = x1;
              m1 = h[j].weight;
              x1 = j;
          }else if (h[j].weight<m2 && h[j].flag == 0){
              m2 = h[j].weight;
              x2 = j;
          }
      }
      h[x1].parent = n+i;
      h[x2].parent = n+i;
      h[x1].flag = 1;
      h[x2].flag = 1;
      
      h[n+i].leftChild = x1;
      h[n+i].rightChild = x2;
      h[n+i].weight = m1+m2;
  }
}

哈夫曼編碼

const int MaxBit = 8;//初始設(shè)定的最大編碼位數(shù)
typedef struct Code//存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu)
{
  int bit[MaxBit];//數(shù)組
  int start;  //編碼的起始下標(biāo)
  int weight;//字符的權(quán)值
}Code;

void huffmanCode(HuffNode h[], int n, Code c[]){
  //創(chuàng)建一個(gè)結(jié)構(gòu)為Code的結(jié)點(diǎn)
  Code *cd = (Code *)malloc(sizeof(Code));
  int child, parent;
  
  //求n個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼
  for (int i = 0; i<n; i++) {
      cd->start = 0;   //從0開始計(jì)數(shù)
      cd->weight = h[i].weight;  //獲取結(jié)點(diǎn)的權(quán)值
      child = i;
      parent = h[i].parent;
      
      //由葉結(jié)點(diǎn)向上到根結(jié)點(diǎn)
      while (parent != 0) {
          if (h[parent].leftChild == child) {
              cd->bit[cd->start] = 0;//該結(jié)點(diǎn)為左孩子編碼為0
          }else{
              cd->bit[cd->start] = 1;//該結(jié)點(diǎn)為右孩子編碼為1
          }
          cd->start++;
          child = parent;
          parent = h[child].parent;
      }
      //將編碼值反轉(zhuǎn)
      for (int j = cd->start - 1; j>=0; j--) {
          int k = cd->start - 1- j;
          c[i].bit[k] = cd->bit[j];
      }
      c[i].weight = cd->weight;
      c[i].start = cd->start;
  }
}

demo