哈夫曼树.cpp

此程序是基于哈夫曼树的编码和译码操作！可实现根据叶子结点的权值

#include<iostream.h>

#define MAX 50

struct HfTreeNode
{
  char data;
  int QZ;
  int parent;
  int Lchild,Rchild;
};

class HuffmanTree
{
public:
	HuffmanTree();
	void CreatHfTree();
	void Bianma(int root);
	void Yima();
	void Getmin(int &,int &,int L);
	int getroot(){return 2*L-2;};
private:
	HfTreeNode HfT[MAX];
    int L;
	char a[10];
	int al;
	
};

HuffmanTree::HuffmanTree()
{
  for(int i=0;i<MAX;i++)
  {
    HfT[i].parent=-1;
	HfT[i].Lchild=-1;
	HfT[i].Rchild=-1;
	HfT[i].data='#';
	HfT[i].QZ=9999;
  }
  a[0]='\0';
  al=0;
}

void HuffmanTree::CreatHfTree()
{
  int i,m,n;
  cout<<"请输入叶子结点的个数"<<endl;
  cin>>L;
  for(i=0;i<L;i++)
  {
     cout<<"请输入要编码的元素：";
	 cin>>HfT[i].data;
	 cout<<"请输入该元素的权值：";
	 cin>>HfT[i].QZ;
  }

  for(int j=0;j<i;j++)
  {
   Getmin(m,n,2*i);
   if(m!=999&&n!=999)
   {
	 HfT[i+j].QZ=HfT[n].QZ+HfT[m].QZ;
	 HfT[i+j].Lchild=m;
	 HfT[i+j].Rchild=n;
	 HfT[n].parent=i+j;
	 HfT[m].parent=i+j;
   }
  }	
}

void HuffmanTree::Getmin(int &m,int &n,int l)
{
   int QZ=9999;
   m=999;
   n=999;
   for(int k=0;k<l;k++)
   {
     if(HfT[k].QZ<QZ&&HfT[k].parent==-1)
	 {
		m=k;
		QZ=HfT[k].QZ;
	 }
   }

   QZ=9999;
   for(k=0;k<l;k++)
   {
     if(HfT[k].QZ<QZ&&k!=m&&HfT[k].parent==-1)
	 {
		n=k;
		QZ=HfT[k].QZ;
	 }
   }

}

void HuffmanTree::Bianma(int root)
{
  if(HfT[root].data!='#')
  { 
     cout<<HfT[root].data<<" "<<a<<endl;
	 al--;
  }
  else
  {
    a[al]='0';
	al++;
	a[al]='\0';
    Bianma(HfT[root].Lchild);
	a[al]='1';
	al++;
	a[al]='\0';
	Bianma(HfT[root].Rchild);
	al--;
  }
}

void HuffmanTree::Yima()
{
  int k[100],i,root,num;
   cout<<"请输入二进制码字数：";
   cin>>num;
   cout<<"请输入二进制码"<<endl;
   for(i=0;i<num;i++)
   {
	   cin>>k[i];
   }
 
   root=getroot();
   for(int j=0;j<=i;j++)
   {
     if(k[j]==0)
	 {
	    root=HfT[root].Lchild;
		if(HfT[root].data!='#')
		{
		  cout<<HfT[root].data;
		  root=getroot();
		}
	 }
     if(k[j]==1)
	 {
	    root=HfT[root].Rchild;
		if(HfT[root].data!='#')
		{
		  cout<<HfT[root].data;
		  root=getroot();
		}
	 }
   }

}

void main()
{
   HuffmanTree hft;
   hft.CreatHfTree();
   hft.Bianma(hft.getroot());
   hft.Yima();
   cout<<endl;
}