哈夫曼树及哈弗曼编码

哈姆曼树的构建：

赫夫曼树的外结点和内结点的区别：外节点是携带了关键数据的结点， 而内部结点没有携带这种数据， 只作为导向最终的外结点所走的路径而使用，所以，我们主要关心的是赫夫曼树的外结点上， 而不是内结点。

我们为扩充二叉树的外结点（叶子结点）定义两条属性： 权值（w）和路径长度(l)。同时规定带权路径长度（WPL）为扩充二叉树的外结点的权值和路径长度乘积之和：

路径长度：

路径长度指的是路径上分支的数目。

节点的权：

节点的权指的是为树中的每一个节点赋予的一个非负的值，如上图中每一个节点中的值。

节点的带权路径长度：

节点的带权路径长度指的是从根节点到该节点之间的路径长度与该节点权的乘积。

树的带权路径长度：

树的带权路径长度指的是所有叶子节点的带权路径长度之和。

由n个权值构造一颗有n个叶子结点的二叉树， 则其中带权路径长度WPL最小的二叉树， 就是赫夫曼树，或者叫做最优二叉树。

构建过程分四步：

• 根据给定的n个权值{w1, w2, w3 … wn }构成n棵二叉树的集合， 每棵二叉树都只包含一个结点
• 在上面的二叉树中选出两颗根结点权值最小的树， 同时另外取一个新的结点作为这两颗树的根结点， 设新节点的权值为两颗权值最小的树的权值和， 将得到的这颗树也加入到树的集合中
• 在2操作后， 从集合中删除权值最小的那两颗树
• 重复2和3，直到集合中的树只剩下一棵为止， 剩下的这颗树就是我们要求得的赫夫曼树。

对于同一组权值的叶结点， 构成的赫夫曼树可以有多种形态， 但是最小WPL值是唯一的。

哈弗曼编码：

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）

哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。若能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

根据Huffman树的结构，我们可以利用Huffman树对每一个字符编码，Huffman编码是一种前缀编码，即一个字符的编码不是另一个字符编码的前缀。规定如下：

• 将权值小的最为左节点，权值大的作为右节点
• 左孩子编码为0，右孩子编码为1

代码如下：

#include<stdio.h>
#include<string.h>
#define MAX 100000


//-----哈夫曼树的存储表示-----
typedef struct
{
	int weight;//结点的权值 
	int parent,lchild,rchild;//结点的双亲，左孩子，右孩子 
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 

void Select(HuffmanTree &HT,int m,int &s1,int &s2)
{
        int m1,m2;
		m1=m2=MAX;//m1、m2中存放两个无父结点且结点权值最小的两个结点 
        s1=s2=1;
        //找出两个其双亲域为0且权值最小的两个结点，返回他们在HT中的序号s1和s2 
        for (int j=1; j<=m; j++)
        {
            if (HT[j].weight < m1 && HT[j].parent==0)//如果说这个值比m1要小，则将其赋值给m1 
            {
                m2=m1; //找到比m1小的数，将m1的值（对应权值）给m2 
                s2=s1; // 对应序号赋值给m2 
                m1=HT[j].weight;
                s1=j; 
            }
            /*这里讲究的是m1和m2谁先比较的顺序 ，这里比较完了 m1之后，m1已经找到比他小的值之后才会把自己原来
			的值赋给m2，然后继续比较,不小于m1了，再看是否比m2要小，即次小数*/ 
            else if (HT[j].weight < m2 && HT[j].parent==0)//如果不比m1小，看他是否比m2小，找出次小数 
            {
                m2=HT[j].weight;
                s2=j;
            }
        } 
}

//--------构建哈夫曼树--------- 
void CreatHuffmanTree(HuffmanTree &HT,int n)
{
	//构造哈夫曼树
	int m,i,s1,s2;
	if(n<=1) return;
	m=2*n-1;
	HT=new HTNode[m+1];//0单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点 
	for(i=1;i<=m;i++)//将1-m号单元中的双亲，左孩子，右孩子的下标都初始化为0 
	{
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	 } 
	for(i=1;i<=n;i++)//输入前n个单元中叶子结点的值 
	{
		printf("请输入第%d个叶子结点的权值：\n",i);
		scanf("%d",&HT[i].weight);
	 } 	
//--------初始化工作结束，下面开始创建哈夫曼树----------
    for(i=n+1;i<=m;i++)
	{
        //通过n-1次选择，删除，合并来创建哈夫曼树 
        //在HT[K](1<=K<=I-1)中选择两个其双亲域为0且权值最小的节点 ，并返回他们在HT中的序号s1和s2
		Select(HT,i-1,s1,s2);
        //得到新节点i,从森林中删除s1,s2,将s1,s2的双亲由0改成i
	    HT[s1].parent=i;
		HT[s2].parent=i;
       // s1,s2分别作为i的左右孩子
		HT[i].lchild=s1;
		HT[i].rchild =s2;
		//i的权值为左右孩子的权值之和  
		HT[i].weight=HT[s1].weight+HT[s2].weight;			
	 } 
	 printf("\n------------------------------------------------------------------------\n"); 
	 printf("结点\t\t权值\t\tparent\t\tlchild\t\trchild");
	 printf("\n");
	 for(i=1;i<=m;i++)
	 {
	 	printf("%d\t\t%d\t\t%d\t\t%d\t\t%d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);	
        printf("\n");
	 }
        
} 
 
 //------哈夫曼编码表的存储表示-----
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
HuffmanCode HC;
 
 
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
 {
 	//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
 	 int i;
 	 char *cd;
	 HC=new char *[n+1];//分配存储n个字符编码的编码表空间 
	 cd=new char[n];//分配临时存储每个字符编码的编码表空间 
	 cd[n-1]='\0';//编码结束符
	
	 for(i=1;i<=n;++i)//逐个字符求解n个字符编码 
	 {
	 	int start=n-1;//start开始时指向最后,即编码结束符位置 
	 	int c=i;int f=HT[i].parent;//f指向结点c的双亲结点 
	 	while(f!=0)//从叶子结点开始向上回溯直至根结点 
	 	{
	 		--start;//回溯一次start向前指一个位置 
	 		if(HT[f].lchild==c) cd[start]='0';//结点c是f的左孩子，则生成代码0 
	 		else cd[start]='1';//结点c是f的右孩子，则生成代码1
	 		c=f;f=HT[c].parent;	//继续向上回溯 		
		 }//求出第i个字符的编码 
		 HC[i]=new char[n-start];//为第i个字符编码分配空间  
		 strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中 
	  }
	 delete cd;//释放临时空间
	 printf("\n\n");
	 printf("结点\t\t权值\t\t编码");
	 printf("\n");
     for(i=1;i<=n;i++)
     {
     	printf("%d\t\t%d\t\t%s",i,HT[i].weight,HC[i]); 
     	printf("\n"); 
	 }

 }
 
  
main()
{
	  int n;
	  HuffmanTree HT;
      printf("请输入初始叶子结点的数目：\n");
	  scanf("%d",&n);
      CreatHuffmanTree(HT,n);
      CreatHuffmanCode(HT,HC,n);
}