binarytree.h

该程序用ＶＣ实现了一个小型文件压缩与解压缩功能的程序

#ifndef BinaryTree_H
#define BinaryTree_H
#include<iostream.h>
#include<assert.h>
#include<stdlib.h>
#include<iomanip.h>
#include"BinTreeNode.h"
#include"MinHeap.h"
#include<fstream.h>

template<class T>
class BinaryTree
{
	private:
		BinTreeNode<T> *root;
		BinTreeNode<T> *Parent(BinTreeNode<T> *start,BinTreeNode<T> *current);
		void Insert(BinTreeNode<T>* &Ptr,const T& item);
		T MaxValue(BinTreeNode<T>* Ptr,T& Max);
		BinTreeNode<T>* GetNode(const T item,BinTreeNode<T>* &Ptr);
		void print(BinTreeNode<T> *current,ostream& out) const;
		int Find(BinTreeNode<T> *current,const T& item) const;
		int level(BinTreeNode<T> *t,BinTreeNode<T> *p);
		BinTreeNode<T>* Copy(BinTreeNode<T> *node);
		
	public:
		void destroy(BinTreeNode<T> *current);
		BinaryTree():root(NULL){}
		BinaryTree(BinaryTree<T> &T) {root = Copy(T.root);}
	    ~BinaryTree() {destroy(root);}
		 int IsEmpty(){return root==NULL?1:0;}
		 BinTreeNode<T>* GetNode(const T item);
    	 BinTreeNode<T>* Parent(BinTreeNode<T> *current)
		{return root==NULL||root==current ? NULL : Parent(root,current);}
		 BinTreeNode<T>* Parent(const T& item);
		 int level(const T& item,int &lev);
		 BinaryTree<T>& MakeTree(const BinaryTree<T>& lt,const BinaryTree<T>& rt);
		 void HuffmanTree(T item[],int frqu[],int n,BinaryTree<T>& newTree);
		void Decoding(int code[],int n);
		void Coding(T& item,int a[]);
		void Coding(char *filename1,char *filename2,BinaryTree<T>& Tree);
		void Decoding(char *file,char * codefile,BinaryTree<T>& Tree);
         void Insert(const T& item);

		 void PrintTree(BinTreeNode<T>* Ptr,int level);
		 void Blanks(int n);
		 BinTreeNode<T> *GetRoot()  {return root;}
		 bool operator > (const BinaryTree<T>& p)
		 {
			 return root->Flag > p.root->Flag;
		 }

		 bool operator <= (const BinaryTree<T>& p)
		 {
			 return root->Flag <= p.root->Flag;
		 }
        BinaryTree<T>& operator = (const BinaryTree<T>& p);

		friend istream& operator >> (istream& is, BinaryTree<T> &Tree);

		friend ostream& operator << (ostream& os, const BinaryTree<T>& Tree);
};

template<class T>
void BinaryTree<T>::destroy(BinTreeNode<T> *current)
{
	if(current != NULL){
		destroy(current->leftChild);
		destroy(current->rightChild);
		delete current;
	}
}

template<class T>
 BinaryTree<T>& BinaryTree<T>::MakeTree(const BinaryTree<T>& lt,const BinaryTree<T>& rt)
 {

	 root = new BinTreeNode<T>;
	 root->data ='#';
	 root->Flag = lt.root->Flag + rt.root->Flag;
     root->leftChild = lt.root;
	 root->rightChild = rt.root;
	 return *this;
 }

template<class T>
void BinaryTree<T>::HuffmanTree(T item[],int frqu[],int n,BinaryTree<T>& newTree)
 {
	 BinaryTree<T> first,second;
	 BinaryTree<T>* Node;
	 Node = new BinaryTree<T>[n];
	 for(int i=0;i<n;i++){	
 		 Node[i].root = new BinTreeNode<T>(item[i],frqu[i],NULL,NULL);
	 }
	 MinHeap< BinaryTree<T> > heap(Node,n);
	  for(i=0;i<n-1;i++){
		  heap.RemoveMin(first); 
		  heap.RemoveMin(second);
		  newTree = MakeTree(first,second);
		  root = newTree.root;
		  heap.Insert(newTree);
	  }
	  cout<<endl<<endl;
 }






 
 template<class T>
 BinaryTree<T>& BinaryTree<T>::operator = (const BinaryTree<T>& p) 
 {

	 root = Copy(p.root);
	 return *this;
 }


 
