HuffMan tree

定义

        给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

基础知识

• 路径：从树中的一个结点到另一个结点之间的分支构成这两点之间的路径
• 路径长度：路径上的分支数目称作路径长度
• 树的路径长度：从树根到每一个结点的路径长度之和
• 权：赋予某个实体的一个量
• 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积
•  树的带权路径长度：树中所有叶子结点的带权路径长度之和

        哈夫曼编码跟 ASCII 编码有什么区别？ASCII 编码是对照ASCII 表进行的编码，每一个字符符号都有对应的编码，其编码长度是固定的。而哈夫曼编码对于不同字符的出现频率其使用的编码是不一样的。其会对频率较高的字符使用较短的编码，频率低的字符使用较高的编码。这样保证总体使用的编码长度会更少，从而实现到了数据压缩的目的。

哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

例如：对 2，3，4，6 这四个数进行构造

huffman存储结构就是采用二叉树存储方式中的一种静态存储（二叉链表的静态结构）

因为每次要找到序列中权值最小的进行合并，所以在创建哈夫曼树时采用优先级队列，每次取出最小值。

列表中由n个数据，构建出来的哈夫曼树就有2*n - 1个节点

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <functional>
#include <ios>
#include<iostream>
#include<vector>
#include<string.h>
#include<stack>
#include<math.h>
#include<cstring>
#include<queue>
using namespace std;const int n = 8;
const int m = 2 * n;
typedef unsigned int WeightType;
typedef unsigned int NodeType;typedef struct {WeightType weight;NodeType parent, leftchild, rightchild;
}HTNode;typedef HTNode HuffManTree[m];
typedef struct {char ch;char code[n + 1];
}HuffManCode;
typedef HuffManCode Huffcode[n + 1];void InitHuffManTree(HuffManTree &hft, WeightType w[]){memset(hft, 0, sizeof(HuffManTree));for(int i = 0; i < n; ++i){hft[i + 1].weight = w[i];}
}
void PrintHuffManTree(HuffManTree hft){for(int i = 1; i < m; ++i){printf("index :%3d weight : %3d parent: %3d leftchild %3d rightchild %3d\n" ,i, hft[i].weight, hft[i].parent, hft[i].leftchild, hft[i].rightchild);}printf("\n");
}
struct IndexWeight{int index;WeightType weight;operator WeightType() const {return  weight;}
};
void CreateHuffManTree(HuffManTree hft){std::priority_queue<IndexWeight, vector<IndexWeight>, std::greater<IndexWeight> > qu;for(int i = 0; i <=n; ++i){qu.push(IndexWeight{i, hft[i].weight});}int k = n + 1;while(!qu.empty()){if(qu.empty())  break;IndexWeight left = qu.top();qu.pop();if(qu.empty())  break;IndexWeight right = qu.top(); qu.pop();hft[k].weight = left.weight + right.weight;hft[k].leftchild = left.index;hft[k].rightchild = right.index;hft[left.index].parent = k;hft[right.index].parent = k;qu.push({k, hft[k].weight});k += 1;}
}
void InitHuffManCode(Huffcode hc, const char * ch){memset(hc, 0, sizeof(HuffManCode));for(int i =1 ;i <= n; ++i){hc[i].ch = ch[i -1];hc[i].code[0] = '\0';}
}void PrintHuffCode(Huffcode hc){for(int i = 1; i <= n; ++i){printf("data : %c ->code %s\n", hc[i].ch, hc[i].code);}printf("\n");
}
void CreateHuffCode(HuffManTree hft, Huffcode hc){char code[n + 1] = {0};for(int i = 1; i <= n; ++i){int k = n;code[k] = '\0';int c = i;int pa = hft[c].parent;while(pa != 0){code[--k] = hft[pa].leftchild == c ? '0' : '1';c = pa;pa = hft[c].parent;}strncpy(hc[i].code, &code[k],  n);}
}
int main(){WeightType w[n] = {5,29,7,8,14,23,3,11};char ch[n + 1] = {'A','B', 'C', 'D', 'E', 'F', 'G', 'H'};HuffManTree hft = {0};Huffcode hc = { 0};InitHuffManTree(hft, w);InitHuffManCode(hc, ch);PrintHuffManTree(hft);PrintHuffCode(hc);CreateHuffManTree(hft);CreateHuffCode(hft, hc);PrintHuffManTree(hft);PrintHuffCode(hc);return 0;
}

参考：

https://blog.csdn.net/Initial_Mind/article/details/124354318