#include <iostream>
using namespace std;
#include <time.h>
#include <stdlib.h>
typedef struct {
char data;
int weight;
int left;
int right;
int parents;
int code;
}Huff;
void InitHuffman(Huff *,int);//初始化叶子
void CreatHuffmanTree(Huff *,int);//建树
void CreatHuffmanCode(Huff *,int); //编码
void TenToTwo(int n);
int main(void)
{
srand((unsigned)time(NULL));
int n=0;
//scanf("%d",&n);
n=rand()%10+1;
Huff *tree=(Huff *)malloc((2*n-1)*sizeof(Huff));
InitHuffman(tree,n);
CreatHuffmanTree(tree,n);
cout<<"输出哈夫曼表:"<<endl;
CreatHuffmanCode(tree,n);
for(int i=0;i<2*n-1;i++){
cout<<tree[i].data<<','<<tree[i].weight;
cout<<','<<tree[i].left<<','<<tree[i].right;
cout<<','<<tree[i].parents<<"code=";
if(i<2*n-2)TenToTwo(tree[i].code);
cout<<endl;
}
cout<<endl;
return 0;
}
void InitHuffman(Huff *tree,int n)
{
for(int i=0;i<n;i++){
tree[i].data=rand()%10+'A';
tree[i].left=tree[i].right=tree[i].parents=-1;
tree[i].weight=rand()%10;
tree[i].code=0;
}
}
void CreatHuffmanTree(Huff *tree,int n)
{
int k1=0,k2=0;
for(int i=0;i<n-1;i++){//有n个结点要找n-1次
for(k1=0;tree[k1].parents!=-1;k1++);
for(k2=k1+1;tree[k2].parents!=-1;k2++);
for(int j=k2;j<n+i;j++){
if(tree[j].parents==-1){
if(tree[j].weight<=tree[k1].weight){
k2=k1;
k1=j;
}else if (tree[j].weight<=tree[k2].weight){
k2=j;
}/*end if else*/
}/*end if j*/
}/*end for j*/
tree[k1].parents=tree[k2].parents=n+i;
tree[n+i].weight=tree[k1].weight+tree[k2].weight;
tree[n+i].data=0;
tree[n+i].left=k1;
tree[n+i].right=k2;
tree[n+i].parents=-1;
tree[k1].code=0;
tree[k2].code=1;
}/*end for i*/
}
void CreatHuffmanCode(Huff *tree,int n)
{
int StayCodeParents=0;
for(int i=0;i<n;i++){
StayCodeParents=tree[i].parents;
while(tree[StayCodeParents].parents!=-1){
tree[i].code=tree[i].code*2+tree[StayCodeParents].code;
StayCodeParents=tree[StayCodeParents].parents;
}
}
}
//十进制转二进制倒着输出
void TenToTwo(int n)
{
if(n){
cout<<n%2;
TenToTwo(n/2);
}else{
cout<<0;
}
}