二叉查找树.h

一个显示二叉树结构和相关算法的小程序,重在结构

#ifndef BST_H
#define BST_H

template<class Elem>class BinNode
{
	private:
		Elem it;
		BinNode<Elem>* lc;
		BinNode<Elem>* rc;
	public:
		Elem val(){return it;}
		inline BinNode<Elem>* left(){return lc;}
		inline BinNode<Elem>* right(){return rc;}
		BinNode(){lc=rc=NULL;}
		BinNode(Elem e,BinNode<Elem>* l=NULL,BinNode<Elem>* r=NULL)
		{
			it=e;
			lc=l;
			rc=r;
		}
		void setVal(Elem e){it=e;}
		void setRight(BinNode<Elem>* r){rc=r;}
		void setLeft(BinNode<Elem>* l){lc=l;}
};

template<class Elem>class BST
{
	private:
		BinNode<Elem>* root;
		int nodecount;
		void clearhelp(BinNode<Elem>* subroot)
		{
			if(subroot==NULL)return;
			clearhelp(subroot->left());
			clearhelp(subroot->right());
			delete subroot;
		}

		BinNode<Elem>* inserthelp(BinNode<Elem>* subroot,const Elem& e)
		{
			if(subroot==NULL)
				return (new BinNode<Elem>(e,NULL,NULL));
			if(e < subroot->val())subroot->setLeft(inserthelp(subroot->left(),e));
			else subroot->setRight(inserthelp(subroot->right(),e));
			return subroot;
		}

		BinNode<Elem>* deletemin(BinNode<Elem>* subroot,BinNode<Elem>*& min){
			if(subroot->left()==NULL){
				min=subroot;
				return subroot->right();
			}
			else {
				subroot->setLeft(deletemin(subroot->left(),min));
				return subroot;
			}
		}

		BinNode<Elem>* removehelp(BinNode<Elem>* subroot,const Elem& K,BinNode<Elem>*& t){
			if(subroot==NULL)return NULL;
			if(K<subroot->val())subroot->setLeft(removehelp(subroot->left(),K,t));
			else if(K>subroot->val())subroot->setRight(removehelp(subroot->right(),K,t));
			else{
				BinNode<Elem>* temp;
				t=subroot;
				if(subroot->left()==NULL)subroot=subroot->right();
				else if(subroot->right()==NULL)subroot=subroot->left();
				else{
					subroot->setRight(deletemin(subroot->right(),temp));
					Elem te=subroot->val();
					subroot->setVal(temp->val());
					temp->setVal(te);
					t=temp;
				}
			}
			return subroot;
		}

		bool findhelp(BinNode<Elem>* subroot,const Elem& K,Elem& e)const
		{
			if(subroot==NULL)return false;
			if(K<subroot->val())return findhelp(subroot->left(),K,e);
			if(K>subroot->val())return findhelp(subroot->right(),K,e);
			e=subroot->val();
			return true;
		}

		void printhelp(BinNode<Elem>* subroot,int level)const
		{
			if(subroot==NULL)return;
			printhelp(subroot->left(),level+1);
			for(int i=0;i<level;i++)cout<<"  ";
			cout<<subroot->val()<<endl;
			printhelp(subroot->right(),level+1);
		}

	public:
		BST(){root=NULL;nodecount=0;}
		~BST(){clearhelp(root);}
		void clear(){clearhelp(root);root=NULL;nodecount=0;}
		bool insert(const Elem& e){
			root=inserthelp(root,e);
			nodecount++;
			return true;
		}
		bool remove(const Elem& K,Elem& e){
			BinNode<Elem>* t=NULL;
			if(t==NULL)return false;
			e=t->val();
			nodecount--;
			delete t;
			return true;
		}
		bool removeAry(Elem& e){
			if(root==NULL)return false;
			BinNode<Elem>* t;
			root=deletemin(root,t);
			e=t->val();
			delete t;
			nodecount--;
			return true;
		}
		bool find(const Elem& K,Elem& e)const
		{return findhelp(root,K,e);}
		int size(){return nodecount;}
		void print(){
			if(root==NULL)cout<<"The BST is empty.\n";
			else printhelp(root,0);
		}
};
#endif