#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream.h>

#define N 6   //Huffman二叉樹的葉子結點數
#define M 2*N-1  //Huffman二叉樹的結點數
    
typedef struct HuffmanNode       //定義Huffman二叉樹的結點
{
	float weight;    //權重
    int parent, lchild, rchild; //該結點的雙親結點、左孩子、右孩子
} HuffmanTree[M+1];   //

typedef struct HuffmanCode
{
	char ch;   //存在字符
	char Bits[N+1];  //存放字符的Huffman編碼
}HCode[N+1];  //保存結點字符的Huffman編碼，HCode[0]作為哨兵

 /*在HT[1...i]中，選取序號分別為s1和s2的兩個權值最小的結點且其Parent=0*/
void Select(HuffmanTree HT, int n, int *s1, int *s2);

void CreatHT(HuffmanTree HT)  //根據葉節點的權值構造Huffman樹
{
	int i,s1,s2;
	for(i=N+1;i<=M;i++)
	{
		Select(HT, i, &s1, &s2);
		/*在HT[1...i]中，選取序號分別為s1和s2的兩個權值最小的結點且其Parent=0*/
   		HT[s1].parent = i; HT[s2].parent = i;
  		HT[i].lchild = s1; HT[i].rchild = s2;
   		HT[i].weight = HT[s1].weight + HT[s2].weight;
  	}
}

void HuffmanEncod(HCode HC)  //根據字符的權值進行Huffman編碼
{
  int i,j,p,start;
  HuffmanTree HT;
  char cd[N+1];
  for(i=1;i<=M;i++)
  {
	  HT[i].parent=0;
	  HT[i].lchild=0;
	  HT[i].rchild=0;
  }
  cout<<"請輸入"<<N<<"個字符及權值"<<endl;
  for(i=1;i<=N;i++)
  {
	  //scanf("%C,%f",HT[i].weight);  //讀入字符及其權值
	  cin>>HC[i].ch;
      cin>>HT[i].weight;
  }
  CreatHT(HT);
  cout<<endl;
  cout<<"Huffman編碼如下："<<endl;
  cout<<endl;
  cout<<"結點字符"<<"  "
	  <<"權重"<<"  "<<"Huffman編碼"<<endl;
  for(i=1;i<=N;i++)  //求Huffman編碼
  {
	  start=N;
	  cd[N]='\0';
	  p=HT[i].parent;
	  j=i;
	  while(p!=0)
	  {
		  if(HT[p].lchild==j)
		  {
			  cd[--start]='0';
		  }
		  else
		  {
			  cd[--start]='1';
		  }
		  j=p;
		  p=HT[p].parent;
	  }

	  strcpy(HC[i].Bits,&cd[start]) ; //復制Huffman編碼串聯
      cout<<HC[i].ch<<"           "
		  <<HT[i].weight<<"       "
		  <<HC[i].Bits<<endl;
  }
  cout<<endl;
  cout<<endl;
  cout<<"各結點的雙親結點，左右孩子如下："<<endl;
  cout<<endl;
  cout <<"結點編號"<<"   "
	  <<"雙親結點編號"<<"   "
	  <<"左孩子編號"<<"   "
      <<"右孩子編號"<<"   "<<"權重"<<"   "<<endl;
  for(i=1;i<=M;i++)
  { 
	  cout<<i<<"            "
		  <<HT[i].parent<<"               "<<HT[i].lchild<<"             "
		  <<HT[i].rchild<<"        "<<HT[i].weight<<endl;
  	}
 
}

 /*在HT[1...i]中，選取序號分別為s1和s2的兩個權值最小的結點且其Parent=0*/
void Select(HuffmanTree HT, int n, int *s1, int *s2) 
{
 
	int i,t,t1,t2;
    for( i=1; i<n; i++ )  //尋找第一個*s1
	{	
		if( HT[i].parent == 0 )
		{
			*s1=i;
			break;
		}
	}
	for( i=*s1+1; i<n; i++ ) //尋找第一個*s2
	{	
		if( HT[i].parent == 0 )
		{
			*s2=i;
			break;
		}
	}

	if(HT[*s1].weight < HT[*s2].weight)
	{
       t1=*s1;    //小
	   t2=*s2;    //大 
	}
	else
	{
       t1=*s2;
	   t2=*s1;
	}

    for( i=*s2+1; i<n; i++ )  //開始尋找s1和s2的兩個權值最小的結點且其Parent=0*/
	{
		if( HT[i].parent == 0 )
		{
			if( HT[i].weight < HT[t1].weight)
            {
				t2=t1;
			    t1=i;
			}
			else if( HT[i].weight < HT[t2].weight )
			{
				t2 = i;
			}
		}
	}

	*s1=t1;
	*s2=t2;
}