哈夫曼树和哈夫曼编码

基本概念

哈夫曼树(Huffman Tree)

哈夫曼树又称赫夫曼树、最优树，是最带权路径长度(WPL)最短的树。

路径：在树中，从一个结点到另一个结点之间的分支被称为路径。

路径长度：路径的分支数目。

结点的权：赋予结点代表某种意义的值，在哈夫曼树中权值可以理解为出现的频率。

树的带权路径长度(WPL)：所有叶子结点的带权路径长度之和。

哈夫曼编码(Huffman Coding)

哈夫曼编码是一种可变字长的编码方式，依据字符出现的频率来构造编码。为了能正确解码，可变字长编码必须满足前缀编码的性质，即任意一个字符的编码都不能是另一个字符编码的前缀，使用字符作为二叉树的叶子结点来设计，其得到的必定为前缀编码，为了得到最短前缀编码，使用哈夫曼树来进行设计。

算法思想

如何构建哈夫曼树？

1.从所有结点选出权值最小的两个结点，用这两个结点构建成一颗二叉树，该二叉树的结点权值为左右孩子权值之和。

2.将构建好的二叉树加入待构建的行列，注意：上一步选出的结点不再参与构建。

3.重复步骤1和步骤2，直到待构建行列剩余一个结点。

使用数组作为存储结构，在哈夫曼树中，没有度为1的结点，树的结点数量为n0+n2，根据n0=n2+1，可得出总结点数量为n * 2 - 1，n为叶子结点数量。

从待构建序列中选出两个权值最小的结点，必须保证：不能选有双亲的结点，两个结点不能重复。

求哈夫曼编码可自顶向下也可自底向上，本文采用自底向上。

代码实现

/*************************************************
 * Author           : TangRan                    
 * Blog             : tongyin.site               
 * Email            : tarngran@outlook.com       
 * Last modified    : 2022-11-12 18:09
 * Filename         : HuffmanTree.c
 * Description      :                            
 *************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

typedef char ElemType;
typedef char** HFcode;
typedef struct {
  ElemType ch;
  int weight;
  int parent, lchild, rchild;
}HTnode;

typedef struct {
  HTnode *data;
  int length;
}HT;

void select(HT *T, int *s1, int *s2) {
   int min = INT_MAX;
   for (int i = 0 ; i < T -> length ; ++i) {
     if (T -> data[i].parent == 0 && T -> data[i].weight < min) {
      *s1 = i;
      min = T -> data[i].weight;
     }
   }
   min = INT_MAX;
   for (int i = 0 ; i < T -> length ; ++i) {
     if (T -> data[i].parent == 0 && i != *s1) {
      if (T -> data[i].weight < min) {
        *s2 = i;
        min = T -> data[i].weight;
      }
     }
   }
}

void createHT(HT *T) {
  int s1, s2, len = T -> length * 2 - 1;
  for (int i = T -> length ; i < len ; ++i) {
   select(T, &s1, &s2);
   T -> data[i].parent = 0;
   T -> data[i].ch = '^';
   T -> data[s1].parent = T -> data[s2].parent = i;
   T -> data[i].lchild = s1;
   T -> data[i].rchild = s2;
   T -> data[i].weight = T -> data[s1].weight + T -> data[s2].weight;
   T -> length++;
  }
}

HT* initHTtree(char ch[], int w[], int length) {
  HT *T = (HT*)malloc(sizeof(HT));
  T -> data = (HTnode*)malloc(sizeof(HTnode) * (2 * length - 1));
  T -> length = length;
  for(int i = 0 ; i < length ; ++i) {
   HTnode tmp = {ch[i], w[i], 0, -1, -1};
   T -> data[i] = tmp;
  }
  return T;
}

void preOrder(const HT *T, int idx) {
  if (idx == -1) return;
  if (T -> data[idx].ch == '^')
   printf("%d ", T -> data[idx].weight);
  else
   printf("%c(%d) ",T -> data[idx].ch, T -> data[idx].weight);
  preOrder(T, T -> data[idx].lchild);
  preOrder(T, T -> data[idx].rchild);
}

//自底向上构建哈夫曼编码
HFcode huffmanCode(HT *T, int n) {
  if (!T || T -> length == 0) return NULL;
  HFcode HC = (HFcode)(malloc(n * sizeof(char*)));
  char *tmp = (char*)malloc(sizeof(char) * n);
  tmp[n - 1] = '\0';
  for (int i = 0 ; i < n ; i++) {
   int idx = n - 1;
   for (int cur = i, p = T -> data[cur].parent ; cur != T -> length - 1 ;cur = p, p = T -> data[p].parent) {
      if (T -> data[p].lchild == cur) tmp[--idx] = '0';
        else tmp[--idx] = '1';
   }
   HC[i] = (char*)malloc((n - idx) * sizeof(char));
   strcpy(HC[i], &tmp[idx]);
  }
  free(tmp);
  return HC;
}

int main() {
  char ch[] = {'a', 'b', 'c', 'd', 'e', 'f'};
  int w[] = {3,7,11,8,9,12};
  int chLen = sizeof(ch) / sizeof(ch[0]), wLen = sizeof(w) / sizeof(w[0]);
  HT *T = initHTtree(ch, w, wLen);
  createHT(T);
  preOrder(T, T -> length - 1);
  printf("\n");
  HFcode code = huffmanCode(T, chLen);
  for(int i = 0 ; i < chLen ; i++) {
   printf("%c = %s\n", ch[i], code[i]);
  }
  return 0;
}