bintree.h

搜索二叉树的实现

struct  Da
{//记录重建树时个节点的信息
	int data;//记录节点数据
	int rlen;//记录左子树结点个数
	int llen;//记录右子树结点个数
	int active;//记录节点有没有插到树中情况
};

template<class Type> class BinaryTree;//二叉树类的前视声明
template<class Type> class BinaryTreeNode//二叉树的结点类声明
{
	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;}//取得结点数据值
		BinaryTreeNode < Type > *GetLeft( ) const{ return leftchild; }//取得结点左子女的指针值
		BinaryTreeNode < Type > *GetRight( )const { return rightchild; }//取得结点右子女的指针值
		void SetData ( const Type &item){ data = item; }//修改结点数据值 
		void SetLeft ( BinaryTreeNode<Type> *L ){ leftchild = L ; }//修改结点左子女指针值
        void SetRight( BinaryTreeNode < Type > *R ){ leftchild = R; }//修改结点右子女指针值
        friend int equal ( BinaryTreeNode < Type > * a , BinaryTreeNode < Type > *b ); //判断两棵树是否相等
		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 );//具体建造树函数
	private:
		BinaryTreeNode < Type > *leftchild , *rightchild;//左子女、右子女链域 
		Type data;//数据域
};

template<class Type> class BinaryTree//二叉树类定义
{
	public:
		BinaryTree():root(NULL){}//无参构造函数
		BinaryTree(Type value ):RefValue(value),root(NULL){}//构造函数
		virtual ~BinaryTree(){ destroy(root);}//析构函数
		virtual int IsEmpty(){ return root==NULL?1:0;}//判断二叉树是否为空
		virtual BinaryTreeNode < Type>*LeftChild( BinaryTreeNode < Type > *current ){ return root!=NULL?current->leftchild:NULL; }//返回左子女结点地址
        virtual BinaryTreeNode< Type>*RightChild( BinaryTreeNode< Type > *current ){ return root!=NULL?current->rightchild:NULL; }//返回右子女结点地址
        void Insert( const Type &item ){ Insert(item , root);}//插入新元素
		void Remove( Type &item ) { Remove(item,root);}//删包含item的节点
		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 );//重载两棵树是否相等函数
		friend istream &operator >> ( istream & in,BinaryTree <Type> &Tree );//输入重载（建立二叉树）
        friend ostream &operator << ( ostream & out,BinaryTree <Type> &Tree );//输出二叉树
	private:
		BinaryTreeNode < Type > *root;//二叉树的根指针
		Type RefValue;//数据输入结束标记
        BinaryTreeNode<Type>*Parent( BinaryTreeNode<Type>*start,BinaryTreeNode < Type > *current );//返回双亲根结点
		void Insert( const Type &item , BinaryTreeNode<Type> * & current );//二叉搜索树插入函数
		void Insert1( const Type &item , BinaryTreeNode<Type> * & current );//普通二叉搜索树插入函数
		void Remove( const Type &item , BinaryTreeNode<Type> * & current );//删包含item的节点
		void Traverse1( BinaryTreeNode < Type > *current, ostream &out ) const;//前序遍历	    
		void Traverse2( BinaryTreeNode < Type > *current, ostream &out ) const;//中序遍历
		void destroy ( BinaryTreeNode < Type > *current );//删除结点
		BinaryTreeNode < Type > *Min ( BinaryTreeNode < Type > *current ) const;//最小值的结点 
};