#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>
char *Info; //节点信息
int LeafNum; //树叶数
typedef struct HuffmanNode //定义哈夫曼树各结点
{
int weight; //频率
int parent; //双亲编号
int lchild,rchild; //左右孩子编号
}HuffmanNode;
HuffmanNode *Node;
void HuffmanTree() //哈夫曼树初始化
{
Node=NULL; //将树结点初始化为空
Info=NULL; //将字符数组初始化为空
LeafNum=0; //将叶子数初始化为0
}
void Initialization(int WeightNum) //建立哈夫曼编码树
{
int i,j,pos1,pos2,max1,max2;
Node=new HuffmanNode[2*WeightNum-1];
Info=new char[2*WeightNum-1];
for(i=0;i<WeightNum;i++)
{
cout<<"请输入第"<<i+1<<"个字符值"<<endl;
Info[i]=getchar(); //记录字符值,包括空格
getchar(); //去掉'/n'
cout<<"请输入该字符的权值或频度"<<endl;
cin>>Node[i].weight; //输入权值
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}
for(i=WeightNum;i<2*WeightNum-1;i++) //表示需做WeightNum-1次合并
{
pos1=-1; //最小值的单元编号
pos2=-1; //次小值的单元编号
max1=32767; //最小值
max2=32767; //次小值
for(j=0;j<i;j++) //在跟节点中选出权值最小的两个
if(Node[j].parent==-1) //是否为根结点
if(Node[j].weight<max1) //是否比最小值要小
{
max2=max1; //原最小值变为次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在单元编号
pos1=j; //修改最小值所在单元编号
}
else
if(Node[j].weight<max2) //比原最小值大但比原次小值要小
{
max2=Node[j].weight; //存放次小值
pos2=j; //修改次小值所在的单元编号
}
Node[pos1].parent=i; //修改父亲位置
Node[pos2].parent=i;
Node[i].lchild=pos1; //修改左儿子位置