bitree.cpp

运用面向对象方法编写的一个haffman编码树

// BiTree.cpp: implementation of the CBiTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "BiTree.h"
#include "LinkList.h"
#include "iostream.h"


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBiTree::CBiTree()
{
	root=NULL;
}

CBiTree::~CBiTree()
{

}

void CBiTree::CountLeaves(CBiTreeNode *p)
{
	if(p!=NULL)
	{
		CountLeaves(p->lChild);
		CountLeaves(p->rChild);
		if(p->lChild==NULL&&p->rChild==NULL)
		{
			codes.push_back(p);
			display(p);
		}
	}
}

CBiTree::Calculateweight(int *frelist,float *weight)
{
	int temp=0;

	for(int i=0;i<128;i++)
	{
		if(frelist[i]>0)
			temp=temp+frelist[i];
	}

	for(i=0;i<128;i++)
	{
		if(frelist[i]>0)
			weight[i]=((float)frelist[i])/temp;
	}

}
CBiTreeNode * CBiTree::CreatTree(float * weight)
{
	CLinkList mylist;
	for(int i=0;i<128;i++)//结点入队
	{
		if(weight[i]>(float)0)
		{
			CBiTreeNode *p=new CBiTreeNode(weight[i],i,NULL,NULL,NULL);
			mylist.Insert(p);
			
		}
	}

	CBiTreeNode *p,*q,*r;
	while(1)
	{
		

		p=mylist.Delete();
		
		if(p->weight==1.00000)
		{
			break;
			return (root=p);
		}
		
		q=mylist.Delete();
		r=new CBiTreeNode((p->weight+q->weight),int('Q'),p,q,NULL);
		p->parent=r;
		q->parent=r;
		mylist.Insert(r);
	}
	return (root=p);
	
}



void CBiTree::preorder(CBiTreeNode *p)
{
	if(p!=NULL)
	{
		this->display(p);
		preorder(p->lChild);
		preorder(p->rChild);
	}
}

void CBiTree::editcode(CBiTreeNode *p)
{
	
	if(p!=NULL)
	{	
		
		int n=p->num.size();
		if(p->lChild!=NULL)
		{
			p->lChild->num.resize(n);

			for(int i=0;i<p->num.size();i++)
			{
				p->lChild->num[i]=p->num[i];
				
			}

			p->lChild->num.resize(n+1);
			p->lChild->num[n]='0';
		}
		
		
		editcode(p->lChild);
		
		int m=p->num.size();
		if(p->rChild!=NULL)
		{
			p->rChild->num.resize(m);
			for( int i=0;i<p->num.size();i++)
			{
				p->rChild->num[i]=p->num[i];
			}
			p->rChild->num.resize(m+1);
			p->rChild->num[m]='1';
		}
		editcode(p->rChild);
	}
}

void CBiTree::display(CBiTreeNode * temp)
{
	cout<<"字符:"<<temp->data<<" 频率:"<<temp->weight<<" 编码";
	for(int i=0;i<temp->num.size();i++)
	{
		cout<<temp->num[i];
	}
	cout<<endl;
}

void CBiTree::Decode(char *p_words,int w_size,char *q_codes,int &code_size)
{
	for(int i=0;i<w_size;i++)
	{
		
		for(int j=0;j<codes.size();j++)
		{
			if(p_words[i]==codes[j]->data)
			{
				for(int m=0;m<codes[j]->num.size();m++)
				{
					q_codes[code_size++]=codes[j]->num[m];
				}
			}
		}
	}
}

void CBiTree::printcodes(char *p_codes,int code_size)
{
	cout<<"译文为:";
	for(int i=0;i<code_size;i++)
	{
		cout<<p_codes[i];
	}

	cout<<endl;
}