struct  Da
{//記錄重建樹時(shí)個(gè)節(jié)點(diǎn)的信息
	int data;//記錄節(jié)點(diǎn)數(shù)據(jù)
	int rlen;//記錄左子樹結(jié)點(diǎn)個(gè)數(shù)
	int llen;//記錄右子樹結(jié)點(diǎn)個(gè)數(shù)
	int active;//記錄節(jié)點(diǎn)有沒有插到樹中情況
};

template<class Type> class BinaryTree;//二叉樹類的前視聲明
template<class Type> class BinaryTreeNode//二叉樹的結(jié)點(diǎn)類聲明
{
	public:
		friend  class BinaryTree<Type>;
		BinaryTreeNode():leftchild(NULL),rightchild(NULL),data() {}
		BinaryTreeNode(Type item,BinaryTreeNode<Type>*left=NULL,BinaryTreeNode<Type>*right=NULL):data(item),leftchild(left),rightchild(right){}
        Type GetData() const {return data;}//取得結(jié)點(diǎn)數(shù)據(jù)值
		BinaryTreeNode < Type > *GetLeft( ) const{ return leftchild; }//取得結(jié)點(diǎn)左子女的指針值
		BinaryTreeNode < Type > *GetRight( )const { return rightchild; }//取得結(jié)點(diǎn)右子女的指針值
		void SetData ( const Type &item){ data = item; }//修改結(jié)點(diǎn)數(shù)據(jù)值 
		void SetLeft ( BinaryTreeNode<Type> *L ){ leftchild = L ; }//修改結(jié)點(diǎn)左子女指針值
        void SetRight( BinaryTreeNode < Type > *R ){ leftchild = R; }//修改結(jié)點(diǎn)右子女指針值
        friend int equal ( BinaryTreeNode < Type > * a , BinaryTreeNode < Type > *b ); //判斷兩棵樹是否相等
		friend void ReConstruct ( BinaryTree < int >  &tr);//據(jù)前序遍歷和中序遍歷結(jié)果重建樹
		friend void PartionAndInsert( int *PreA , Da *IoA ,int  startp ,int starti,int  end , BinaryTreeNode < int > * &current,BinaryTree < int > &tr );//具體建造樹函數(shù)
	private:
		BinaryTreeNode < Type > *leftchild , *rightchild;//左子女、右子女鏈域 
		Type data;//數(shù)據(jù)域
};

template<class Type> class BinaryTree//二叉樹類定義
{
	public:
		BinaryTree():root(NULL){}//無參構(gòu)造函數(shù)
		BinaryTree(Type value ):RefValue(value),root(NULL){}//構(gòu)造函數(shù)
		virtual ~BinaryTree(){ destroy(root);}//析構(gòu)函數(shù)
		virtual int IsEmpty(){ return root==NULL?1:0;}//判斷二叉樹是否為空
		virtual BinaryTreeNode < Type>*LeftChild( BinaryTreeNode < Type > *current ){ return root!=NULL?current->leftchild:NULL; }//返回左子女結(jié)點(diǎn)地址
        virtual BinaryTreeNode< Type>*RightChild( BinaryTreeNode< Type > *current ){ return root!=NULL?current->rightchild:NULL; }//返回右子女結(jié)點(diǎn)地址
        void Insert( const Type &item ){ Insert(item , root);}//插入新元素
		void Remove( Type &item ) { Remove(item,root);}//刪包含item的節(jié)點(diǎn)
		BinaryTreeNode < Type >* GetRoot( ) const{ return root; }//取根
		Type GetRefValue( ) { return RefValue; }//獲得RefValue
		void Print( const  BinaryTreeNode < Type > *current ,int &i  ) const;//凹入表輸出
		void Traverse1( const BinaryTreeNode < Type > *current ) const;//前序遍歷
		void Traverse2( const BinaryTreeNode < Type > *current ) const;//中序遍歷
		void LevelOrder(  BinaryTreeNode < Type > *current ) const;//層次輸出
		int Size(const BinaryTreeNode<Type> * t)const;
		friend void ReConstruct ( BinaryTree < int >  &tr);//
		friend void PartionAndInsert( int *PreA , Da *IoA ,int startp ,int starti,int  end , BinaryTreeNode < int > * &current,BinaryTree < int > &tr );//
		friend bool operator == ( BinaryTree<Type> &ta , BinaryTree < Type > &tb );//重載兩棵樹是否相等函數(shù)
		friend istream &operator >> ( istream & in,BinaryTree <Type> &Tree );//輸入重載（建立二叉樹）
        friend ostream &operator << ( ostream & out,BinaryTree <Type> &Tree );//輸出二叉樹
	private:
		BinaryTreeNode < Type > *root;//二叉樹的根指針
		Type RefValue;//數(shù)據(jù)輸入結(jié)束標(biāo)記
        BinaryTreeNode<Type>*Parent( BinaryTreeNode<Type>*start,BinaryTreeNode < Type > *current );//返回雙親根結(jié)點(diǎn)
		void Insert( const Type &item , BinaryTreeNode<Type> * & current );//二叉搜索樹插入函數(shù)
		void Insert1( const Type &item , BinaryTreeNode<Type> * & current );//普通二叉搜索樹插入函數(shù)
		void Remove( const Type &item , BinaryTreeNode<Type> * & current );//刪包含item的節(jié)點(diǎn)
		void Traverse1( BinaryTreeNode < Type > *current, ostream &out ) const;//前序遍歷	    
		void Traverse2( BinaryTreeNode < Type > *current, ostream &out ) const;//中序遍歷
		void destroy ( BinaryTreeNode < Type > *current );//刪除結(jié)點(diǎn)
		BinaryTreeNode < Type > *Min ( BinaryTreeNode < Type > *current ) const;//最小值的結(jié)點(diǎn) 
};