1、二叉树的应用－哈夫曼树（电文的编码和译码）哈夫曼编码/译码器问题描述：设计一个哈夫曼编码/译码系统，对字符串进行编码/译码基本要求：（1）从键盘输入字符串，以回车结束

Question

1、二叉树的应用－哈夫曼树（电文的编码和译码）
哈夫曼编码/译码器
问题描述：设计一个哈夫曼编码/译码系统，对字符串进行编码/译码
基本要求：
（1）从键盘输入字符串，以回车结束；
（2）根据字符串中字符出现的概率进行哈夫曼编码；）
（3）并输出编码结果和编码表；
（4）根据编码结果和编码表还原字符串；
（5）输出编码过程中构造的哈夫曼树。

Answer 1

#include
#include
int n;
int m=2*n-1;

struct tree
{
float weight;
int parent;
int lch,rch;
};
struct codetype
{
int bits[100];
int start;
char ch;
};
tree hftree[100];
codetype code[99];
void creathuffmantree(int n,int m)
{

int i,j ,p1,p2;
float s1,s2;
for(i=1;i<=m;i++)
{hftree[i].parent=0;
hftree[i].lch=0;
hftree[i].rch=0;
hftree[i].weight=0;
}
cout<for(i=1;i<=n;i++)
cin>>hftree[i].weight;
for(i=n+1;i<=m;i++)
{ p1=p2=0;
s1=s2=32767;
for(j=1;j<=i-1;j++)
if (hftree[j].parent==0)
if (hftree[j].weight{s2=s1;s1=hftree[j].weight;
p2=p1;p1=j;
}
else
if (hftree[j].weight{s2=hftree[j].weight;p2=j;
}
hftree[p1].parent=i;
hftree[p2].parent=i;
hftree[i].lch=p1;
hftree[i].rch=p2;
hftree[i].weight=hftree[p1].weight+hftree[p2].weight;
}
}
void huffcode(int n,int m)
{

codetype cd;
int c,p;
for(int i=1;i<=n;i++)
{
cd.start=n+1;
cd.ch=96+i;
c=i;
p=hftree[i].parent;
while(p!=0)
{ cd.start--;
if(hftree[p].lch==c) cd.bits[cd.start]=0;
else cd.bits[cd.start]=1;
c=p;
p=hftree[p].parent;
}
code[i]=cd;
}
for(i=1;i<=n;i++)
{ cout< for(int j=code[i].start;j<=n;j++)
cout< cout< }
}
void trancode(int n,int m)
{
int i=m;char b;
cout< cin>>b;
while ((b=='0')||(b=='1'))
{ if (b=='0') i=hftree[i].lch;
else i=hftree[i].rch;
if (hftree[i].lch==0)
{ cout< i=m;
}
cin>>b;
}
}
void main()
{
cout< cin>>n;
creathuffmantree(int (n),int (m));
huffcode(int (n),int (m));
trancode(int (n),int (m));
}