bst.h

一些查找的程序

template<class Type>
struct BSTNode{
	Type data;
	BSTNode *left;//给出结点的左儿子的地址
	BSTNode *right;//给出结点的右儿子的地址
    int SizeNode;
	int info;
	BSTNode():left(NULL),right(NULL),size(1){}
	int Size(BSTNode *T){
		if(T == NULL)
			return 0;
		else
		return 1 + Size(T->left)+Size(T->right);}
	BSTNode(const Type x,BSTNode *L = NULL,BSTNode *R = NULL):data(x),left(L),right(R),SizeNode(1){}
	~BSTNode(){}

};//二叉排序树的结点的表示


template<class Type>
class BinarySearchTree{
public:
	BinarySearchTree():LastFind(NULL),Root(NULL){count = 0;}
	~BinarySearchTree(){FreeTree(Root);}
	int Insert(const Type & x){return Insert(x,Root);}//插入x到以Root为根的二叉排序树，成功则返回1。
	const Type & Find(const Type & x){return (LastFind = Find(x,Root)?LastFind->data:ItemNotFound);}//若查找x成功，则返回二叉排序树中的相应数据项，否则返回ItemNotFound
	const Type & FindMin() const{
	    const BSTNode *p = FindMin(Root);
		return p?p->data:ItemNotFound;
	   }//返回二叉排序树中的最小数据项，若树为空，返回ItemNotFound
    const Type & FindMax() const{
	    const BSTNode *p = FindMax(Root);
		return p?p->data:ItemNotFound;
	   }//返回二叉排序树中的最大数据项，若树为空，返回ItemNotFound
	int IsFound(const Type & x){return Find(x,Root) != NULL;} //若x找到，则返回true
	int WasFound(const Type & x){return LastFound != NULL;}//最近一次查找成功，则返回True
	int Remove(const Type & x){reutn Remove(x,Root);}//从二叉排序树中删除值为x的结点，成功返回True
	int RemoveMin(){return RemoveMin(Root);}//从二叉树排序中删除最小结点，删除成功返回True
	int IsEmpty() const {return Root == NULL;}//二叉排序树为空，返回True，否则为False
	void MakeEmpty(){FreeTree(Root); Root == NULL; }//清除二叉排序树中的所有结点
	BSTNode<Type> * Root;
	void SetInfo(BSTNode<Type> *T);
	void GetInfo(BSTNode<Type> *T);
	void PrintInorder(BSTNode<Type> *T);
	int sort[100];
protected:
	const BSTNode<Type> *LastFind;
	Type ItemNotFound;//用于查找失败返回
	const BSTNode<Type> *Find (const Type & x,const BSTNode<Type> * T) const;
	const BSTNode<Type> *FindMin (const BSTNode<Type> * T) const;
    const BSTNode<Type> *FindMax (const BSTNode<Type> * T) const;
	int Insert(const Type & x,BSTNode<Type> *&T);
	int RemoveMin(BSTNode<Type> *&T);
	int Remove(const Type & x,BSTNode<Type> *&T);
	void FreeTree(BSTNode<Type> *T);
	int count;

};


template<class Type>
const BSTNode<Type> *BinarySearchTree<Type>::Find(const Type & x,const BSTNode<Type> * T) const{
    
	   while(T != NULL)
		   if(x < T-> data) T = T->left;
		   else if (x > T->data) T = T->right;
		   else return T;
	   return NULL;//查找失败，则返回空。查找成功，返回指向相应结点的指针
}

template<class Type>
const BSTNode<Type> *BinarySearchTree<Type>::FindMin(const BSTNode<Type> * T) const{

	if(T != NULL)
		while(T->left != NULL)
			T = T-> left;
	return T;//二叉排序树非空，返回最左方的左后代地址，空，返回NULL

}

template<class Type>
const BSTNode<Type> *BinarySearchTree<Type>::FindMax(const BSTNode<Type> * T) const{

	if(T != NULL)
		while(T->right != NULL)
			T = T-> right;
	return T;//二叉排序树非空，返回最右方的左后代地址，空，返回NULL

}



template<class Type> int BinarySearchTree<Type>::Insert(const Type & x,BSTNode<Type> *&T)
{
	if(T == NULL){
		T = new BSTNode<Type>(x);
	    return 1;//新结点插入
	}
	else if(x < T->data)
		return Insert(x,T->left);//转向左子树
	else if (x > T->data)
		return Insert(x,T->right);//转向右子树
	return 0;//若结点已经存在，返回不必重复插入标志
}//插入结点到以T为根的二叉排序树,插入成功返回1，插入失败返回0


template<class Type> int BinarySearchTree<Type>::RemoveMin(BSTNode<Type> *&T){

	if(T == NULL) return 0;
	else if(T -> left != NULL)
		return RemoveMin(T->left);
	BSTNode<Type> * p;
	p = T;
	T = T->right;
	delete p;
	return 1;


}//删除T的最左方的左后代，删除成功，返回1，删除失败，返回0。




template<class Type> int BinarySearchTree<Type>::Remove(const Type & x,BSTNode<Type> *&T){

	BSTNode<Type> * p;
	if(T == NULL) return 0;//删除失败，返回0；
	else if( x < T -> data) return Remove(x,T->left);//转向左子树
	else if( x > T -> data) return Remove(x,T->right);//转向右子树
	else if( T -> left != NULL && T-> right != NULL){//被删结点的左右儿子非空
	
		p = (BSTNode<Type> *) FindMin(T->right);
		T -> data = p -> data;//复制右子树最小结点数据值
		return RemoveMin(T->right);//删除被删结点的右子树的最小结点
	
	}
	p = T; //处理被删结点的至少一个儿子为空的情况
	T = (T->left == NULL)?T->right:T->left;
	delete p;
	return 1;
} //删除成功，返回1，删除失败，返回0


template<class Type>
void BinarySearchTree<Type>::FreeTree(BSTNode<Type> *T)
{
	if(T != NULL)
	{
   		FreeTree(T->left);
		FreeTree(T->right);
		delete T;
	}

}

template<class Type> void BinarySearchTree<Type>::SetInfo(BSTNode<Type> *T)
{
	T->info = T->Size(T->left);
	if(T->left != NULL)
	SetInfo(T->left);
	if(T->right != NULL)
	SetInfo(T->right);
}

template<class Type> void BinarySearchTree<Type>::GetInfo(BSTNode<Type> *T)
{ 
    cout << T->info << endl;
	if(T->left != NULL)
	GetInfo(T->left);
	if(T->right != NULL)
	GetInfo(T->right);

}

template<class Type> void BinarySearchTree<Type>::PrintInorder(BSTNode<Type> *T)
{
	if(T->left != NULL)
		 PrintInorder(T->left);
	 sort[count] = T->data;
	 count++;
	if(T->right != NULL)
		 PrintInorder(T->right);



}