#include<iostream.h>
#define FLOAT_MAX 1
const int n=3; //叶子结点数
const int m=2*n-1; //结点总数
typedef int datatype;
typedef struct{
char name[10];
float weight;
int parent,lchild,rchild;
}nodetype; //结点类型
typedef nodetype hftree[m]; //哈夫曼树类型
hftree T; //哈夫曼树向量
void huffman(hftree T)
{
int i,j,p1,p2;
float small1,small2;
for(i=0;i<n;i++)
{
T[i].parent=-1;
T[i].lchild=T[i].rchild=-1;
}
for(i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个节点的名字"<<endl;
cin>>T[i].name;
cout<<"请输入第"<<i+1<<"个节点的权"<<endl;
cin>>T[i].weight;
}
for(i=n;i<m;i++)
{p1=p2=-1;
small1=small2=FLOAT_MAX;
for(j=0;j<=i-1;j++)
{
if(T[j].parent!=-1) continue;
if(T[j].weight<small1)
{
small2=small1;
small1=T[j].weight;
p2=p1;
p1=j;
}
else if(T[j].weight<small2)
{small2=T[j].weight;
p2=j;
}
}
T[p1].parent=T[p2].parent=i;
T[i].parent=-1;
T[i].lchild=p1;
T[i].rchild=p2;
T[i].weight=small1+small2;
}
}
这是生成哈夫曼树的代码
#include<iostream>
using namespace std;
struct node
{
int w;
int flag;
int lchild,rchild;
int parent;
};
node huff[1001];
int n;
void read()
{
int i;
cout<<"输入n"<<endl;
cin>>n;
for(i=1;i<=n;i++)
cin>>huff[i].w;
}
int huffman()
{
int i,min1,min2,k1,k2,j,s;//初始化标记
for(i=1;i<=2*n-1;i++)
{
huff[i].flag=0;
huff[i].lchild=-1;
huff[i].rchild=-1;
huff[i].parent=-1;
}
//n-1次建树
for(i=1;i<=n-1;i++)
{
min1=100000;
min2=100000;//求最小初始化最大
k1=-1;// 记下最小次小的下标
k2=-1;
for(j=1;j<=n+i-1;j++)//搜索范围
{
if((huff[j].w<min1)&&(huff[j].flag==0))//比最小数还小
{
min2=min1;//最小给次小
k2=k1;//记下次小下标
min1=huff[j].w;//把最小赋值给min1
k1=j; //记下最小下标
}
else if((huff[j].w<min2)&&(huff[j].flag==0))
{
min2=huff[j].w;//直接修改次小值
k2=j;//记下次小的下标
}
}
huff[n+i].w=min1+min2;//新增加的结点
huff[k1].flag=1;//填最小与次小的标记：
huff[k2].flag=1;
huff[k1].parent=n+i;//填最小与次小的parent：
huff[k2].parent=n+i;
huff[n+i].lchild=k1;//填新增结点的左右孩子:
huff[n+i].rchild=k2;
}
s=0;//WPL的值为非叶子结点之和
for(i=n+1;i<=2*n-1;i++)
s=s+huff[i].w;
cout<<s<<endl;
return s;
}
void print(int t,string s1)
{
if ((huff[t].lchild==-1)&&(huff[t].rchild==-1))
cout<<huff[t].w<<"的编码为:"<<s1<<endl;
else
{
print(huff[t].lchild,s1+"0");
print(huff[t].rchild,s1+"1");
}
}
int main()
{
read();
huffman();
print(2*n-1,"");
}