haff.cpp

哈夫曼树问题：数据结构中的基本问题

#include"iostream.h"
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
typedef struct{
	int weight;
	int parent;
	int lchild;
	int rchild;
}HNodeType;
HNodeType *HaffmanTree()
{
	HNodeType HuffNode[MAXNODE];
	int i,j,m1,m2,x1,x2,n;
	cin>>n;//输入叶子节点
	for(i=0;i<2*n-1;i++)
	{
		HuffNode[i].weight=0;
		HuffNode[i].parent=-1;
		HuffNode[i].lchild=-1;
		HuffNode[i].rchild=-1;
	}

	for(i=0;i<n;i++)
		cin>>HuffNode[i].weight;
	for(i=0;i<n-1;i++)
	{
		m1=m2=MAXVALUE;
		x1=x2=0;
		for(j=0;j<n+i;j++)
		{
			if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)
			{
				m2=m1;x2=x1;
				m1=HuffNode[j].weight;
				x1=j;
			}
			else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
			{
				m2=HuffNode[j].weight;
				x2=j;
			}
		}
			HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;
		HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
		HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;

	}
		for(i=0;i<=6;i++)
	{cout<<HuffNode[i].weight<<ends<<HuffNode[i].lchild<<ends;
	cout<<HuffNode[i].rchild<<ends<<HuffNode[i].parent<<endl;}
	return HuffNode;
}
void main()
{
	HNodeType *	huffnode;
	int i;
	huffnode=HaffmanTree();
	for(i=0;i<=6;i++)
	{cout<<huffnode[i].weight<<ends<<huffnode[i].lchild<<ends;
	cout<<huffnode[i].rchild<<ends<<huffnode[i].parent<<endl;}
		//		{cout<<HuffNode[n+i].weight<<ends<<HuffNode[n+i].lchild<<ends;
	//cout<<HuffNode[n+i].rchild<<ends<<n+i<<endl;}

}