bitree.h

这个是二叉排序树。能通过二叉树对一组数字进行排序。

#include"iostream.h"
template<class T>
class BiSearchTree;
template<class T>
class BiTreeNode
{
	friend class BiSearchTree<T>;
private:
	T data;
	BiTreeNode<T>* left;
	BiTreeNode<T>* right;
public:
	BiTreeNode()
	{
		left=right=NULL;
	}
	~BiTreeNode(){};
	BiTreeNode(const T&item)
	{
		data=item;
		left=right=NULL;
	}
	BiTreeNode<T>*& Left()
	{
		return left;
	}
	BiTreeNode<T>*& Right()
	{
		return right;
	}
};
template<class T>
class BiSearchTree
{
	friend istream&operator>>(istream&in,BiSearchTree<T>*&tree);
private:
	BiTreeNode<T>* root;
	void Insert(BiTreeNode<T>*&ptr,const T& item);
	void Delete(BiTreeNode<T>*&ptr,const T& item);
	void PreOrder(BiTreeNode<T>*&ptr,void(*Visit)(T item))
	{
		if(ptr!=NULL)
		{
			Visit(ptr->data);
			if(ptr->left!=NULL)
				PreOrder(ptr->left,Visit);
			if(ptr->right!=NULL)
				PreOrder(ptr->right,Visit);
		}
	}
	void InOrder(BiTreeNode<T>*&ptr,void(*Visit)(T item))
	{
		if(ptr!=NULL)
		{	
			if(ptr->left!=NULL)
				InOrder(ptr->left,Visit);
			Visit(ptr->data);
			if(ptr->right!=NULL)
				InOrder(ptr->right,Visit);
		}
	}
	void PostOrder(BiTreeNode<T>*&ptr,void(*Visit)(T item))
	{
		if(ptr!=NULL)
		{
			if(ptr->left!=NULL)
				PostOrder(ptr->left,Visit);
			if(ptr->right!=NULL)
				PostOrder(ptr->right,Visit);
			Visit(ptr->data);
		}
	}
public:
	BiSearchTree():root(NULL)
	{};
	~BiSearchTree()
	{
		delete root;
	}
	BiTreeNode<T>*Find(const T&item);
	void Insert(const T&item)
	{
		Insert(GetRoot(),item);
	}
	void Delete(const T&item)
	{
		Delete(GetRoot(),item);
	}
	BiTreeNode<T>*& GetRoot()
	{
		return root;
	}
	BiTreeNode<T>& LeftChild(BiTreeNode<T>*&current)
	{
		if(root==NULL)
			return NULL;
		return current->Left();
	}
	BiTreeNode<T>& RightChild(BiTreeNode<T>*&current)
	{
		if(root==NULL)
			return NULL;
		return current->Right();
	}
	void PreOrder(void (*Visit)(T item))
	{
		PreOrder(root,Visit);
	}
	void InOrder(void (*Visit)(T item))
	{
		InOrder(root,Visit);
	}
	void PostOrder(void (*Visit)(T item))
	{
		PostOrder(root,Visit);
	}
};
template<class T>
BiTreeNode<T>* BiSearchTree<T>::Find(const T&item)
{
	BiTreeNode<T>* ptr=root;
	while(ptr!=NULL)
	{
		if(ptr->data==item)
			return ptr;
		if(ptr->data>item)
			ptr=ptr->left;
		else
			ptr=ptr->right;
	}
	return NULL;
}
template<class T>
void BiSearchTree<T>::Insert(BiTreeNode<T>*&ptr,const T&item)
{
	if(ptr==NULL)
		ptr=new BiTreeNode<T>(item);
	else
	{
		if(ptr->data>item)
			Insert(ptr->left,item);
		if(ptr->data<=item)
			Insert(ptr->right,item);
	}
}
//非递归算法
template<class T>
void BiSearchTree<T>::Delete(BiTreeNode<T>*&ptr,const T&item)
{
	BiTreeNode<T>*temp,*curr1,*curr2;
	if(ptr!=NULL)
	{
		curr1=curr2=ptr;
		while(curr2->data!=item&&curr2!=NULL)
		{
			curr1=curr2;
			if(curr2->data>item)
				curr2=curr2->Left();
			if(curr2->data<item)
				curr2=curr2->Right();
		}
		if(curr2==NULL)
		{
			cout<<"找不到此元素!"<<endl;
			return;
		}
		if(curr2->Left()!=NULL&&curr2->Right()!=NULL)
		{
			BiTreeNode<T>*min=curr2->Right();
			while(min->Left()!=NULL)
				min=min->Left();
			T num=min->data;
			Delete(curr2,min->data);
			curr2->data=num;
		}
		else
		{
			if(curr2==curr1->Left())
			{
				if(curr2->Left()==NULL)
					curr1->left=curr2->Right();
				if(curr2->Right==NULL)
					curr1->left=curr2->Left();
				else
					curr1->left=NULL;
			}
			else
			{
				if(curr2->Left()==NULL)
					curr1->right=curr2->Right();
				else if(curr2->Right==NULL)
					curr1->right=curr2->Left();
				else
					curr1->right=NULL;
			}
			delete curr2;
		}
	}
}
//递归算法
/*template<class T>
void BiSearchTree<T>::Delete(BiTreeNode<T>*&ptr,const T&item)
{
	BiTreeNode<T>*temp;
	if(ptr!=NULL)
	{
		if(ptr->data>item) Delete(ptr->Left(),item);
		if(ptr->data<item) Delete(ptr->Right(),item);
		if(ptr->Left()!=NULL&&ptr->Right()!=NULL)
		{
			BiTreeNode<T>*min=ptr->Right();
			while(min->Left()!=NULL)
				min=min->Left();
			ptr->data=min->data;
			Delete(ptr->Right(),min->data);
		}
		else
		{
			temp=ptr;
			if(ptr->Left()==NULL)
				ptr=ptr->Right();
			if(ptr->Right==NULL)
				ptr=ptr->Left();
			delete temp;
		}
	}
}*/