extbintree1.h

霍夫曼压缩解压缩算法

#ifndef ex_h
#define ex_h
#include"Heap.h"
const int DefaultSize=256;
template<class Type> class BinaryTree;
template<class Type> class BinTreeNode{
	friend class BinaryTree<Type>;
public:
	BinTreeNode():leftChild(NULL),rightChild(NULL),ref(0){}
	BinTreeNode(Type item,BinTreeNode<Type> *left=NULL,
		BinTreeNode<Type> *right=NULL):data(item),
		leftChild(left),rightChild(right),ref(0){}
	Type GetData()const{return data;}
	BinTreeNode<Type> *GetLeft()const{return leftChild;}
	BinTreeNode<Type> *GetRight()const{return rightChild;}
	void SetData(const Type& item){data=item;}
	void SetLeft(BinTreeNode<Type> *L){leftChild=L;}
	void SetRight(BinTreeNode<Type> *R){rightChild=R;}
	friend int equal(BinTreeNode<Type> *a,BinTreeNode<Type> *b);
	friend int operator==(const BinTreeNode<Type>& a,const BinTreeNode<Type>& b);
private:
	BinTreeNode<Type> *leftChild, *rightChild;
	Type data;int ref;
};
template<class Type> class BinaryTree{
public:
	BinaryTree():root(new BinTreeNode<Type>()){}
	BinaryTree(Type value):RefValue(value),root(NULL){}
	BinaryTree(const BinaryTree<Type>& s); 
	BinaryTree<Type>& operator=(const BinaryTree<Type>& s);
	BinaryTree(BinaryTree<Type> &bt1,BinaryTree<Type> &bt2);
	virtual ~BinaryTree(){destroy(root);}
	void HuffmanTree(Type *fr,int n);
	virtual int IsEmpty(){return root==NULL?1:0;}
	virtual BinTreeNode<Type> *Parent(BinTreeNode<Type> *current){
		return root==NULL||root==current?NULL:Parent(root,current);
	}
	virtual BinTreeNode<Type> *LeftChild(BinTreeNode<Type> *current){
		return root!=NULL?current->leftChild:NULL;
	}
	virtual BinTreeNode<Type> *RightChild(BinTreeNode<Type> *current){
		return root!=NULL?current->rightChild:NULL;
	}
	const BinTreeNode<Type> *GetRoot()const{ return root;}
	BinTreeNode<Type>* Find(const Type &item)const{
		return Find(root,item);
	}
    friend int operator==(const BinaryTree<Type> &s, const BinaryTree<Type> &t);	
	//friend istream &operator>>(istream &in,BinaryTree<Type> &Tree);
	//friend ostream &operator<<(ostream &out,BinaryTree<Type> &Tree);
	long key;
private:
	BinTreeNode<Type> *root;
	Type RefValue;
  	BinTreeNode<Type>* Copy(BinTreeNode<Type> *orignode);
	BinTreeNode<Type> *Parent(BinTreeNode<Type> *start,BinTreeNode<Type> *current);
	int Insert(BinTreeNode<Type>* &current,const Type &item);
	//void Traverse(BinTreeNode<Type> *current,ostream &out)const;
	BinTreeNode<Type>* Find(BinTreeNode<Type> *current,const Type &item)const;
	void destroy(BinTreeNode<Type> *current);
};
template<class Type> BinaryTree<Type>::BinaryTree(const BinaryTree<Type>& s){
	root=Copy(s.root);
	key=s.key;
}
template<class Type> BinaryTree<Type>& BinaryTree<Type>::operator=(const BinaryTree<Type>& s){
	root=Copy(s.root);
	key=s.key;
	return *this;
}
template<class Type> BinaryTree<Type>::BinaryTree(BinaryTree<Type> &bt1,BinaryTree<Type> &bt2)
{
	root=new BinTreeNode<Type>();
	root->leftChild=Copy(bt1.root);root->rightChild=Copy(bt2.root);
	key=root->data.key=bt1.root->data.key+bt2.root->data.key;
    root->data.ch=0;
}
template<class Type> int equal(BinTreeNode<Type> *a,BinTreeNode<Type> *b){
	if(a==NULL&&b==NULL)return 1;
	if(a!=NULL&&b!=NULL&&a->data=b->data&&equal(a->leftChild,b->leftChild)&&
       equal(a->rightChild,b->rightChild))
	   return 1;
	return 0;
}
template<class Type> int operator==(const BinTreeNode<Type>& a,const BinTreeNode<Type>& b){
		return equal(&a,&b);
}
template<class Type> BinTreeNode<Type>* BinaryTree<Type>::Copy(BinTreeNode<Type> *orignode){
	if(orignode==NULL)return NULL;
	BinTreeNode<Type> *temp=new BinTreeNode<Type>;
	temp->data=orignode->data;
	temp->leftChild=Copy(orignode->leftChild);
	temp->rightChild=Copy(orignode->rightChild);
	return temp;
}
template<class Type> void BinaryTree<Type>::destroy(BinTreeNode<Type> *current){
	if(current!=NULL){
		destroy(current->leftChild);
		destroy(current->rightChild);
		delete current;
	}
}
template<class Type> BinTreeNode<Type> *BinaryTree<Type>::
               Parent(BinTreeNode<Type> *start,BinTreeNode<Type> *current){
    if(start==NULL)return NULL;
	if(start->leftChild==current||start->rightChild==current)return start;
	BinTreeNode<Type> *p;
	if((p=Parent(start->leftChild,current))!=NULL)return p;
	else return Parent(start->rightChild,current);
}
template<class Type> BinTreeNode<Type>* BinaryTree<Type>::Find(
			BinTreeNode<Type> *current,const Type &item)const{
	if(current==NULL) return NULL;
	else if(item.key==current->data.key&&item.ch==current->data.ch) return current;
	else if(Find(current->leftChild,item)) return Find(current->leftChild,item);
	else return Find(current->rightChild,item);
}
/*template<class Type> void BinaryTree<Type>::Traverse(BinTreeNode<Type> *current,ostream
										 &out)const{
	if(current!=NULL){
		if(current==root)
			out<<current->data.key;
		else
			out<<","<<current->data.key;
		Traverse(current->leftChild,out);
		Traverse(current->rightChild,out);
	}
}*/
template<class Type> void BinaryTree<Type>::HuffmanTree(Type *fr,int n){
	BinaryTree<Type> first,second,newtree;
	BinaryTree<Type> Node[DefaultSize];
	if(n>DefaultSize){
		cerr<<"Size n "<<n<<"exceeds the boundary of Array"<<endl;return;
	}
	for(int i=0;i<n;i++){
 		Node[i].root->SetData(fr[i]);
		Node[i].key=fr[i].key;
	}
    MinHeap< BinaryTree<Type> > hp(Node,n);	
	for(i=0;i<n-1;i++){
		hp.RemoveMin(first);hp.RemoveMin(second);
		newtree=BinaryTree<Type>(first,second);
		hp.Insert(newtree);
	}
	hp.RemoveMin(newtree);
	*this=newtree;
}
template<class Type> int operator==(const BinaryTree<Type> &s, const BinaryTree<Type> &t){
	return equal(s.root,t.root);
}
/*template<class Type> ostream &operator<<(ostream &out,BinaryTree<Type> &Tree){
	out<<"Preorder traversal of binary tree.\n";
	Tree.Traverse(Tree.root,out);
	out<<endl;
	return out;
}*/
#endif