前天acm实验课，老师教了几种排序，抓的一套题上有一个哈夫曼树的题，正好之前离散数学也讲过哈夫曼树，这里我就结合课本，整理一篇关于哈夫曼树的博客。
主要摘自https://www.cnblogs.com/skywang12345/p/3706821.html感谢大佬
https://www.cnblogs.com/kubixuesheng/p/4397798.html这位大佬举例很好
哈夫曼树的介绍
Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。
定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。 这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。
(01) 路径和路径长度
定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。
(02) 结点的权及带权路径长度
定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 例子：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。
(03) 树的带权路径长度
定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。 例子：示例中，树的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。
比较下面两棵树
上面的两棵树都是以{10, 20, 50, 100}为叶子节点的树。
左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右边的树WPL=350
左边的树WPL > 右边的树的WPL。你也可以计算除上面两种示例之外的情况，但实际上右边的树就是{10,20,50,100}对应的哈夫曼树。至此，应该堆哈夫曼树的概念有了一定的了解了，下面看看如何去构造一棵哈夫曼树。
哈夫曼树的图文解析
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：
1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
以{5,6,7,8,15}为例，来构造一棵哈夫曼树。
第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。
第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是11。 然后，将"树5"和"树6"从森林中删除，并将新的树(树11)添加到森林中。
第3步：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。 然后，将"树7"和"树8"从森林中删除，并将新的树(树15)添加到森林中。
第4步：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。 然后，将"树11"和"树15"从森林中删除，并将新的树(树26)添加到森林中。
第5步：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后，将"树15"和"树26"从森林中删除，并将新的树(树41)添加到森林中。 此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！
哈夫曼树代码
直接使用了PJQ师姐的代码，之后有空会更新。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
int key;
struct node *l;
struct node *r;
};
typedef struct node *pnode;
int mark[];
struct node huffman[];
void PrintNode(const pnode node)
{
printf("key = %d \n", node->key);
}
void PreOrder(pnode T)
{
if(T)
{
PrintNode(T);
PreOrder(T->l);
PreOrder(T->r);
}
}
void Select(int *mark, struct node *huffman, int size, int *choose)
{ int i;
for(i = ; i< size; i++)
{
if(mark[i])
{
choose[] = i;
i++;
break;
}
}
choose[] = choose[];
for(; i < size; i++)
{
if(mark[i])
{
if(huffman[choose[]].key >= huffman[i].key)
{
choose[] = choose[];
choose[] = i;
}
else if(huffman[choose[]].key > huffman[i].key)
{
choose[] = i;
}
} }
}
void Choose(int *mark, struct node *huffman, int size, int *choose)
{
int i;
int minkey = ;
int tkey = ;
int temp = ;
for(i = ; i< size; i++)
{
if(mark[i])
{
minkey = i;
i++;
break;
}
}
tkey = minkey;
for(; i< size; i++)
{
if(mark[i])
{
if(huffman[i].key < huffman[minkey].key)
{
tkey = minkey;
minkey = i;
}
if(tkey == minkey)
tkey = i;
if(huffman[tkey].key > huffman[i].key && i != minkey)
{
tkey = i;
}
}
}
choose[] = minkey;
choose[] = tkey;
}
pnode HuffmanTree(int *mark, struct node *huffman, int size)
{
int choose[];
int i;
pnode mynode;
for(i = ; i < size-; i++)
{
Select(mark, huffman, size, choose);
mynode = (pnode)malloc(sizeof(struct node));
mynode->key = huffman[choose[]].key+huffman[choose[]].key;//更新key值
mynode->l = (pnode)malloc(sizeof(struct node));
mynode->l->key = huffman[choose[]].key;
mynode->l->l = huffman[choose[]].l;
mynode->l->r = huffman[choose[]].r;
mynode->r = &huffman[choose[]];
huffman[choose[]] = *mynode;
mark[choose[]] = ;
free(mynode);
}
return &huffman[choose[]];
}
int main(void)
{
int key[] = {,,,,,,,};
int i;
pnode huffmantree;
memset(mark, -, sizeof(mark));
memset(huffman, , sizeof(huffman));
for(i = ; i < ; i++)
{
huffman[i].key = key[i];
}
huffmantree = HuffmanTree(mark, huffman, );
PreOrder(huffmantree);
return ;
}
在解决acm竞赛题时，可以直接使用C++ STL里的优先队列实现，因为优先队列具有直接排序的功能，可以模拟节点和合并。
这个代码是之前遇到的大顶堆问题，但它并不能建立树形结构，只能用来求树的最小带权路径长度。
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long int
using namespace std;
int main()
{
int n,i;
int x,y;
int a;
ll ans=;
priority_queue<int,vector<int>,greater<int> >q;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d",&a);
q.push(a);
}
while(q.size()>)
{
x=q.top();
q.pop();
y=q.top();
q.pop();
ans+=x+y;
q.push(x+y);
}
printf("%lld\n",ans);
return ;
}
哈夫曼编码
哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。
例：如果需传送的电文为 ‘ABACCDA’，它只用到四种字符，用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01,10, 11，则上述电文便为 ‘00010010101100’（共 14 位），译码员按两位进行分组译码，便可恢复原来的电文。
能否使编码总长度更短呢？
实际应用中各字符的出现频度不相同，用短（长）编码表示频率大（小）的字符，使得编码序列的总长度最小，使所需总空间量最少
数据的最小冗余编码问题
在上例中，若假设 A, B, C, D 的编码分别为 0，00，1，01，则电文 ‘ABACCDA’ 便为 ‘000011010’（共 9 位），但此编码存在多义性：可译为： ‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’ 等。
译码的惟一性问题
要求任一字符的编码都不能是另一字符编码的前缀，这种编码称为前缀编码（其实是非前缀码）。 在编码过程要考虑两个问题，数据的最小冗余编码问题，译码的惟一性问题，利用最优二叉树可以很好地解决上述两个问题
用二叉树设计二进制前缀编码
以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。
编码： A：0， C：10，B：110，D：111
任意一个叶子结点都不可能在其它叶子结点的路径中。
用哈夫曼树设计总长最短的二进制前缀编码
假设各个字符在电文中出现的次数（或频率）为 wi ，其编码长度为 li，电文中只有 n 种字符，则电文编码总长为：
设计电文总长最短的编码，设计哈夫曼树（以 n 种字符出现的频率作权），
由哈夫曼树得到的二进制前缀编码称为哈夫曼编码
例：如果需传送的电文为 ‘ABACCDA’，即：A, B, C, D
的频率（即权值）分别为 0.43, 0.14, 0.29, 0.14，试构造哈夫曼编码。
编码： A：0， C：10， B：110， D：111 。电文 ‘ABACCDA’ 便为 ‘0110010101110’（共 13 位）。
例：如果需传送的电文为 ‘ABCACCDAEAE’，即：A, B, C, D, E 的频率（即权值）分别为0.36, 0.1, 0.27, 0.1, 0.18，试构造哈夫曼编码。
编码： A：11，C：10，E：00，B：010，D：011 ，则电文 ‘ABCACCDAEAE’ 便为 ‘110101011101001111001100’（共 24 位，比 33 位短）。
电文为 “1101000” ，译文只能是“CAT”
哈夫曼算法的真正确性
其实想要简单了解和使用哈夫曼算法，看到前面已经可以了，博主由于复习算法设计分析，这里增加关于哈夫曼算法正确性的推理。
要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构。
1、贪心选择性质
2、最优子结构性质
