哈夫曼树C语言实现

#include
#include
#include
#include
#define Max 32767 //int 型最大可取值
typedef struct Node{
int weight;
int parent,Lchild,Rchild;
}HTNode;
typedef char *HuffmanCode;

void select(int w[],int n,int &xb1,int &xb2){ //select(w,i-1,xb1,xb2);
int min1,min2; //min1最小，min2次小

min1=w[1];xb1=1;
min2=w[2];xb2=2;
if(min1>min2){
min1=w[2];xb1=2;
min2=w[1];xb2=1; //安排第一和第二个数的显示顺序
}
for(int i=3;i<=n;i++){//n=7 遍历>2的数组元素
if(w[i]min2=min1;xb2=xb1; //第一次遍历，下标为6和7的3，2显示，其中2为最小，3为次小，故先显示xb1 2--7
//然后是xb2 3--6
min1=w[i]; xb1=i;
}
else if(w[i]min2=w[i];
xb2=i; //安排次小的在前
}

}
cout<<"权值 下标"<cout<cout<cout<<"--------------"<
}

void createHTree(HTNode ht[],HuffmanCode hc[],int w[],int n){
int start;
int m=2*n-1;

for(int i=1;i<=n;i++){
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].Rchild=0;//初始化原有数据成员，都赋值为0
ht[i].Lchild=0;
}
for(i=n+1;i<=m;i++){
ht[i].weight=0;
ht[i].parent=0;
ht[i].Rchild=0;
ht[i].Lchild=0;//初始化权值相加的成员
}

int xb1,xb2;
cout<<"依次被选中的节点值"<for(i=n+1;i<=m;i++){
select(w,i-1,xb1,xb2);//（数据成员，遍历参数，下标1，下标2）
ht[xb1].parent=i; //第一次遍历双亲为8
ht[xb2].parent=i;
ht[i].Lchild=xb1; //一道初始化此双亲的孩子节点
ht[i].Rchild=xb2; //要保证下标小的作左孩子，还需加一句判断语句
w[i]=w[xb1]+w[xb2]; //双亲=左右孩子节点权值相加
ht[i].weight=w[i];
if(xb1>xb2){//保证 下标小 的做左孩子
ht[i].Lchild=xb2;
ht[i].Rchild=xb1;
}
w[xb1]=Max;
w[xb2]=Max; //修改选过的节点的权值，避免下次再被选中
}

//输出所有节点的下标、权值、双亲、左孩子、右孩子的下标
cout<for(i=1;i<=13;i++)
cout<
char *cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0'; //这里限制哈夫曼编码写入到cd[5]就结束了
for(i=1;i<=n;i++){
start=n-1;
for(int c=i,p=ht[i].parent;p!=0;c=p,p=ht[p].parent)
if(ht[p].Lchild==c) //左孩子下标是否为数据成员下标1，2，3，4，5，6，7
cd[--start]='0'; //i=1时，编码cd[6]='0'，然

后分别为i=2时 cd[5]='0'.........
else cd[--start]='1';
hc[i]=(char *)malloc(sizeof(char));//hc[i]只是一个指针，指针指向的空间还没有分配，所以此时用strcpy向str1所指向的内存
//中拷贝内容将出错。利用malloc动态分配指向的内存（在堆中）
strcpy(hc[i],&cd[start]);
}
free(cd);
}

void main(){


int w[14]={0,40,30,16,5,4,3,2};
int n=7;
int m=2*n-1;
HTNode ht[14];//哈夫曼树成员数组 从1---13； 0 下标不用。用于双亲表示法存储Huffman树
HuffmanCode hc[8];//7个叶子节点也就是w[14]里面的，从1-7； 0下标不用 其中HuffmanCode被自定义为char型指针数据类型
createHTree(ht,hc,w,n);
cout<for(int i=1;i<=n;i++){
cout<}
}