/*文件Haffman.h*/
typedef struct
{	
	int weight;			/*權值*/
	int flag;			/*標記*/
	int parent;			/*雙親結點下標*/
	int leftChild;		/*左孩子下標*/
	int rightChild;		/*右孩子下標*/
}HaffNode;				/*哈夫曼樹的結點結構*/

typedef struct
{
	int bit[MaxN];		/*數組*/
	int start;			/*編碼的起始下標*/
	int weight;			/*字符的權值*/
}Code;					/*哈夫曼編碼的結構*/

void Haffman(int weight[],int n,HaffNode haffTree[])
/*建立葉結點個數為n、權值數組為weight的哈夫曼樹haffTree*/
{	
	int i,j,m1,m2,x1,x2;
	/*哈夫曼樹初始化。n個葉結點共有2n-1個結點*/
	
	for(i=0;i<2*n-1;i++)
	{
		if(i<n)haffTree[i].weight=weight[i];
		else haffTree[i].weight=0;
		haffTree[i].parent=0;
		haffTree[i].flag=0;
		haffTree[i].leftChild=-1;
		haffTree[i].rightChild=-1;
	}
	/*構造哈夫曼樹的n-1個非葉結點*/
	for(i=0;i<n-1;i++)
	{
		m1=m2=MaxValue;
		x1=x2=0;
		for(j=0;j<n+i;j++)
		{
			if(haffTree[j].weight<m1&&haffTree[j].flag==0)
			{	
				m2=m1;
				x2=x1;
				m1=haffTree[j].weight;
				x1=j;
			}
			else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
			{	
				m2=haffTree[j].weight;
				x2=j;
			}
		}
		/*把找出的兩棵權值最小的子樹合并為1棵子樹*/
		haffTree[x1].parent=n+i;
		haffTree[x2].parent=n+i;
		haffTree[x1].flag=1;
		haffTree[x2].flag=1;
		haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
		haffTree[n+i].leftChild=x1;
		haffTree[n+i].rightChild=x2;
	}
}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
/*構造哈夫曼編碼haffCode*/
{
	Code*cd=(Code*)malloc(sizeof(Code));
	int i,j,child,parent;
	/*求n個葉結點的哈夫曼編碼*/
	for(i=0;i<n;i++)
	{
		cd->start=n-1;	/*最后一位為n-1*/
		cd->weight=haffTree[i].weight;/*取得權值*/
		child=i;
		parent=haffTree[child].parent;
		/*由葉結點向上直到根結點*/
		while(parent!=0)
		{
			if(haffTree[parent].leftChild==child)
			cd->bit[cd->start]=0;	/*左孩子分支編碼0*/
			else
				cd->bit[cd->start]=1;/*右孩子分支編碼1*/
				cd->start--;
				child=parent;
				parent=haffTree[child].parent;
		}
			for(j=cd->start+1;j<n;j++)
				haffCode[i].bit[j]=cd->bit[j];
				haffCode[i].start=cd->start;
				haffCode[i].weight=cd->weight;/*保存相應字符的權值*/
	}
      
}