bst.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//二叉搜索树类
#ifndef BST_H
#define BST_H
template <class E, class K>
struct BSTNode  {			    //二叉树结点类
	E data;				    //数据域
	BSTNode<E, K> *left, *right;  //左子女和右子女
	BSTNode() { left = NULL; right = NULL; }
	//构造函数
	BSTNode (const E d, BSTNode<E, K> *L = NULL, 
		BSTNode<E, K> *R = NULL)
	{ data = d; left = L; right = R;}
	//构造函数
	~BSTNode() {}				//析构函数
	void setData (E d) { data = d; }	//修改	
	E getData() { return data; }		//提取
	bool operator < (const E& x) 	//重载：判小于
	{ return data.key < x.key; }   
	bool operator > (const E& x) 	//重载：判大于
	{ return data.key > x.key; }
	bool operator == (const E& x) 	//重载：判等于
	{ return data.key == x.key; }
};

template <class E, class K>
class BST {				  //二叉搜索树类定义
public:
	BST() { root = NULL; }	  //构造函数
	BST(K value);			  //构造函数
	BST(BSTNode<E,K> * temp):root(temp){}
	~BST() {};			  //析构函数	
	bool Search (const K x) 	//搜索 
	{ return Search(x,root) != NULL; }
	BST<E, K> operator = (const BST<E, K>& R);		     				//重载：赋值
	void makeEmpty() 			//置空
	{ makeEmpty (root); root = NULL;}
	bool isEmpty() { return root==NULL;}
	void PrintTree() const { PrintTree (root); }    //输出
	E Min() { return Min(root)->data; }	 //求最小
	E Max() { return Max(root)->data; }	 //求最大
	bool Insert (const E& e1)                //插入新元素
	{ return Insert(e1, root);}
	bool Remove (const K x) { return Remove(x, root);} 	  //删除含x的结点
private: 
	BSTNode<E, K> *root;	//根指针
	K RefValue;	 		//输入停止标志
	BSTNode<E, K> * 	Search (const K x, BSTNode<E, K> *ptr);//递归：搜索
	void makeEmpty (BSTNode<E, K> *& ptr);						//递归：置空
	void PrintTree (BSTNode<E, K> *ptr) const;						//递归：打印
	BSTNode<E, K> *Copy (const BSTNode<E, K> *ptr);		//递归：复制
	BSTNode<E, K>* Min (BSTNode<E, K>* ptr);						//递归：求最小
	BSTNode<E, K>* Max (BSTNode<E, K>* ptr);					//递归：求最大
	bool Insert (E& e1, BSTNode<E, K>*& ptr);					//递归：插入
	bool Remove (const K x, BSTNode<E, K>*& ptr);					//递归：删除
};

template<class E, class K>
BSTNode<E, K>* BST<E, K>::Search (const K x, BSTNode<E, K> *ptr) {
	//非递归函数：在当前以ptr为根的二
	//叉搜索树中搜索含x的结点。若找到，则函数返
	//回该结点的地址，否则函数返回NULL值。
	if (ptr == NULL) return NULL; 
	BSTNode<E, K>* temp = ptr;
	while (temp != NULL) {
		if (x == temp->data.key) return temp;
		if (x < temp->data.key) temp = temp->left;
		else temp = temp->right;
	}
	return NULL;
};

template <class E, class K>
bool BST<E, K>::Insert ( E& e1, 	BSTNode<E, K> *& ptr) {	   
	//私有函数：在以ptr为根的二叉搜索树中插入值为
	//e1的结点。若在树中已有含e1的结点则不插入
	if (ptr == NULL) {	   //新结点作为叶结点插入
		ptr = new BSTNode<E, K>(e1);	  //创建新结点
		if (ptr == NULL)
		{ cerr << "Out of space" << endl;  exit(1); }
		return true;
	}
	else if (e1 < ptr->data) Insert (e1, ptr->left);	 		//左子树插入
	else if (e1 > ptr->data) Insert (e1, ptr->right);		//右子树插入
    return false;	      //x已在树中,不再插入
};
template <class E, class K>
BST<E, K>::BST (K value) {
	//输入一个元素序列, 建立一棵二叉搜索树
	E x;  
	root = NULL;  RefValue = value;	     //置空树
	cout<<"请输入数据："<<endl;
	cin >> x;					     //输入数据
	while ( x.key != RefValue) {				//RefValue是一个输入结束标志
		Insert (x, root);  cin >> x;	   //插入，再输入数据
	}
};

template<class E, class K>
BSTNode<E, K>* BST<E,K>::Copy(const BSTNode<E,K> *ptr){
	if (!ptr)
		return NULL;
	if (! root)
		delete[] root;
	root = new BSTNode<E,K> (ptr->data);
	Copy(ptr->left);
	Copy(ptr->right);
	return this->root;
}
	
template<class E, class K>
void BST<E,K>::makeEmpty (BSTNode<E, K> *& ptr){
	if (!ptr) return ;
	makeEmpty(ptr->left);
	makeEmpty(ptr->right);
	delete ptr;
}

template<class E, class K>
BSTNode<E, K>* BST<E,K>::Min(BSTNode<E,K> *ptr){
	if (!ptr)
		return NULL;
	BSTNode<E,K> *temp=ptr;
	while (temp->left)
		temp=temp->left;
	return temp;
}

template<class E, class K>
BSTNode<E, K>* BST<E,K>::Max(BSTNode<E,K> *ptr){
	if (!ptr)
		return NULL;
	BSTNode<E,K> *temp=ptr;
	while (temp->right)
		temp=temp->right;
	return temp;
}


template<class E, class K>
BST<E, K> BST<E,K>::operator = (const BST<E, K>& R){
	if (this != &R){
		return BST<E,K>(Copy(R.root));
	}
	return *this;
}


template <class E, class K>
bool BST<E, K>::Remove (const K x, BSTNode<E, K> *& ptr) {
	//在以 ptr 为根的二叉搜索树中删除含 x 的结点
	BSTNode<E, K> *temp;
	if (ptr != NULL) {
		if (x < ptr->data.key) Remove (x, ptr->left);	
		//在左子树中执行删除
		else if (x > ptr->data.key) Remove (x, ptr->right);
		//在右子树中执行删除
		else if (ptr->left != NULL && ptr->right != NULL)
		{       //ptr指示关键码为x的结点，它有两个子女
			temp = ptr->right;  
			//到右子树搜寻中序下第一个结点
			while (temp->left != NULL) 
				temp = temp->left;
			ptr->data = temp->data;
			//用该结点数据代替根结点数据
			Remove (temp->data.key, ptr->right);
		}
		else {	//ptr指示关键码为x的结点有一个子女

			temp = ptr;
			if (ptr->left == NULL) ptr = ptr->right;
			else ptr = ptr->left;
			delete temp;
			return true;
		}

	}
	return false;
}; 

template<class E, class K>
void BST<E,K>::PrintTree(BSTNode<E,K> *ptr) const{
	if (!ptr) return;
	PrintTree(ptr->left);
	cout<<ptr->data<<"   ";
	PrintTree(ptr->right);
}




#endif