binarytree.h

数据结构程序设计21

#ifndef BINARYTREE
#define BINARYTREE

#include<iostream.h>
#include "Queue.h"


template<class Type> class BinaryTree;
template<class Type> class FullBinaryTree;
template<class Type> class BinTreeNode
{
	friend class BinaryTree<Type>;
	friend class FullBinaryTree<Type>;

	public:
		BinTreeNode():leftChild(NULL),rightChild(NULL){}
		BinTreeNode(Type item,BinTreeNode<Type> *left=NULL,
			BinTreeNode<Type> * right=NULL):data(item),
			leftChild(left),rightChild(right){}
		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;}
	private:
		BinTreeNode<Type> *leftChild,* rightChild;
		Type data;
};


template<class Type> class BinaryTree
{
	public:
		BinaryTree():root(NULL){}
		BinaryTree(Type  value)
			:RefValue(value),root(NULL)	{}

		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;
		}
		virtual int Insert(const Type & item)=0;
		virtual int Find(const Type & item)const;
		virtual void print(ostream &out){};
		virtual void destory(){destory(root);}
		const BinTreeNode<Type> * GetRoot() const { return root;}
		friend istream &operator >> (istream & in,BinaryTree<Type> & Tree);
		friend ostream & operator<< (ostream & out,BinaryTree<Type> & Tree);
	protected:
		BinTreeNode<Type> * root;
		BinTreeNode<Type> * current;
		Type  RefValue;

		int depth(BinTreeNode<Type> *current);
		//以current为根结点的二插树的高度
		int depth(){ return depth(root)-1;}
		//二叉树高度 若为空树则返回-1
	
		virtual int Insert(BinTreeNode<Type>* current,const Type & item)=0;
	private:
		BinTreeNode<Type> * Parent(BinTreeNode<Type> * start,BinTreeNode<Type> * current);
		void destory(BinTreeNode<Type> * current);
		void Traverse(BinTreeNode<Type> *current,ostream & out) const;
		int Find(BinTreeNode<Type> * current,const Type & item) const;
	
};

template<class Type> void BinaryTree<Type>::destory(BinTreeNode<Type> * current)
{ 
	if(current!=NULL)
	{
		destory(current->leftChild);
		destory(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> void BinaryTree<Type>::Traverse(BinTreeNode<Type> * current,ostream & out) const
{
	if(current!=NULL)
	{
		out<<current->data<<' ';
		Traverse(current->leftChild,out);
		Traverse(current->rightChild,out);
	}
}

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

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;
}

template<class Type> int BinaryTree<Type>::Find(BinTreeNode<Type> * current,const Type & item) const
{
	if(current==NULL) return 0;
	else 
	{
	   if(current->data==item) return 1;
	   else if(Find(current=current->leftChild,item)==1) return 1;
	   else if(Find(current=current->rightChild,item)==1) return 1;
	   else
		   return 0;
	}
}




template<class Type> int BinaryTree<Type>::Find(const Type & item) const
{
	if(Find(current,item)) return 1;
	return 0;
}
template<class Type> int BinaryTree<Type>::depth(BinTreeNode<Type> *current)
{
	if(current==NULL) return 0;
	else
	{
		int d1,d2;
		d1=depth(current->leftChild)+1;
		d2=depth(current->rightChild)+1;
		if(d1>d2) return d1;
		else
			return d2;
	}
}
#endif