C++ 二叉搜索树 模板

#pragma once
#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;
template <class T> class STree;
template<class T, class Ref=T&, class Ptr=T*> class STree_iterator;
template<class T, class Ref=T&, class Ptr=T*> class STree_const_iterator;
///////////////////////////////////////////////////////////////////////////////////////
//search tree NODE
template <class T>
class TNode{
	friend class STree<T>;   //bound friend
	friend class STree_iterator<T>;
	friend class STree_const_iterator<T>;
protected:
	T data;
	TNode<T> *left, *right, *parent;
	void copy(const TNode<T> &rhs) {
		//if(rhs==NULL) {cout<<"error: no source"<<endl; return;}
		left=rhs.left;
		right=rhs.right;
		parent=rhs.parent;
		data=rhs.data;
	}
public:
	TNode() {left=NULL, right=NULL, parent=NULL;}
	TNode(const T &item, TNode<T> *lptr=NULL, TNode<T> *rptr=NULL, TNode<T> *pptr=NULL)
		 :data(item), left(lptr), right(rptr), parent(pptr) {}	
	
	TNode( const TNode<T> &rhs) { copy(rhs);	}
	TNode<T> &operator=(const TNode<T> &rhs) { copy(rhs); return *this;}
	~TNode() {}
};
///////////////////////////////////////////////////////////////////////////////////////
//binary search tree declaration
template <class T>
class STree {
	friend class STree_iterator<T>;
	friend class STree_const_iterator<T>;
protected:
	TNode<T> *root;
	int size;
	TNode<T> *GetNode(const T &item, TNode<T> *lptr, TNode<T> *rptr, TNode<T> *pptr);  //allocate storage for the current root node
	TNode<T> *copy(TNode<T> *rhs);
	void DelTree(TNode<T> *root);
	TNode<T> *findNode(const T& item) const;  //only the type of return value is different, it seems polymorphism must be sacrificed
public:
	typedef T value_type;
	typedef value_type* pointer;
	typedef STree_iterator<T, T&, T*> iterator;
	typedef STree_const_iterator<T, T&, T*> const_interator;	
	STree(void);
	STree(T *first, T *last);
	STree(const STree<T> &rhs);
	STree<T> &operator=(const STree<T> &rhs);	//support 
	 ~STree(void);
	iterator begin();//return the iterator of the node which should be firstly calls for
	iterator end();//return the last node in the tree
	int height(TNode<T> *cur) const;//calculate the height of the tree whose root is cur;
	iterator find(const T& item);//find element in the tree
	iterator insert(const T& item);//insert element in the tree
	bool erase(const T& item);//if item exist, erase it and return true
	void erase(iterator pos);/*select the minimum one (R) in the right sub tree to substitute the deleted node, 
									 connect the right subtree of R to its parent as the left sub tree 
									 connect the left subtree of the deleted node to R as the left subtree link the right 
									 subtree of the deleted node to R as its right sub tree, and the substitute the 
									 deleted node with R*/
	void erase(iterator first, iterator last);
	void LevelorderPrint();
	bool empty() const {return root==NULL;}
	int Size() const {return size;}
	TNode<T> *Root() {return root;}
};  //end of declaration of STree
///////////////////////////////////////////////////////////////////////////////////////
//binary search tree implementation
//construction and destruction 
template <class T>
STree<T>::STree(void){
	root=NULL;
	size=0;
}
template <class T> 
STree<T>::STree(T *first, T *last) {
	root=NULL;
	size=0;	
	while(first!=last) {
		insert(*first);
		++first;
	}
}
template <class T> 
STree<T>::STree(const STree<T> &rhs) {
	root=copy( rhs.Root() );
	size=rhs.Size();
}
template <class T> 
STree<T> &STree<T>::operator=(const STree<T> &rhs){
	if(this==rhs) return this;
	DelTree(root);
	root=copy(rhs.Root());
	size=rhs.Size();
	return this;
}
template <class T>
STree<T>::~STree(void){
	DelTree(root);
}
//private routines
template <class T>
TNode<T> *STree<T>::GetNode(const T &item, TNode<T> *lptr, TNode<T> *rptr, TNode<T> *pptr){
	TNode<T> *newnode=new TNode<T>(item, lptr, rptr, pptr);
	if(newnode==NULL) {cerr<<"allocate storage for new node failed!"<<endl; exit(0);}
			/*throw referenceError
				("allocate storage for new node failed!");*/
	return newnode;
}
template <class T>
TNode<T> *STree<T>::copy(TNode<T> *rhs){
	TNode<T> *lptr, *rptr, *newnode;
	if(rhs==NULL) return NULL;
	lptr=copy(rhs->left);
	rptr=copy(rhs->right);//recurisively copy
	newnode=GetNode(rhs->data, lptr, rptr, NULL);
	if(lptr!=NULL) lptr->parent=newnode;
	if(rptr!=NULL) rptr->parent=newnode;
	return newnode;//return the root of the current tree
}
template <class T>
void STree<T>::DelTree(TNode<T> *_root) {
	if(_root!=NULL){
		DelTree(_root->left);
		DelTree(_root->right);
		delete _root;
	}
}
template <class T>
TNode<T> *STree<T>::findNode(const T& item) const {
	TNode<T> *cur=root;
	while(cur!=NULL) {
		if(item==cur->data) return cur;
		else if(item<cur->data) cur=cur->left;
		else cur=cur->right;
	}
	return cur;
}
//interface 
template <class T>
int STree<T>::height(TNode<T> *cur) const {
	int r_depth, l_depth, depth;
	if(cur==NULL) depth=-1;
	else {
		r_depth=height(cur->right);
		l_depth=height(cur->left);
		depth=1+(r_depth>l_depth?r_depth:l_depth);
	}
	return depth;
}
template <class T>
typename STree<T>::iterator STree<T>::find(const T& item){
	TNode<T> *cur;
	cur=findNode(item);
	if(cur!=NULL) return STree<T>::iterator(cur, this);
	else return this->end();
}
template <class T>
typename STree<T>::iterator STree<T>::insert(const T& item) {
	TNode<T> *cur=root, *par=NULL, *newnode;
	while(cur!=NULL) {
		par=cur;
		if(item==cur->data) return STree<T>::iterator(cur, this);
		else if(item<cur->data) cur=cur->left;
		else cur=cur->right;
	}
	newnode=GetNode(item, NULL, NULL, par);
	if(par==NULL) root=newnode;
	else if(item<par->data) par->left=newnode;
	else par->right=newnode;
	++size;
	return STree<T>::iterator(newnode, this);
}
template <class T>
bool STree<T>::erase(const T& item) {
	STree<T>::iterator pos=find(item);
	if( pos!=end() ) erase(pos);
	return pos!= end();
}
template <class T>
void STree<T>::erase(typename STree<T>::iterator pos) {
	TNode<T> *del=pos.pn;
	if(del==NULL) return;
	TNode<T> *par=del->parent, *subs;
	if(del->left==NULL || del->right==NULL) {
		if(del->left==NULL) subs=del->right;
		else subs=del->left;
		if(subs != NULL) subs->parent=par;		
	}
	else {		
		subs=del->right;
		TNode<T> *temp=del;
		while(subs->left!=NULL) {
			temp=subs;
			subs=subs->left;
		}
		if(temp==del) {
			subs->left=del->left;
			subs->parent=par;
			subs->left->parent=subs;
		}
		else {
			temp->left=subs->right;	//reconstructe left tree of upstream node
			if(subs->right!=NULL) subs->right->parent=temp;
		
			subs->left=del->left;//reconstructe left tree of substitute
			subs->left->parent=subs;
			subs->right=del->right;//reconstructe right tree of substitute
			subs->right->parent=subs;
			subs->parent=par;//modify parent pointer of substitute
		}
	}
	if(par==NULL) root=subs;	
	else if(par->left==del) par->left=subs;
	else par->right=subs;
	delete del;
	--size;
}
template <class T>
void STree<T>::erase(typename STree<T>::iterator first, typename STree<T>::iterator last){
	STree<T>::iterator iter=first;
	while(iter!=last) {
		erase(iter);
		++iter;
	}
}
template <class T>
void STree<T>::LevelorderPrint() {
	queue< TNode<T> > parQ;
	queue< TNode<T> > chdQ;
	TNode<T> *cur=new TNode<T>;
	parQ.push(*root);
	while(!parQ.empty()) {
		do{
			*cur=parQ.front();
			parQ.pop();
			cout<<cur->data<<ends;
			if(cur->left!=NULL) chdQ.push(*(cur->left) );
			if(cur->right!=NULL) chdQ.push(*(cur->right) );
		}	while(!parQ.empty());
		cout<<endl;
		parQ=chdQ;
		queue< TNode<T> > empty;
		swap(chdQ, empty);
	}
	delete cur;
	cur=NULL;
}
//iterators
template <class T>
typename STree<T>::iterator STree<T>::begin(){
	TNode<T> *cur=root;
	if(cur!=NULL) 
		while(cur->left!=NULL)
			cur=cur->left;
	return STree<T>::iterator(cur, this);//this will point to the tree who call the function
}
template <class T>
typename STree<T>::iterator STree<T>::end(){//a null pointer will be returned, represent the last node
	return STree<T>::iterator(NULL, this);
}
///////////////////////////////////////////////////////////////////////////////////////
//binary search tree iterators
template<class T, class Ref, class Ptr>
class STree_iterator {//nested iterator declaration
		friend class STree<T>;
	public:
		typedef STree_iterator<T, T&, T*> iterator;
		typedef STree_iterator<T, Ref, Ptr> self;
		typedef std::bidirectional_iterator_tag iterator_category; 
		typedef T value_type;
		typedef Ref reference;
		typedef Ptr pointer;			
		typedef ptrdiff_t difference_type;		
	public:
		//constructors
		STree_iterator(){
			pn=NULL;
			tree=NULL;
		}
		STree_iterator(const STree_iterator &rhs) {//copy construction
			pn=rhs.pn;
			tree=rhs.tree;
		}
		//operators
		bool operator==(const STree_iterator &rhs) const {return pn == rhs.pn;}
		bool operator!=(const STree_iterator &rhs) const {return pn != rhs.pn;}
		reference operator*() const{
			if(pn==NULL) {cerr<<"allocate storage for new node failed!"<<endl; exit(0);}
				/*throw referenceError
					("allocate storage for new node failed!");*/
			return pn->data;
		}
		pointer operator->() const { return &( operator*() ); }
		self &operator++() { //move to the next node following inorder traversal
			TNode<T> *p;
			if(pn==NULL) {//pn point to the end, next should be the first one in the tree
				pn=tree->root;
				if(pn==NULL) { cerr<<"move on a empty tree!"<<endl; exit(0);}
					/*throw referenceError
						("allocate storage for new node failed!");*/
				while(pn->left!=NULL) pn=pn->left;
			}
			else if(pn->right != NULL) {//return the last node of the right subtree
				pn=pn->right;
				while(pn->left!=NULL) pn=pn->left;
			}
			else {//left subtree have been traversed and no right subtree, move to the parent
				p=pn->parent;
				while(p!=NULL && pn==p->right) {
					pn=p;
					p=p->parent;
				}
				pn=p;
			}
			return *this;//prefix, return current iterator (++iter)
		}
		self operator++(int) {//suffix iter++
			self temp(pn, tree);
			++(*this);//invoke ++iter;
			return temp;//return a object but the reference
		}
		self &operator--() { //move to the previous node following inorder traversal
			TNode<T> *p;
			if(pn==NULL) {//pn point to the end, next should be the last(not null) one in the tree
				pn=tree->root;
				if(pn==NULL) {cerr<<"move on a empty tree!"<<endl; exit(0);}
					/*throw referenceError
						("allocate storage for new node failed!");*/
				while(pn->right!=NULL) pn=pn->right;
			}
			else if(pn->left != NULL) {//return the last node of the left subtree
				pn=pn->left;
				while(pn->right!=NULL) pn=pn->right;
			}
			else {//left subtree have been traversed and no left subtree, move to the parent
				p=pn->parent;
				while(p!=NULL && pn==p->left) {
					pn=p;
					p=p->parent;
				}
				pn=p;
			}
			return *this;
		}
		self operator--(int) {
			self temp(pn, tree);
			--(*this);//invoke --iter;
			return temp;//return a object but the reference
		} 
	private:
		TNode<T> *pn;
		STree<T> *tree;
		STree_iterator(TNode<T> *p, STree<T> *t):pn(p), tree(t) {}
};
template<class T, class Ref, class Ptr>
class STree_const_iterator{
		friend class STree<T>;
	public:
		typedef STree_const_iterator<T, T&, T*> iterator;
		typedef STree_const_iterator<T, Ref, Ptr> self;
		typedef std::bidirectional_iterator_tag iterator_category; 
		typedef T value_type;
		typedef Ref reference;
		typedef Ptr pointer;			
		typedef ptrdiff_t difference_type;
	public:
		STree_const_iterator(){
			pn=NULL;
			tree=NULL;
		}
		STree_const_iterator(const STree_const_iterator &rhs){//copy construction
			pn=rhs.pn;
			tree=rhs.tree;
		}
		STree_const_iterator(const iterator &rhs){//copy construction
			pn=rhs.pn;
			tree=rhs.tree;
		}
		bool operator==(const STree_const_iterator &rhs) const {return pn == rhs.pn;}
		bool operator!=(const STree_const_iterator &rhs) const {return pn != rhs.pn;}
		const T &operator*() const {
			if(pn==NULL) { cerr<<"STree STree_const_iterator operator*(): NULL reference"<<endl; exit(0); }
				/*throw referenceError 
					("STree STree_const_iterator operator*(): NULL reference");*/
			return pn->data;
		}
		const pointer operator->() const { return &( operator*() ); }
		STree_const_iterator &operator++() { //move to the next node following inorder traversal
			TNode<T> *p;
			if(pn==NULL) {//pn point to the end, next should be the first one in the tree
				pn=tree->root;
				if(pn==NULL) { cerr<<"STree STree_const_iterator operator++(): tree empty"<<endl; exit(0); }
					/*throw underflowError
						("STree STree_const_iterator operator++(): tree empty");*/
				while(pn->left!=NULL) pn=pn->left;
			}
			else if(pn->right != NULL) {//return the last node of the right subtree
				pn=pn->right;
				while(pn->left!=NULL) pn=pn->left;
			}
			else {//left subtree have been traversed and no right subtree, move to the parent
				p=pn->parent;
				while(p!=NULL && pn==p->right) {
					pn=p;
					p=p->parent;
				}
				pn=p;
			}
			return *this;//prefix, return current iterator (++iter)
		}
		STree_const_iterator operator++(int) {//suffix iter++
			STree<T>::STree_const_iterator temp(pn, tree);
			++(*this);//invoke ++iter;
			return temp;//return a object but the reference
		}
		STree_const_iterator &operator--() { //move to the previous node following inorder traversal
			TNode<T> *p;
			if(pn==NULL) {//pn point to the end, next should be the last(not null) one in the tree
				pn=tree->root;
				if(pn==NULL)
					throw underflowError
					("STree STree_const_iterator operator++(): tree empty");
				while(pn->right!=NULL) pn=pn->right;
			}
			else if(pn->left != NULL) {//return the last node of the left subtree
				pn=pn->left;
				while(pn->right!=NULL) pn=pn->right;
			}
			else {//left subtree have been traversed and no left subtree, move to the parent
				p=pn->parent;
				while(p!=NULL && pn==p->left) {
					pn=p;
					p=p->parent;
				}
				pn=p;
			}
			return *this;
		}
		STree_const_iterator operator--(int) {
			STree_const_iterator temp(pn, tree);
			--(*this);//invoke --iter;
			return temp;//return a object but the reference
		}
	private:
		const TNode<T> *pn;
		const STree<T> *tree;
		STree_const_iterator(const TNode<T> *p, const STree<T> *t):pn(p), tree(t) {}
	};