数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现 - melonstreet_H5之家

0. 数据结构图文解析系列

数据结构系列文章

数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现

数据结构图文解析之：栈的简介及C++模板实现

数据结构图文解析之：队列详解与C++模板实现

数据结构图文解析之：树的简介及二叉排序树C++模板实现.

数据结构图文解析之：AVL树详解及C++模板实现

数据结构图文解析之：二叉堆详解及C++模板实现

数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现

1. 哈夫曼编码简介

哈夫曼编码（Huffman Coding）是一种编码方式，也称为“赫夫曼编码”，是David A. Huffman1952年发明的一种构建极小多余编码的方法。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号进行编码，出现频率较高的源符号采用较短的编码，出现频率较高的符号采用较长的编码，使编码之后的字符串字符串的平均长度、期望值降低，以达到无损压缩数据的目的。
举个例子，现在我们有一字符串：

this is an example of a huffman tree

这串字符串有36个字符，如果按普通方式存储这串字符串，每个字符占据1个字节，则共需要36 * 1 * 8 = 288bit。
经过分析我们发现，这串字符串中各字母出现的频率不同，如果我们能够按如下编码：

字母频率编码 --- 字母频率编码

space 7 111 s 2 1011

a 4 010 t 2 0110

e 4 000 l 1 11001

f 3 1101 o 1 00110

h 2 1010 p 1 10011

i 2 1000 r 1 11000

m 2 0111 u 1 00111

n 2 0010 x 1 10010

编码这串字符串，只需要：
(7+4+4)x3 + (3+2+2+2+2+2+2)x4 + (1+1+1+1+1+1)x 5 = 45+60+30 = 135bit
编码这串字符串只需要135bit！单单这串字符串，就压缩了288-135 = 153bit。

那么，我们如何获取每个字符串的编码呢？这就需要哈夫曼树了。
源字符编码的长短取决于其出现的频率，我们把源字符出现的频率定义为该字符的权值。

2. 哈夫曼树简介

哈夫曼又称最优二叉树。是一种带权路径长度最短的二叉树。它的定义如下。

哈夫曼树的定义

假设有n个权值{w1,w2,w3,w4...,wn}，构造一棵有n个节点的二叉树，若树的带权路径最小，则这颗树称作哈夫曼树。这里面涉及到几个概念，我们由一棵哈夫曼树来解释

3. 构造哈夫曼树 3.1 哈夫曼树的节点结构

/*哈夫曼树的节点定义*/ template <typename T> struct HuffmanNode { HuffmanNode(T k,HuffmanNode<T>*l=nullptr,HuffmanNode<T>* r=nullptr) :key(k),lchild(l), rchild(r){} ~HuffmanNode(){}; T key; //节点的权值 HuffmanNode<T>* lchild; //节点左孩 HuffmanNode<T>* rchild; //节点右孩 };

3.2 哈夫曼树的抽象数据类型

template <typename T> class Huffman { public: Huffman(); ~Huffman(){}; postOrder(); destory(); : void preOrder(HuffmanNode<T>* pnode); void inOrder(HuffmanNode<T>* pnode); void postOrder(HuffmanNode<T>*pnode); void print(HuffmanNode<T>*pnode); void destroy(HuffmanNode<T>*pnode); private: HuffmanNode<T>* root; //哈夫曼树根节点 deque<HuffmanNode<T>*> forest;//森林 };

root:哈夫曼树的根结点。

forset : 森林，这里使用deque来存储森林中树的根节点。

3.3 哈夫曼树的构造步骤

假设有n个权值，则构造出的哈夫曼树有n个叶子节点.n个权值记为{w1,w2,w3...wn},哈夫曼树的构造过程为：

图一的树b为一棵哈夫曼树，它的叶子节点为{10，20，30，40}，以这4个权值构建树b的过程为：

这个过程很编码实现为:

/*创建哈夫曼树*/ template<typename T> void Huffman<T>::creat(T a[],int size) { for (int i = 0; i < size; i++) //每个节点都作为一个森林 { //为初始序列的元素构建节点。每个节点作为一棵树加入森林中。 HuffmanNode<T>* ptr = new HuffmanNode<T>(a[i],nullptr,nullptr); forest.push_back(ptr); } for (int i = 0; i < size - 1; i++) { //排序，以选出根节点权值最小两棵树 sort(forest.begin(), forest.end(), [](HuffmanNode<T>* a, HuffmanNode<T>*b){return a->key< b->key; }); HuffmanNode<T>*node = new HuffmanNode<T>(forest[0]->key + forest[1]->key, forest[0], forest[1]); //构建新节点 forest.push_back(node); //新节点加入森林中 forest.pop_front(); //删除两棵权值最小的树 forest.pop_front(); } root = forest.front(); forest.clear(); };

这里仅仅示范构建哈夫曼树的过程，没有经过性能上的优化和完善的异常处理。这里使用deque双端队列来存储森林中树根节点，使用库函数sort来对根节点依权值排序。这里也可以使用我们之前介绍的小顶堆来完成工作。

3.4 哈夫曼树的其他操作

其他操作在前几篇博文中都有介绍过，这里就不再啰嗦，可以在文章底部链接取得完整的工程源码。
这里贴出测试时需要的代码：