#include <iostream> #include <stdlib.h> using namespace std; 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;} }; template <class E,class K> class BST{ public: BST():root(NULL){} BST(K value); ~BST(){} bool Search(const K x) const{ return(Search(x,root)!=NULL)?true:false; } BST<E,K>&operator=(const BST<E,K>& R); void makeEmpty(){makeEmpty(root);root=NULL;} void PrintTree()const{PrintTree(root);} E Min(){return Min(root)->data;} E Max(){return Max(root)->data;} bool Insert(const E& el){return Insert(el,root);} bool Remove(const K x){return Remove(x,root);} private: BSTNode<E,K> *root; K RefValue; BSTNode<E,K> *Search(const K x,BSTNode<E,K> *ptr) const; 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) const; BSTNode<E,K> *Max(BSTNode<E,K> *ptr) const; bool Insert(const E& el,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) const { //私有递归函数,在以ptr为根的二叉树中搜索含x的结点,若找到则返回地址,否则返回NULL if(ptr==NULL) return NULL; else if(x<ptr->data) return Search(x,ptr->left); else if(x>ptr->data) return Search(x,ptr->right); else return ptr; } //使用插入算法前应先用搜索算法检测有没有 template <class E,class K> bool BST<E,K>::Insert(const E &el, BSTNode<E, K>& *ptr) { //私有函数,在以ptr为根的二叉搜索树中插入所含值为el的结点 if(ptr==NULL){ //当ptr为NULL时即为我们要找的插入的地方 ptr=new BSTNode<E,K>(el); if(ptr==NULL){ cerr<<"Out of space"<<endl; exit(1); } return true; } //当ptr不为NULL时它一定指向一颗子树的根 else if(el<ptr->data) Insert(el,ptr->left); else if(el>ptr->data) Insert(el,ptr->right); else return false; } template <class E,class K> BST<E,K>::BST(K value){ //输入一个元素序列,建立一颗二叉搜索树 E x; root=NULL; RefValue=value; cin>>x; while(x.key!=RefValue){ //RefValue是一个输入结束标志,输入序列以输入一个结束标志value结束 Insert(x,root); cin>>x; } }; template <class E,class K> bool BST<E,K>::Remove(const K x, BSTNode<E, K>* &ptr) { //删除结点时,必须把断开的二叉链表重新链接,同时确保二叉搜索树性质不丢失、同时防止重链后树高度增加。 BSTNode<E,K> *temp; if(ptr!=NULL){ if(x<ptr->data) Remove(x,ptr->left); else if(x>ptr->data) Remove(x,ptr->right); else if(ptr->left!=NULL && ptr->right!=NULL){ //ptr指示关键码即为所寻,它有两个子女 temp=ptr->right; while(temp->left!=NULL) temp=temp->left; //到右子女搜索中序下第一个结点(关键码最小) ptr->data=temp->data; //两个结点互相交换关键码、再删了那个结点 Remove(ptr->data,ptr->right); } else{ //ptr指示关键码即为所寻,它有一个子女,拿该子女顶替它;或者它是叶结点,直接删除即可 temp=ptr; if(ptr->left==NULL) ptr=ptr->right; else ptr=ptr->left; delete temp; return true; } } return false; //ptr为空指针或者找不到关键码为x的结点 }