7_4.cpp

C++的电子教程

#include<stdio.h>
#include<stdlib.h>
#define N 10
#define Max 100

typedef struct node
{	union 
	{	char data;
		int w;
	}val;
	struct node *left,*right;
}NODE;

NODE *htree(char *dat,int *w,int n)    //构造Huffman树
{	NODE *T[N],*p;
	int n1,n2,min1,min2,i,j,v;
	for(i=0;i<n;i++)     //构造n棵只有根结点的二叉树的森林
	{	T[i]=(NODE *)malloc(sizeof(NODE));
		T[i]->val.w=w[i];
		T[i]->left=NULL;
		T[i]->right=NULL;
	}
	for(i=0;i<n-1;i++)   //重复（2）和（3）
	{	n1=n2=-1;
		min1=min2=Max;
		for(j=0;j<n;j++)  //选取两棵根结点权值最小的树
		{	if(T[j]!=NULL)
			{	v=T[j]->val.w;
				if(v<min1)
				{	min2=min1;	n2=n1;
					min1=v; 	n1=j;
				}
				else if(v<min2)/**/
				{	min2=v;	n2=j; }
			}
		}

		p=(NODE *)malloc(sizeof(NODE));
		p->val.w=T[n1]->val.w+T[n2]->val.w;
		p->left=T[n1];		p->right=T[n2];

		if(T[n1]->left==NULL)   //新树的左子树的根为叶结点
			T[n1]->val.data=dat[n1];
		else		T[n1]->val.data='*';	   //否则为分支结点

		if(T[n2]->left==NULL)  //新树的右子树的根为叶结点
			T[n2]->val.data=dat[n2];
		else		T[n2]->val.data='*';		//否则为分支结点

		T[n1]=p; T[n2]=NULL;  //在森林中，用新树取代原先的两棵树
	}
	p->val.data='*';    //最后树的根结点为分支结点
	return(p);
}


void prn_btree(NODE *b)
{	if(b!=NULL)
	{	printf("%c",b->val.data);
		if(b->left!=NULL)
		{	printf("(");
			prn_btree(b->left);
			printf(",");
			prn_btree(b->right);
			printf(")");
		}
	}
}

void main()//主函数
{
	NODE *h;
	char d[N]="abcd";
	int w[N]={5,7,2,4};
	h=htree(d,w,4);
	prn_btree(h);   //输出huffman树
	printf("\n");
}