基础概念
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
结点的权值：
将树中结点赋给一个含有某种含义的数值。记为：Wi(i=1,2,...n)
路径长度：
等于路径上的结点数减1。
结点的带权路径长度：
从根结点到该结点的路径长度与该结点的权值的乘积。记为：Li(i=1,2,...n)。
树的带权路径长度：
树中所有叶子结点的带权路径长度之和
记为WPL
= (W1L1+W2L2+W3L3+...+WnLn)，
如果让这N个结点，构成一棵有N个叶结点的二叉树，可以证明哈夫曼树的WPL是最小的。
哈夫曼树也是效率最高的判别树。（ 判断树：用于描述分类的判断树）
注意：
- 满二叉树不一定是哈夫曼树；
- 哈夫曼树中权值越大的叶子离根越近
- 具有相同带权结点的哈夫曼树不惟一
构造思想
构造哈夫曼口诀:
- 构造森林全是根,
- 先用两小造新树,
- 删除两小添新人,
- 重复2,3剩单根
具体来说就是：
- 根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
- 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
- 在F中删除这两棵树,同时将新的二叉树加入森林中.
- 重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)
构造代码
伪代码：
将n个结点放入集合S
while (S中的结点数 > 1){
取走S中2个权值最小的结点，计算它们值之和，并加入S
}
return 集合S剩下的结点 // 剩下的结点就是根结点
借助优先队列实现代码：
#include <bits/stdc++.h>
using namespace std;
struct Huffman
{
Huffman *lchild;
Huffman *rchild;
double data;
};
struct cmp
{ /* 规定优先队列的排序规则 */
bool operator()(Huffman *a, Huffman *b) const
{
return (a->data > b->data); /* 小顶堆 */
}
};
int main()
{
priority_queue<Huffman *, vector<Huffman *>, cmp> Q;
double x;
while (cin >> x)
{
Huffman *h = new Huffman();
h->data = x;
h->lchild = h->rchild = 0;
Q.push(h);
}
Huffman *p;
while (Q.size() > 1)
{ /* 如果Q剩余结点大于1，则执行循环体 */
p = new Huffman();
Huffman *p1, *p2;
p1 = Q.top(); /* 依次取出权值最小的两个结点，放入p1和p2 */
Q.pop();
p2 = Q.top();
Q.pop();
/*
计算两结点的权值之和，存入p，且因为
p1->data <= p2->data，可以将权值小
的结点存入p的左子树，权值大的结点存入p
的右子树，最后将p放入Q中
*/
p->data = p1->data + p2->data;
p->lchild = p1;
p->rchild = p2;
Q.push(p);
}
Pre(F);
return 0;
}
Huffman 编码
编码规则：
从根节点到每一个叶子节点的路径上，左分支记为0，右分支记为1， 将这些0与1连起来即为叶子节点的哈夫曼编码。如下图：
哈夫曼编码是最优前缀码
前缀编码：
要求任一字符的编码都不能是另一字符编码的前缀。
为什么哈夫曼编码是最优前缀码？
代码：
/*
code 变量的初始值是空字符串，采用二叉树后续遍历，如果是非叶子结点，
存在左子树就将code加"0"，存在右子树就将code加"1"，继续递归调用；
如果是叶子结点，就记录到键值对（map）里。
*/
void huffman_code(Huffman* h, string code, map<double, string>& map_huff)
{
if (!h)
return;
if (h->lchild)
huffman_code(h->lchild, code + "0", map_huff);
if (h->rchild)
huffman_code(h->rchild, code + "1", map_huff);
if (h->lchild == 0 && h->rchild == 0) {
map_huff[h->data] = code;
return;
}
}