hufffman.cpp

动态建立huffman树 纯语言完成

#include<iostream>
using namespace std;
class treenode
{
public:
	int m_data;
	treenode *m_left,*m_right;
public:
	treenode(int data=0,treenode *left=NULL,treenode *right=NULL)
	{
		m_data=data;
		m_left=left;
		m_right=right;
	}
};
void inorder(treenode *p)
{
	if(p!=NULL)
	{
		inorder(p->m_left);
		cout<<p->m_data<<" ";
		inorder(p->m_right);
	}
}
void main()
{
	cout<<"请输入数组大小:";
	int n;
	cin>>n;
	cout<<"请输入数组:";
	int *a=new int[n];
	for(int i=0;i<n;++i)
	{
		cin>>a[i];
	}
	treenode** ptr=new treenode* [n];
	for(int j=0;j<n;++j)
	{
		ptr[j]=new treenode(a[j]);
	}
	for(i=0;i<n-1;++i)
	{
		int k1=0;
		for(int k2=1;k2<n;++k2)
		{
			if(ptr[k2]->m_data<ptr[k1]->m_data)
				k1=k2;
		}
		int k3;
		if(k1==0)
			k3=1;
		else
			k3=0;
		for(k2=1;k2<n;++k2)
		{
			if(k2==k1)
				continue;
			else
			{
				if(ptr[k2]->m_data<ptr[k3]->m_data)
					k3=k2;
			}
		}
		treenode *p1=ptr[k1];
		treenode *p2=ptr[k3];
		ptr[k1]=new treenode(p1->m_data+p2->m_data,p1,p2);
		ptr[k3]=new treenode(1000);
	}
	i=0;
	for(j=1;j<n;++j)
	{
		if(ptr[i]->m_data>ptr[j]->m_data)
			i=j;
	}
	inorder(ptr[i]);
	cout<<"complete!"<<endl;
}