template<class T>
 BinTreeNode<T>* BinaryTree<T>::Copy(BinTreeNode<T> *node)
 {
	 if(node == NULL) return NULL;
	 BinTreeNode<T> *temp = new BinTreeNode<T>;
	 temp->data = node->data;
	 temp->Flag = node->Flag;
	 temp->leftChild = Copy(node->leftChild);
	 temp->rightChild = Copy(node->rightChild);
	 return temp;
 }












template<class T>
BinTreeNode<T>* BinaryTree<T>::GetNode(const T item)
{
	BinTreeNode<T> *p = GetNode(item,root);
	return p;
}





template<class T>
BinTreeNode<T>* BinaryTree<T>::GetNode(const T item,BinTreeNode<T>* &Ptr)
{
	if(Ptr == NULL) return NULL;
	else if(Ptr->data == item) return Ptr;
	else{
		BinTreeNode<T> *p=NULL;
		p=GetNode(item,Ptr->leftChild);
		if(p!=NULL)
			return p;
		else
			return GetNode(item,Ptr->rightChild);
		}
}


template<class T>
int BinaryTree<T>::level(const T& item,int& lev)
{
	BinTreeNode<T> *p = GetNode(item,root);
	int m = level(root,p);
	lev = m;
	return m;
}

template<class T>
int BinaryTree<T>::level(BinTreeNode<T> *t,BinTreeNode<T> *p)
{
	int leftLevel=0,rightLevel=0;
	if(t==NULL){
		return -1;}
	if(t==p) return 0;
	if((leftLevel = level(t->leftChild,p)) > -1) 
		return leftLevel + 1;
	if((rightLevel = level(t->rightChild,p)) > -1)
		return rightLevel + 1;
	return -1;
}









template<class T>
BinTreeNode<T>* BinaryTree<T>::Parent(const T& item)
{
	BinTreeNode<T>* p = GetNode(item);
//	cout<<item<<endl;
	return Parent(root,p);
}



template<class T>
BinTreeNode<T>* BinaryTree<T>::Parent(BinTreeNode<T> *start,BinTreeNode<T> *current)
{
	if(start == NULL) return NULL;	
	if(start->leftChild == current || start->rightChild == current) return start;
	
		BinTreeNode<T> *p;
		if((p = Parent(start->leftChild,current)) != NULL) return p;
		else return Parent(start->rightChild,current);


}





template<class T>
void BinaryTree<T>::Insert(const T& item)
{
	Insert(root,item);
}



template<class T>
void BinaryTree<T>::Insert(BinTreeNode<T>* &Ptr,const T& item)
{
	if(Ptr==NULL){
		Ptr = new BinTreeNode<T>(item);
		assert(Ptr!=NULL);
//		cout<<Ptr<<endl;
	}
	else{
		if(Ptr->data < item)
				Insert(Ptr->rightChild,item);        
		else if(Ptr->data >= item)
					Insert(Ptr->leftChild,item);
	}
}
	

template<class T>
void BinaryTree<T>::PrintTree(BinTreeNode<T>* Ptr,int level)
{
	if(Ptr!=NULL){
		PrintTree(Ptr->rightChild,level+1);
		Blanks(3*level);
		cout<<Ptr->data<<endl;
		PrintTree(Ptr->leftChild,level+1);
	}
}


template<class T>
void BinaryTree<T>::Blanks(int n)
{
	for(int i=0;i<n;i++)
		cout<<" ";
}


