# include <iostream.h>
# define n 5
# define m 2*n-1
# define max 1000
//哈夫曼樹型結構//
typedef struct
{
	int wi;
	char data;
	int parent,Lchild,Rchild;
}huffm;
//哈夫曼編碼結構//
typedef struct
{
	int bits[n];
	int number;
	char data;
}Hcode;


//-------哈夫曼樹---------//
void huffmTree(huffm HT[m+1])       
{
	
	int i,j,w,s1,s2,p1,p2;
	for(i=1;i<=m;i++)        //初始化哈夫曼樹//   
	{
		HT[i].wi=0;
		HT[i].parent=0;
		HT[i].Lchild=0;
		HT[i].Rchild=0;
	}
	for(i=1;i<=n;i++)
	{
		cout<<"請輸入第"<<i<<"個字符:\t";
		cin>>HT[i].data;
		cout<<"請輸入該字符的權值:\t";
		cin>>w;
		HT[i].wi=w;
		cout<<"\n";
	}
		cout<<endl;
	//找出最小值//
	for(i=n+1;i<=m;i++)
	{
		p1=p2=0;
		s1=s2=max;
		for(j=1;j<=i-1;j++)
		{
			if(HT[j].parent==0)
			{
				if(HT[j].wi<s1)
				{
					s2 = s1;
					s1 = HT[j].wi;			     //此時j結點是第一個最小值
					p2 = p1;
					p1 = j;
				}
				else if(HT[j].wi<s2)
				{
					s2 = HT[j].wi;              //此時j結點是第二個最小值
					p2=j;
				}				
			}			
		}
		HT[p1].parent = HT[p2].parent = i;		//構造新樹//
		HT[i].Lchild = p1;
		HT[i].Rchild = p2;
		HT[i].wi = HT[p1].wi + HT[p2].wi;
	}
	for(i=1;i<=m;i++)
	{
		cout<<"哈夫曼樹的權是:"<<HT[i].wi<<endl;
	}
	cout<<endl;
}
//---------哈夫曼編碼--------//
void HuffmCode()
{
	
	int i,j,p,s;
	huffm HT[m+1];
	Hcode cd;
	Hcode code[n+1];
	huffmTree(HT);
	for(i=1;i<=n;i++)
	{
		code[i].data = HT[i].data;
	}
	cout<<"字符\t"<<"哈夫曼權值\t"<<"哈夫曼編碼"<<endl;
	for(i=1;i<=n;i++)
	{
		cd.data = code[i].data;
		cd.number = 0;
		s = i;
		p = HT[i].parent;
		while(p!=0)
		{
			cd.number++;
			if(HT[p].Lchild == s)
				cd.bits[cd.number] =0;
			else
				cd.bits[cd.number] =1;
			s = p; 
			p = HT[p].parent;
		
		}
		code[i] = cd;
		cout<<code[i].data<<"\t"<<HT[i].wi<<"\t\t";
			for(j=1;j<=cd.number;j++)
			{
				cout<<code[i].bits[j];
			}
			cout<<endl;
			
		}
}
//主函數//

void main(void)
{
	cout<<"//******************************//"<<endl;
	cout<<"               哈夫曼樹           "<<endl;
	cout<<"             楊忠 20028717        "<<endl;
	cout<<"//******************************//"<<endl;
	cout<<"如果哈夫曼樹的結點為5個\n"<<endl;
	HuffmCode();
}