引例
为了更好地理解哈夫曼树的用途我们先来看一个引例
什么是哈夫曼树？
首先我们来了解一下什么是带权路径长度：从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼树并不唯一，但带权路径长度一定是相同的。利用哈夫曼树可以根据结点不同的查找频率来提高搜索效率
怎么构建哈夫曼树？
算法：- 将叶子结点按权值从小到大排序构成森林
- 从森林中取出最小的两个结点构成一棵新树，两较小结点作为新树的左右子树，新树的权值为两较小结点权值之和，从森林中删去取出的结点并将构成的新树加入森林中（ 注意：我们需要保证Huffman树的编码是前缀编码，因此它必须是一颗满树，同时只能在叶子节点中存储具体的字符。 ）
- 重复操作2，直到森林中只剩一棵树，该树即为哈夫曼树
图示：
eg:有结点{10，20，30，40}，以这四个权值构建哈夫曼树的过程如下
哈夫曼编码
什么是哈夫曼编码？
出现频率较高的符号用较短的编码表示，出现频率较低的符号用较长的编码表示。这样就降低了编码之后的字符串长度，达到压缩数据的目的。对于一个已经压缩好的数据文件，我们只需要拥有对应的编码表，则可将其展开。
哈夫曼树的操作
准备工作：
有关c++优先队列(priority_queue)的用法可以看 这里
#include <iostream>
#include <queue>
#include <map>
#include <sstream>
using namespace std;
/** 定义二叉树Htree (HuffmanTree)*/
typedef
struct Node
{
float weight; // 权:叶子权为字符频次,有分支结点则为左右子树权值和
char alpha; // 结点字符：叶子结点为编码字符，分支结点字符则为哑元'\0'
Node *lch;
Node *rch;
Node(float e,char ch=0,Node *lt=0, Node *rt=0) // ctor构造根结点：权值e，字符ch，左右子树lt,rt
:weight(e),alpha(ch),lch(lt),rch(rt) {}
}*HTree;
/* 重载运算符()的类,其行为仿似函数,故名仿函数
Lt定义了树之优先级:根权值大者优先级高 */
struct Lt
{
bool operator()(HTree ta, HTree tb)
{
return ta->weight > tb->weight;
}
};
typedef map<char,string> Dict; // 编码字典类型Dict：字符为键,编码为值
哈夫曼树的构建
/*利用字符数组alpha[0..n-1]和对应权值数组ws[0:n-1],构造HuffmanTree*/
HTree CreateHT(char alphs[],float ws[], int n)
{
/*优先队列类：元素类型是树,底层采用顺序表vector,元素优先级采用Lt类中定义的operator()*/
priority_queue< HTree, vector<HTree>, Lt > forest;
for(int i=0; i<n; i++) //输入n个结点，创建结点的树林
{
forest.push( new Node(ws[i],alphs[i]));
}
for(int i=0; i<n-1; i++) //两两合并n-1次
{
HTree t1 = forest.top(); //取出最小的树t1
forest.pop(); //删去t1
HTree t2 = forest.top(); //再取最小的t2
forest.pop(); //删去t2
float w = t1->weight + t2->weight;
forest.push(new Node(w,0,t1,t2)); // 合并为新树,新数结点字符为'\0',加入森林
}
return forest.top(); // 森林中最后一棵树 即所建huffman树
}
生成密码字典（哈夫曼编码）
/*通过遍历Hufman树t,生成密码字典dict*/
void generateDict(HTree t, Dict &dict)
{
static string code; //字符密码
if(0==t)
return;
if(t->alpha!=0) //达到叶子结点,得该字符的编码(唯叶子字符不为\0)
dict[t->alpha] = code; // 字典增一项
code +='0'; // 左走为0
generateDict(t->lch,dict);
code.erase(code.end()-1); // 回溯：删除进入左子树时,在串尾添加的0
code+='1'; // 右走为0
generateDict(t->rch,dict);
code.erase(code.end()-1); // 回溯：删除进入右子树时,在串尾添加的1
return;
}
对字符串进行编码
/**使用编码字典dict,返回串txt的编码*/
string encode(string txt, Dict dict)
{
string code;
for(int i=0; i<txt.size(); i++)
code += dict[ txt[i] ]; // 查字典dict得txt[i]的编码
return code;
}
解码
/**使用Huffman树t解码code，返回解码后的报文*/
string Decode(HTree t, string code)
{
string txt;
istringstream in(code); // 字符串输入流 in
Node *p = t; // 从根开始解码
char dire;
while( in>>dire ) // 依次读入各字符
{
p = ('0'==dire ? p->lch :p->rch); // 0向左走,1向右走
if( p->alpha ) //到达叶子得一字符
{
txt += p->alpha;
p = t; // 重新从根开始解码下一个字符
}
}
return txt;
}
主函数
int main()
{
char alphs[] = "ABCD";
float ws[] = {9,4,5,2};//分别对应ABCD的权值
int n = 4;
Dict dict; // 编码字典
HTree t = CreateHT(alphs,ws, n); // 构造Huffman树t
generateDict(t,dict); //以Huffman树来构造字典dict
cout << encode("ABC",dict) <<endl; // 输出"ABC"的编码
cout << Decode(t,"011110"); // 输出编码"011110"的报文
return 0;
}
运行结果：
011110
ABC
