main.cpp

该程序是基于哈弗曼树的构造

#include<iostream>
#include<deque>
#include<iterator>
using namespace std;

typedef int valueType;
struct Tree{
	struct Tree *lchild,*rchild;
	deque<int> ss;
	valueType value;
};



int findfirst(Tree *B[],int a)//找一个最小的值
{
	int i,j,min;
	min=100;
	for(i=0;i<a;i++)
	{
		if((B[i]->value)<min)
		{
			min=B[i]->value;
			j=i;
		}
	}
	return j;
}

int findsecond(Tree* B[],int a,int m)//找一个次小的值
{
	int i,j,min;
	min=100;
 	for(i=0;i<a;i++)
	{
		if(i!=m)
		{
			if((B[i]->value)<min)
			{
				min=B[i]->value;
				j=i;
			}
		}
	}
	return j;
}

bool decrease(Tree* B[],int a)//选取B中值最小的两个合并后重新插入数组中
{
	int m,n,j,x;
	m=findfirst(B,a);
	n=findsecond(B,a,m);
	cout<<m<<"  "<<n<<endl;
	(B[m]->ss).push_back(0);
	(B[n]->ss).push_back(1);
	Tree *p=new Tree;
	p->value=(B[m]->value)+(B[n]->value);
	cout<<p->value<<endl;
	p->lchild=B[m];
	p->rchild=B[n];

	if(m<n)
	{
		B[m]=p;
		for(j=n;j<a-1;j++)
		{
			x=j+1;
			B[j]=B[x];
		}
	}
	else if(m>n)
	{
		B[n]=p;
		for(j=m;j<a-1;j++)
		{
			x=j+1;
			B[j]=B[x];
		}
	}

	for(j=0;j<a-1;j++)
		cout<<B[j]->value<<"  ";
	cout<<endl;
	return true;
}

Tree* CreateTree(valueType A[])//建一棵哈弗曼树
{
	int i,j;
	Tree *q;
	Tree* B[8];
	for(i=0;i<8;i++)
	{
		Tree *p=new Tree;
		p->value=A[i];
		p->lchild=p->rchild=NULL;
		B[i]=p;
	}
	for(j=0;j<8;j++)
		cout<<B[j]->value<<"  ";
	cout<<endl;

	for(i=0;i<7;i++)
	{
		decrease(B,8-i);
	}
    q=B[0];
	return q;
}

void showTree(Tree *p)   //输出这棵树
{
	deque<int> sm;
	if(p)
	{	
		deque<int>::reverse_iterator iter;
		sm=p->ss;
	
		if(p->lchild)
		{
			for(iter=sm.rbegin();iter!=sm.rend();iter++)
			{
				((p->lchild)->ss).push_front(*iter);
			}
		}
		showTree(p->lchild);
		cout<<p->value<<"  ";
        if(p->rchild)
		{
			for(iter=sm.rbegin();iter!=sm.rend();iter++)
			{
				((p->rchild)->ss).push_front(*iter);
			}
		}
		showTree(p->rchild);
	}
}

void outPut(Tree *p)
{
	deque<int>::iterator iter;

	if(p->lchild)
		outPut(p->lchild);
		
    if(p->rchild)
		outPut(p->rchild);
	else
	{
		cout<<p->value<<": ";
		for(iter=(p->ss).begin();iter!=(p->ss).end();iter++)
		{
			cout<<*iter<<" ";

		}
		cout<<endl;
	}
}

void main()
{
	Tree *tr;
	int A[8]={5,29,7,8,14,23,3,11};
	tr=CreateTree(A);
	cout<<"输出这棵树："<<endl;
	showTree(tr);
	cout<<endl;
    cout<<"哈弗曼编码如下："<<endl;
	outPut(tr);
}