转载请注明出处：http://blog.csdn.net/ns_code/article/details/19174553

Huffman Tree简介

赫夫曼树（Huffman Tree），又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,...,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,...,wn}，则所构造出的带权路径长度最小的二叉树就被称为赫夫曼树。

这里补充下树的带权路径长度的概念。树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和，如果在一棵二叉树中共有n个叶子节点，用Wi表示第i个叶子节点的权值，Li表示第i个也叶子节点到根节点的路径长度，则该二叉树的带权路径长度 WPL=W1*L1 + W2*L2 + ... Wn*Ln。

根据节点的个数以及权值的不同，赫夫曼树的形状也各不相同，赫夫曼树具有如下特性：

对于同一组权值，所能得到的赫夫曼树不一定是唯一的。赫夫曼树的左右子树可以互换，因为这并不影响树的带权路径长度。带权值的节点都是叶子节点，不带权值的节点都是某棵子二叉树的根节点。权值越大的节点越靠近赫夫曼树的根节点，权值越小的节点越远离赫夫曼树的根节点。赫夫曼树中只有叶子节点和度为2的节点，没有度为1的节点。一棵有n个叶子节点的赫夫曼树共有2n-1个节点。

Huffman Tree的构建

赫夫曼树的构建步骤如下： 1、将给定的n个权值看做n棵只有根节点（无左右孩子）的二叉树，组成一个集合HT，每棵树的权值为该节点的权值。 2、从集合HT中选出2棵权值最小的二叉树，组成一棵新的二叉树，其权值为这2棵二叉树的权值之和。 3、将步骤2中选出的2棵二叉树从集合HT中删去，同时将步骤2中新得到的二叉树加入到集合HT中。 4、重复步骤2和步骤3，直到集合HT中只含一棵树，这棵树便是赫夫曼树。
假如给定如下5个权值：

则按照以上步骤，可以构造出如下面左图所示的赫夫曼树，当然也可能构造出如下面右图所示的赫夫曼树，这并不是唯一的。

Huffman编码

赫夫曼树的应用十分广泛，比如众所周知的在通信电文中的应用。在等传送电文时，我们希望电文的总长尽可能短，因此可以对每个字符设计长度不等的编码，让电文中出现较多的字符采用尽可能短的编码。为了保证在译码时不出现歧义，我们可以采取如下图所示的编码方式：


即左分支编码为字符0，右分支编码为字符1，将从根节点到叶子节点的路径上分支字符组成的字符串作为叶子节点字符的编码，这便是赫夫曼编码。我们根据上面左图可以得到各叶子节点的赫夫曼编码如下：
权值为5的也自己节点的赫夫曼编码为：11 权值为4的也自己节点的赫夫曼编码为：10 权值为3的也自己节点的赫夫曼编码为：00 权值为2的也自己节点的赫夫曼编码为：011 权值为1的也自己节点的赫夫曼编码为：010
而对于上面右图，则可以得到各叶子节点的赫夫曼编码如下： 权值为5的也自己节点的赫夫曼编码为：00 权值为4的也自己节点的赫夫曼编码为：01 权值为3的也自己节点的赫夫曼编码为：10 权值为2的也自己节点的赫夫曼编码为：110 权值为1的也自己节点的赫夫曼编码为：111

Huffman编码的C实现

由于赫夫曼树中没有度为1的节点，则一棵具有n个叶子节点的的赫夫曼树共有2n-1个节点（最后一条特性），因此可以将这些节点存储在大小为2n-1的一维数组中。我们可以用以下数据结构来表示赫夫曼树和赫夫曼编码：

/*
赫夫曼树的存储结构，它也是一种二叉树结构，
这种存储结构既适合表示树，也适合表示森林。
*/
typedef struct Node
{
	int weight;                //权值
	int parent;                //父节点的序号，为0的是根节点
	int lchild,rchild;         //左右孩子节点的序号，为0的是叶子节点
}HTNode,*HuffmanTree;          //用来存储赫夫曼树中的所有节点
typedef char **HuffmanCode;    //用来存储每个叶子节点的赫夫曼编码

根据赫夫曼树的构建步骤，我们可以写出构建赫夫曼树的代码如下：

/*
根据给定的n个权值构造一棵赫夫曼树,wet中存放n个权值
*/
HuffmanTree create_HuffmanTree(int *wet,int n)
{
	//一棵有n个叶子节点的赫夫曼树共有2n-1个节点
	int total = 2*n-1;
	HuffmanTree HT = (HuffmanTree)malloc(total*sizeof(HTNode));
	if(!HT)
	{
		printf("HuffmanTree malloc faild!");
		exit(-1);
	}
	int i;

	//HT[0],HT[1]...HT[n-1]中存放需要编码的n个叶子节点
	for(i=0;i
  
       上述代码中调用到了select_minium（）函数，它表示从集合中选出两个最小的二叉树，代码如下：
   
/*
从HT数组的前k个元素中选出weight最小且parent为0的两个，分别将其序号保存在min1和min2中
*/
void select_minium(HuffmanTree HT,int k,int &min1,int &min2)
{
	min1 = min(HT,k);
	min2 = min(HT,k);
}
    这里调用到的min（）函数代码如下：
   
/*
从HT数组的前k个元素中选出weight最小且parent为0的元素，并将该元素的序号返回
*/
int min(HuffmanTree HT,int k)
{
	int i = 0;
	int min;        //用来存放weight最小且parent为0的元素的序号
	int min_weight; //用来存放weight最小且parent为0的元素的weight值

	//先将第一个parent为0的元素的weight值赋给min_weight,留作以后比较用。
	//注意，这里不能按照一般的做法，先直接将HT[0].weight赋给min_weight，
	//因为如果HT[0].weight的值比较小，那么在第一次构造二叉树时就会被选走，
	//而后续的每一轮选择最小权值构造二叉树的比较还是先用HT[0].weight的值来进行判断，
	//这样又会再次将其选走，从而产生逻辑上的错误。
	while(HT[i].parent != 0)
		i++;
	min_weight = HT[i].weight;
	min = i;

	//选出weight最小且parent为0的元素，并将其序号赋给min
	for(;i
    
         构建了赫夫曼树，便可以进行赫夫曼编码了，要求赫夫曼编码，就需要遍历出从根节点到叶子节点的路径，我们这里采用从叶子节点到根节点逆向遍历求每个字符的赫夫曼编码，代码如下：
     
/*
从叶子节点到根节点逆向求赫夫曼树HT中n个叶子节点的赫夫曼编码，并保存在HC中
*/
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{
	//用来保存指向每个赫夫曼编码串的指针
	HC = (HuffmanCode)malloc(n*sizeof(char *));