#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>

template<class Type>
class BinarySearchTree;

template<class Type>
class BSTNode{      //结点结构
	friend class BinarySearchTree<Type>;
	public:
		BSTNode():left(0),right(0),Size(1),BalanceFactor(1){;}
		BSTNode(const Type x):data(x),left(0),right(0),Size(1),BalanceFactor(1){;}
		~BSTNode(){}
		BSTNode(const Type x,BSTNode<Type> *L,BSTNode<Type> *R):data(x),left(L),right(R),Size(1),BalanceFactor(1){;}
		void FreeTree(BSTNode<Type> *T);
	private:
		Type data;
	    BSTNode<Type> *left, *right;
		int BalanceFactor;
		int Size;
};

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

template<class Type>
class BinarySearchTree{
	public:
		BinarySearchTree():LastFind(0),Root(0){}
		~BinarySearchTree(){FreeTree(Root);}
		int Insert(const Type &x) {return Insert(x,Root);}
		const Type &Find(const Type x) {return (LastFind=Find(x,Root))?LastFind->data:ItemNotFound;}
		const Type &FindMin() const{const BSTNode *p=FindMin(Root);return p?p->data:ItemNotFound;}
		const Type &FindMax() const{const BSTNode *p=FindMax(Root);return p?p->data:ItemNotFound;}
		int IsFound(const Type &x){return Find(x,Root) != 0;}
		int WasFound() const {return LastFound != 0;}
		int Remove(const Type &x) {return Remove(x,Root);}
		int RemoveMin() {return RemoveMin(Root);}
		int IsEmpty() const {return Root == 0;}
		void MakeEmpty() {FreeTree(Root); Root = 0;}
	protected:
		BSTNode<Type> *Root;
		const BSTNode<Type> *LastFind;
		Type ItemNotFound;
		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);
};

template<class Type>
BSTNode<Type> *BinarySearchTree<Type>::Find(const Type &x,const BSTNode<Type> *T) const{
	if(T != 0){
		if(x < T->data)
			T = T->left;
		else if(x > T->data)
			T = T->Right;
		else return T;
	}
	return 0;
}

template<class Type>
const BSTNode<Type> *BinarySearchTree<Type>::FindMin(const BSTNode<Type> *T) const{
	if(T != 0)
		while(T->left != 0) T = T->left;
	return T;
}

template<class Type>
const BSTNode<Type> *BinarySearchTree<Type>::FindMax(const BSTNode<Type> *T) const{
	if(T != 0)
		while(T->right != 0) T = T->right;
	return T;
}

template<class Type>
int BinarySearchTree<Type>::Insert(const Type &x, BSTNode<Type> *&T){
	if(T != 0){
		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;
}

template<class Type>
int BinarySearchTree<Type>::RemoveMin(BSTNode<Type> *&T){
	if(T == 0)
		return 0;
	else if(T->left != 0)
		return RemoveMin(T->left);
	BSTNode<Type> *p;
	p = T;
	T = T->right;
	delete p;
	return 1;
}

template<class Type>
int BinarySearchTree<Type>::Remove(const Type &x, BSTNode<Type> *&T){
	BSTNode<Type> *p;
	if(T == 0)
		return 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 != 0 && T->right != 0){
		p = (BSTNode<Type> *)FindMin(T->right);
		T->data = p->data;
		return RemoveMin(T->right);
	}
	p = T;
	T = (T->left == 0)?T->right:T->left;
	delete p;
	return 1;
}

void main(void)
{
;	//按实际情况给出
}