template<class T>
void BinaryTree<T>::print(BinTreeNode<T> *current,ostream& os) const
{
	if(current != NULL){
		os<<setw(30)<< "current    :"<<current<<endl
		<<setw(30)<< "data       :" <<current->data<<endl
		<<setw(30)<<"leftChild  :"<<current->leftChild<<endl
		<<setw(30)<<"rightChild :"<<current->rightChild<<endl;
		os<<endl;
		print(current->leftChild, os);
		print(current->rightChild, os);
	}
}



template<class T>
void BinaryTree<T>::Coding(char *filename1,char *filename2,BinaryTree<T>& Tree)
{
	*this = Tree;
	ifstream fin;
	fin.open(filename1);
	if(!fin)
	{
		cout<<"file can't open!"<<endl;
		exit(1);
	}
    ofstream fout;
	fout.open(filename2);
	if(!fout)
	{
		cout<<"file can't open!"<<endl;
		exit(1);
	}
	int a[100];int level = 0;
	T item;
//	while(fin>>item )
	while(fin.get(item)){                          
//		cout<<item<<"--->";
		Coding(item,a);
		this->level(item,level);
		for(int i=0;i<level;i++){
//			cout<<a[i]<<" ";
			fout<<a[i];
		}
	
//		cout<<endl;
	}
	

	fin.close();
	fout.close();
}




/*
template<class T>
void BinaryTree<T>::Decoding(int code[],int n)
{

	int i=0;
	BinTreeNode<T>* p=root;
	for(i=0;i<n;i++)
	{
		if(code[i]==0){
			if(p->leftChild==NULL){ 
				cout<<"NO"<<" ";
				p = root; continue;
			}
			p = p->leftChild;
		}
		
		else {
			if(p->rightChild==NULL){
				cout<<"NO"<<" ";
				p = root;continue;
			}
			p = p->rightChild;
		}
		if( p->IsLeaf()) {
			cout<<p->data<<" ";
			p = root;
		}
	}
	cout<<endl;

}
*/


template<class T>
void BinaryTree<T>::Decoding(char *file,char *codefile,BinaryTree<T>& Tree)
{
	*this = Tree;
	ifstream fin;
	fin.open(file);
	if(!fin)
	{
		cout<<"file can't open!"<<endl;
		exit(1);
	}
	ofstream fout;
	fout.open(codefile);
	if(!fout)
	{
		cout<<"codefile can't open!"<<endl;
		exit(1);
	}
//	int temp=0;
	char temp;
	BinTreeNode<T> *p=root;
//	while(fin>>temp)
	while(fin.get(temp))
	{
		if(temp=='0'){
			if(p->leftChild==NULL){ 
				cout<<"NO"<<" ";fout<<"NO"<<" ";
				p = root; continue;
			}
			p = p->leftChild;
		}
		else {
			if(p->rightChild==NULL){
				cout<<"NO"<<" ";fout<<"NO"<<" ";
				p = root;continue;
			}
			p = p->rightChild;
		}
		if( p->IsLeaf()) {
			cout<<p->data;
			fout<<p->data;
			
			p = root;
		}
	}cout<<endl;fin.close();
}


template<class T>
void BinaryTree<T>::Coding(T& item,int a[])
{
	int i=0;int m=0;
	level(item,m);
	BinTreeNode<T>* p = GetNode(item);
	while(p!=root){	
		BinTreeNode<T>* q = Parent(p);
		if(q->leftChild == p) a[--m]=0;
		else a[--m]=1;
		p = q;
	}
}




	
	

/*

template<class T>
istream& operator >> (istream& is, BinaryTree<T> &Tree)
{
	T item;
	cout<<"Construct binary tree:"<<endl;
	cout<<"Input data ( end with"<< Tree.RefValue <<"):";
	is>>item;
	while(item != Tree.RefValue){
		cout<<"Input data ( end with" << Tree.RefValue <<"):";
		is >> item;
	}
	return is;
}

*/



template<class T>
ostream& operator << (ostream& os, const BinaryTree<T>& Tree)
{

	Tree.print(Tree.root,os);

	return os;
}


#endif