Huffman树及Huffman编码
一．实验目的
掌握哈夫曼树的构造算法、哈夫曼编码原理。
二．实验要求与内容
假设用于通信的电文仅由7个字母(A,B,C,D,E,F,G)组成，字母在电文中出现的次数分别为 4，15，17，6，9，31，27且按字母顺序依次存储。试构造哈夫曼树并为这7个字母设计哈夫曼编码。约定：在构造哈夫曼树时，权值小的为左子树节点，权值大的为右子树节点；哈夫曼编码左子树分支编码为0，右子树分支编码为1。
编程实现构造huffman树以及huffman编码。
算法参见课本P202
三．实验步骤
1．数据结构
数据结构定义、分析、设计等
定义哈夫曼树的结点，结点记录该结点的父结点的下标，左子树的下标，右子树的下标以及本身的权值。哈夫曼树构造：取最小的权值作为哈夫曼树的左右子树，并将最小两个权值相加作为新的结点的权值，该新结点为最小两个结点的父结点，最小两个结点分别为该新结点的左右子树。哈夫曼树编码：对于每个结点进行父结点的遍历，，直至父结点为0，利用字符串记录结点是其父结点的左子树还是右子树，左子树s=“0”+s;右子树s=“1”+s;
2．算法设计
该哈夫曼树从下往上构建，最小的两个结点分别为最低层的左右子树，将最小的两个权值相加作为新结点的权值，新结点的左右子树为这两个权值最小的结点，该新结点为这两个结点的父结点，再找这些结点的最小两个结点，相加作为新的权值，标记成子结点的左右子树，新结点标记成这两个结点的父结点，重复这些动作直至只剩下最后新构造好的结点为止。
哈夫曼树编码则是遍历结点的父结点，如果该结点是其父结点的左子树则字符串s=“0”+s否则s=“1”+s;继续寻找该父结点的父结点，判断，，重复动作直至该结点的父结点为0为值。
哈夫曼树的最小WPS值也可以用最优队列进行计算。
具体解析看代码注释
3．程序
//方法二：每次找到最小的两个数作为左右子树，将他们相加构成新的结点，该新结点为这两个最小结点的父结点，最小两个结点分别为该结点的左右结点，
//该结点的权值为两个结点的权值的和，将权值累计即为该数的最小WPL
```
for(i=N;i<M;i++){
int l=mini();//先求左边，再求右边能确保左边小于右边
int r=mini();
HT[l].parent=i;//左右结点的父结点为第i个
HT[r].parent=i;
HT[i].left=l;//设置第i个的左右结点
HT[i].right=r;
HT[i].weight=HT[l].weight+HT[r].weight;
s=s+HT[i].weight;
weight[i]=HT[i].weight;
}
//编码：求前N-1个结点的是该结点的父结点的左边还是右边，重复该查找动作直至结点的父结点为0为止。
void huffmannodecode(){
struct huffmannode p;
for(int i=0;i<N;i++){
string s="";//用字符串的形式记录编码
p=HT[i];
int m=i;//m记录它的上一父结点
int c=p.parent;//用c记录它的父结点
p=HT[c];
while(c!=0){
if(p.left==m)//如果上一父结点是结点的左孩子则记录为0否则为1；
s="0"+s;
else
s="1"+s;
m=c;
c=p.parent;
p=HT[c];
}
cout<<s<<endl;
}
}
4．程序调试
四．结果与体会
在哈夫曼树的编码中求最小WPL时可以用累加法代替乘法。在记录哈夫曼树编码的时候可以用字符串的形式记录。
五．源程序
另附
#include<iostream>
#include<queue>
#define N 7
#define M N*2-1
using namespace std;
int weight[]={4,15,17,6,9,31,27,0,0,0,0,0,0};
priority_queue<int,vector<int>,greater<int>>q;
struct huffmannode{
int parent;
int left;
int right;
int weight;
}HT[M];
void init(int weight[]){
for(int i=0;i<M;i++){
HT[i].parent=0;
HT[i].left=0;
HT[i].right=0;
HT[i].weight=weight[i];
}
}
//编码：求前N-1个结点的是该结点的父结点的左边还是右边，重复该查找动作直至结点的父结点为0为止。
void huffmannodecode(){
struct huffmannode p;
for(int i=0;i<N;i++){
string s="";//用字符串的形式记录编码
p=HT[i];
int m=i;//m记录它的上一父结点
int c=p.parent;//用c记录它的父结点
p=HT[c];
while(c!=0){
if(p.left==m)//如果上一父结点是结点的左孩子则记录为0否则为1；
s="0"+s;
else
s="1"+s;
m=c;
c=p.parent;
p=HT[c];
}
cout<<s<<endl;
}
}
//求最小值
int mini(){
int mi=999;
int k=-1;
for(int i=0;i<M;i++){
if(weight[i]< mi && weight[i]!=0){
mi=weight[i];
k=i;
}
}
weight[k]=999;
return k;
}
int main(){
int s=0;
int i,ans=0;
init(weight);
for(int i=0;i<N;i++)
{
q.push(weight[i]);
}
//两种方式求权值 方法一：利用优先队列，取队列的头相加作为新的加入队列，累加值。
while(q.size()>1){
int x=q.top();
q.pop();
int y=q.top();
q.pop();
q.push(x+y);
ans+=x+y;
}
//方法二：每次找到最小的两个数作为左右子树，将他们相加构成新的结点，该新结点为这两个最小结点的父结点，最小两个结点分别为该结点的左右结点，
//该结点的权值为两个结点的权值的和，将权值累计即为该数的最小WPL
for(i=N;i<M;i++){
int l=mini();//先求左边，再求右边能确保左边小于右边
int r=mini();
HT[l].parent=i;//左右结点的父结点为第i个
HT[r].parent=i;
HT[i].left=l;//设置第i个的左右结点
HT[i].right=r;
HT[i].weight=HT[l].weight+HT[r].weight;
s=s+HT[i].weight;
weight[i]=HT[i].weight;
}
for (i=0;i<M;i++)
printf("%d %d %d %d\n",HT[i].weight,HT[i].parent,HT[i].left,HT[i].right);
printf("\n");
huffmannodecode();
cout<<"最小WPL"<<ans<<endl;
cout<<"最小WPL"<<s<<endl;
}
```
