哈夫曼编码可能不唯一。
输入：
第1行：n
接下来n行，每行两数据，字符和一个整数（表示出现频率）
输出：
n行，每行包含一个字符和其相应编码
参考程序：
参考程序
#include<iostream>
#include<algorithm>
#include<iterator>
#include<string>
#include<map>
using namespace std;
struct node{
char ch;
int data;
node *lch,*rch;
friend bool operator < (node x,node y)
{
return x.data>y.data;
}
friend bool operator > (node x,node y)
{
return x.data<y.data;
}
};
const int N = 100;
node h[N],tmp[2*N];
map<char,string> m;
void create(int n) //创建哈夫曼树
{
make_heap(h+1,h+n+1); //先调整成堆
for (int k=1,i=n,j=0;k<n;k++)
{
pop_heap(h+1,h+i+1); //将堆头放到最后
pop_heap(h+1,h+i); //将堆头放到最后
tmp[++j]=h[i]; tmp[++j]=h[i-1];
h[i-1].data+=h[i].data;
h[i-1].lch=tmp+j-1;
h[i-1].rch=tmp+j;
push_heap(h+1,h+i);
i--;
}
}
void visit(node *root,string s)
{
if (root->lch==NULL){
m[root->ch]=s;
return ;
}
visit(root->lch,s+'0');
visit(root->rch,s+'1');
}
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
{
//h[i]=new(node);
cin>>h[i].ch>>h[i].data;
h[i].lch=h[i].rch=NULL;
}
create(n);
visit(h+1,"");
map<char ,string>::iterator it;
for (it=m.begin();it!=m.end();it++)
cout<<(*it).first<<" "<<(*it).second<<endl;
return 0;
}样例输入：
6
A 26
B 10
C 12
D 16
E 28
F 8
样例输出：
A 01
B 001
C 100
D 101
E 11
F 000
posted on 2014-03-06 12:00
龙在江湖 阅读(158)
评论(0) 编辑 收藏 引用 所属分类:
二叉树