#include<stdio.h> 
#include<malloc.h>
#include <string.h>
typedef struct HTNode
{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
int n;
HuffmanTree HT;	
HuffmanCode HC;

void HuffmanCoding()
{		
	HuffmanTree p;
	int m,i,j,c,f,start;
	int s1,s2,w1,w2;
	char *cd;	
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(struct HTNode));
	for(p=HT+1,i=1;i<=m;++i,++p)
	{
		p->weight=0;
		p->parent=p->lchild=p->rchild=0;
	}
	printf("請輸入這%d個權值:\n",n);
	for(i=1;i<=n;i++)
		scanf("%d",&HT[i].weight);
	for(i=n+1;i<=m;++i)
	{
		s1=s2=-1;
		w1=w2=100;
		for(j=1;j<=i-1;++j)
			if(HT[j].parent==0)
				if(HT[j].weight<w1)
				{
					w2=w1;
					w1=HT[j].weight;
					s2=s1; s1=j;
				}
				else if(HT[j].weight<w2)
				{
					w2=HT[j].weight;
					s2=j;
				}
				HT[s1].parent=i; HT[s2].parent=i;
		        HT[i].lchild=s1; HT[s2].rchild=s2;
		        HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd=(char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for(i=1;i<=n;++i)
	{
		start=n-1;
		for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)
			if(HT[f].lchild==c)
				cd[--start]='0';
			else cd[--start]='1';
		HC[i]=(char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
	}
	free(cd);
	printf("哈夫曼編碼為：\n");
	for(i=1;i<=n;i++)
		printf("\n%2d : %s",HT[i].weight,HC[i]);
}

void main()
{	
	printf("共有多少個權值？\n");
	scanf("%d",&n);
	HuffmanCoding();
	getchar();
	getchar();
}