哈夫曼树.cpp

数据结构常用算法

#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define N 10    
#define M 2*N-1 
typedef struct
{
	 int weight;
	 int parent,lchild,rchild;
}htnode;       //树中结点的结构
typedef struct
{
	char data;   
	int weight;  //字符的权值
	char code[N];
}htcode;
void init(htcode hc[],int  n)
{//初始化,读入编码字符的个数,从键盘输入6个字符和6个权值
	int i;
	cout<<"输入 "<<n<<" 个叶子结点： "<<endl;
	for(i=1;i<=n;i++)
		cin>>hc[i].data;
	cout<<"依次输入 "<<n<<" 个叶子结点的权值:"<<endl;
	for(i=1;i<=n;i++)
		cin>>hc[i].weight;
}
void select(htnode ht[],int n,int & s1,int & s2)
{//ht[1....k]中选择parent为0,并且weight最小的两个结点,
	//其序号由变量s1,s2返回
	int i;
	int max;
	int flag=1;
	for(i=1;i<=n;i++)
	{		//找前两个父结点为0的结点,用s1,s2返回其序号
		if(ht[i].parent==0 )
		{	
			if(flag)
			{s1=i;flag=0;}
			else
			{s2=i;break;}
		}
	}
	for(i=s2+1;i<=n;i++)
	{
		max=ht[s1].weight>ht[s2].weight?ht[s1].weight:ht[s2].weight;  //max=权大的结点的权
		if(ht[i].parent==0 && ht[i].weight<max)
			if(ht[s1].weight>ht[s2].weight)s1=i;   //因为ht[s1].weight>ht[s2].weight,
												   //并且ht[i].weight<ht[s1].weight,所以使s1=i
			else s2=i;
	}				   //// 寻找权值最小的两结点
}
void huffmancoding(htnode ht[],htcode hc[],int n)
{  //构造huffman树ht,并求出n个字符的编码
	char cd[N];
	int i,m,c,f,s1,s2,start;
	m=2*n-1;   //n=待编码字符个数   有N个叶子结点的二叉树有2n-1个结点
	for(i=1;i<=m;i++)  //初始化huffmantree
	{
		if(i<=n)
			ht[i].weight=hc[i].weight;
		else
			ht[i].weight=0;
		ht[i].parent=ht[i].lchild=ht[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)////建立huffmantree
	{    
		select(ht,i-1,s1,s2);
		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;		
	}
	cd[n-1]='\0';
	for(i=1;i<=n;i++)  
	{
		start=n-1;
		for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
			if(ht[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
			strcpy(hc[i].code,&cd[start]);////huffman编码
	}
}
void main()
{
	int i,n=6;
	htnode ht[20];
	htcode hc[11];
	init(hc,n);
	huffmancoding(ht,hc,n);
	cout<<"huffman编码为:"<<endl;
	for(i=1;i<=n;i++)
		cout<<hc[i].data<<"---------"<<hc[i].code<<endl;
}