VC++2012编程演练数据结构《24》哈夫曼树

大灰狼

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。
哈夫曼树又称为最优树.
　　1、路径和路径长度　　
在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
　　2、结点的权及带权路径长度
　　若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
　　3、树的带权路径长度
　　树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
哈夫曼树的构造
　  哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
　　(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
　　(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
　　(3)从森林中删除选取的两棵树，并将新树加入森林；
　　(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
哈夫曼编码
　　在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
　　为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
　　哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。

　　哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。

打开IDE

     我们来创建一个工程

哈夫曼树类实现

[cpp] view plaincopy

• #include "stdafx.h"  
•   
• //哈夫曼树与哈夫曼编码  
• using namespace std;  
• #include<iostream>  
• #include<iomanip>  
• #include<stdlib.h>  
• const int MaxV=1000;//初始设定的最大权值  
• const int MaxBit=10;//初始设定的最大编码位数  
• const int MaxN=10;//初始设定的最大结点数  
• //哈夫曼树的结点结构  
• typedef struct  
•   {int weight;//权值  
•    int flag;  //标记  
•    int parent;//双亲结点下标  
•    int left;//左孩子下标  
•    int right;//右孩子下标  
•   }HuffNode;  
•   typedef struct  
•   {int bit[MaxN];//存放编码数组  
•    int start;//编码的起始下标  
•    int weight;//字符的权值  
•   }Code;  
• //类定义  
• class HuffmanT  
• {public:  
•   //构造函数  
•   HuffmanT(HuffNode *&,Code *&,int);  
•   //创建叶结点个数为n,权值数组为weight的哈夫曼树HuffTree  
•   void MakeHufm(int weight[],int n);  
•   //由n个结点的哈夫曼树HuffTree构造哈夫曼编码huffCode  
•   void HuffCode(int n);  
• private:  
•   HuffNode *HuffTree;  
•   Code *huffCode;  
• };  
• HuffmanT::HuffmanT(HuffNode *&huffnode,Code *&huCode,int n)  
• {huffnode=new HuffNode[2*n+1];  
• huCode=new Code[n];  
• HuffTree=huffnode;  
• huffCode=huCode;  
• }  
• void HuffmanT::MakeHufm(int weight[],int n)  
• {int j,m1,m2,x1,x2,i;  
• //哈夫曼树HuffTree的初始化  
• for(i=0;i<2*n-1;i++)  
• {if(i<n) HuffTree.weight=weight;  
•   else HuffTree.weight=0;  
•   HuffTree.parent=0;  
•   HuffTree.flag=0;  
•   HuffTree.left=-1;  
•   HuffTree.right=-1;  
• }  
• //构造哈夫曼树HuffTree的n-1个非叶结点  
• for(i=0;i<n-1;i++)  
• {m1=m2=MaxV;  
•   x1=x2=0;  
•   for(j=0;j<n+i;j++)  
•   {if(HuffTree[j].weight<m1&&HuffTree[j].flag==0)  
•     {m2=m1;  
•      x2=x1;  
•      m1=HuffTree[j].weight;  
•      x1=j;  
•     }  
•    else if(HuffTree[j].weight<m2&&HuffTree[j].flag==0)  
•     {m2=HuffTree[j].weight;  
•      x2=j;  
•     }  
•   }  
•   //将找出的两棵权值最小的子树合并为一棵子树  
•   HuffTree[x1].parent=n+i;  
•   HuffTree[x2].parent=n+i;  
•   HuffTree[x1].flag=1;  
•   HuffTree[x2].flag=1;  
•   HuffTree[n+i].weight=HuffTree[x1].weight+HuffTree[x2].weight;  
•   HuffTree[n+i].left=x1;  
•   HuffTree[n+i].right=x2;  
• }  
• }  
• void HuffmanT::HuffCode(int n)  
• {Code *cd=new Code;  
• int child,parent;  
• //求n个叶结点的哈夫曼编码  
• for(int i=0;i<n;i++)  
• {cd->start=n-1;//不等长编码的最后一位为n-1  
•   cd->weight=HuffTree.weight;//取得编码对应权值的字符  
•   child=i;  
•   parent=HuffTree[child].parent;  
•   //由叶结点向上直到根结点  
•   while(parent!=0)  
•   {if(HuffTree[parent].left==child)  
•     cd->bit[cd->start]=0;//左孩子结点编码0  
•    else  
•     cd->bit[cd->start]=1;//右孩子结点编码1  
•    cd->start--;  
•    child=parent;  
•    parent=HuffTree[child].parent;  
•   }  
•   //保存每个叶结点的编码和不等长编码的起始位  
•   for(int j=cd->start+1;j<n;j++)  
•    huffCode.bit[j]=cd->bit[j];  
•   huffCode.start=cd->start;  
•   huffCode.weight=cd->weight;//记住编码对应权值的字符  
• }  
• }  
  

哈夫曼树类调用

[cpp] view plaincopy

• //哈夫曼编码问题的测试  
• void main()  
• {cout<<"运行结果:\n";  
• int i,j,n=4;  
• int weight[]={1,3,5,7};  
• HuffNode *myHuffTree;  
• Code *myHuffCode;  
• HuffmanT t(myHuffTree,myHuffCode,n);  
• if(n>MaxN)  
• {cout<<"n越界,修改MaxN!\n";exit(1);}  
• t.MakeHufm(weight,n);  
• t.HuffCode(n);  
• //输出每个叶结点的哈夫曼编码  
• for(i=0;i<n;i++)  
• {cout<<"weight="<<myHuffCode.weight<<"  Code=";  
•   for(j=myHuffCode.start+1;j<n;j++)  
•    cout<<myHuffCode.bit[j];  
•   cout<<endl;  
• }  
• cin.get();  
• }  
  

效果如下