# include <iostream.h>
# define n 4
# define m 2*n-1
# define M 100
typedef struct TreeNode
{
	int wi;
	char data;
	int parent,Lchild,Rchild;
}HTNode;
typedef struct code
{
	int string[n];
	int num;
	char data;
}HuffmanCode;
void select(HTNode HT[m+1])       
{
	int i,j,s1,s2,x1,x2;
	for(i=n+1;i<=m;i++)
	{
		x1=x2=0;
		s1=s2=M;
		for(j=1;j<=i-1;j++)
		{
			if(HT[j].parent==0)
			{
				if(HT[j].wi<s1)
				{
					s2 = s1;
					s1 = HT[j].wi;			     
					x2 = x1;
					x1 = j;
				}
				else if(HT[j].wi<s2)
				{
					s2 = HT[j].wi;              
					x2=j;
				}				
			}			
		}
		HT[x1].parent = HT[x2].parent = i;		
		HT[i].Lchild = x1;
		HT[i].Rchild = x2;
		HT[i].wi = HT[x1].wi + HT[x2].wi;
	}

}
void main(void)
{
	int i,j,p,s;
	HuffmanCode CD;
	HuffmanCode code[n+1];
	HTNode HT[m+1];
	for(i=1;i<=m;i++)          
	{
		HT[i].wi=HT[i].parent=HT[i].Lchild=HT[i].Rchild=0;
	}
	cout<<"代碼有4個(gè)"<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<"請(qǐng)輸入第"<<i<<"個(gè)字符:\t";
		cin>>HT[i].data;
		cout<<"請(qǐng)輸入該字符的權(quán)值:\t";
		cin>>HT[i].wi;
		cout<<"\n";
	}
		cout<<endl;
	select(HT);
	for(i=1;i<=n;i++)
	{
		code[i].data = HT[i].data;
	}
	cout<<"哈夫曼編碼"<<endl;
	for(i=1;i<=n;i++)
	{
		CD.data = code[i].data;
		CD.num = 0;
		s = i;
		p = HT[i].parent;
		while(p!=0)
		{
			CD.num++;
			if(HT[p].Lchild == s)
				CD.string[CD.num] =0;
			else
				CD.string[CD.num] =1;
			s = p; 
			p = HT[p].parent;
		
		}
		code[i] = CD;
		cout<<code[i].data<<"\t\t";
			for(j=1;j<=CD.num;j++)
			{
				cout<<code[i].string[j];
			}
			cout<<endl;
			
		}
}