bst.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

/////////////////////////////////////////////////////////
/////////二叉排序树的构建和删除以及平衡///////////////
//////////////////////////////////////////////////////
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
//#include"tree.h"
#include"stack.h"
template <class Type>class BST;
template <class Type>

class BSTNode //定义二叉排序树的结点类
{
	friend	class BST<Type>;
	public:
		BSTNode():lchild(NULL),rchild(NULL){}
		BSTNode(const Type d,BSTNode<Type> *L=NULL,BSTNode<Type> *R=NULL):data(d),rchild(R),lchild(L){}
		void SetData(Type d){data=d;}
		Type GetData(void){return data;}
		~BSTNode(){}
		BSTNode<Type> *LChild(){return lchild;}
		BSTNode<Type> *RChild(){return rchild;}
	protected:
		Type data;
		BSTNode<Type> *rchild;
		BSTNode<Type> *lchild;
};
template <class Type>//定义二叉排序树类
class BST
{
	public:
		BST():root(NULL){}//构造函数
		BST(Type value);
		~BST(){};
		//const BST & operator=(const BST& value);
		void MakeEmpty(){Destroy(root);}//使二叉排序为空
		void PrintTree()const;//输出所有结点值
		int	Find(Type x){return Find(x,root)!=NULL;}//找查二叉树中是否有结点值为X的结点
		Type Min(){return Min(root)->data;}//查找二叉排序中最小值的结点的值
		Type Max(){return Max(root)->data;}//查找二叉排序中最小值的结点的值
		void Insert(Type x){Insert(x,root);}//插入一个值为X的结点
		void Remove(Type x){Remove(x,root);}//删除一个值为X的结点
		int Height(){return Height(root);}//求树的高度
		BSTNode<Type> *GetRoot(){return root;}//返回二叉排序的根结点
		int Height(BSTNode<Type> *ptr);//求以结点ptr为根的高度
	
	/////////////平衡二叉排序树的一些操作////////////
		void SetBalance();//根据平衡系数来调节平衡
		void RotateLeft();//左单旋转的算法
		void RotateRight();//右单旋转的算法
		//void LeftBalance();//先左后右的双向旋转
		//void RightBalance();//先右后左的双向旋转
	
	protected:
		BSTNode<Type> *root;
		Type RefValue;			//数据输入停止的标志
		void Insert(Type x,BSTNode<Type> *&ptr);//子程序
		void Remove(Type x,BSTNode<Type> *&ptr);
		BSTNode<Type> *Find(Type x,BSTNode<Type> *ptr)const;
		BSTNode<Type> *Min(BSTNode<Type> *ptr);
		BSTNode<Type> *Max(BSTNode<Type> *ptr);
		void Destroy(BSTNode<Type> *point);
		
		int balance;//记录树的平衡度，其值为左子树的高度减去右子树的高度,当为正时表左高，为负时表右高
					//其绝值不能超过1，否则高得做平衡处理

		bool IsBalance();
		
	
};
template <class Type>
BSTNode<Type> *BST<Type>::Find(Type x,BSTNode<Type> *ptr)const
{
	if(ptr!=NULL)
	{
		BSTNode<Type> *temp=ptr;//从根结点开始找
		while(temp!=NULL)
		{
			if(temp->data==x)return temp;
			else if(temp->data<x)temp=temp->rchild;
			else
				temp=temp->lchild;
		}
	}
}

/*template <class Type>//二叉排序树迭代的算法
BSTNode<Type> *BST<Type>::Find(Type x,BSTNode<Type> *ptr)const
{
	if(ptr==NULL)return NULL;
	else if(x<ptr->data)return Find(x,ptr->lchild);
	else if(x>ptr->data)return Find(x,ptr->rhcild);
	else
		return ptr;
}*/

template <class Type>
void BST<Type>::Insert(Type x,BSTNode<Type> *&ptr)
{
	if(ptr==NULL)
		ptr=new BSTNode<Type>(x);
	else if(x<ptr->data)Insert(x,ptr->lchild);//在左子树插入
	else if(x>ptr->data)Insert(x,ptr->rchild);//在右子树插入
}

template <class Type>
BST<Type>::BST(Type value)
{
	Type x;;
	root=NULL;
	RefValue=value;
	cout<<"input the the node data:";
	cin>>x;
	while(x!=RefValue)
	{
		Insert(x,root);
		cout<<"input the the node data:";
		cin>>x;
	}
}

template <class Type>
void BST<Type>::Remove(Type x,BSTNode<Type> *&ptr)
{
	BSTNode<Type> *temp;
	if(ptr!=NULL)
	{
		if(ptr->data>x)Remove(x,ptr->lchild);//在左子树中删除
		else if(ptr->data<x)Remove(x,ptr->rchild);//在右子树中删除
		else if(ptr->lchild!=NULL&&ptr->rchild!=NULL)//当ptr->data==x,且ptr的左右子树都不为空时
		{
			temp=Min(ptr->rchild);//找ptr右子树中序下第一个结点
			ptr->data=temp->data;//填补上
			Remove(ptr->data,ptr->rchild);//在ptr的右子树中删除temp结点
		}
		else
		{
			temp=ptr;
			if(ptr->lchild==NULL)ptr=ptr->rchild;
			else if(ptr->rchild==NULL)ptr=ptr->lchild;
		}
	//delete temp;
	}
}

template <class Type>
BSTNode<Type> *BST<Type>::Max(BSTNode<Type> *ptr)
{
	Stack<BSTNode<Type> *> stk;
	BSTNode<Type> *temp=ptr;
	while(!stk.IsEmpty()||ptr!=NULL)//当point不为空或栈不为空时遍历
	{
		while(ptr!=NULL)
		{
			stk.Push(ptr);
			ptr=ptr->lchild;//所有左结点入栈
		}
		if(!stk.IsEmpty())
		{
			ptr=stk.Pop();
			if(ptr->data>temp->data)temp=ptr;//记住在的元素
			ptr=ptr->rchild;
		}
	}
	return temp;
}

template <class Type>
BSTNode<Type> *BST<Type>::Min(BSTNode<Type> *ptr)
{
	Stack<BSTNode<Type> *> stk;
	BSTNode<Type> *temp=ptr;
	while(!stk.IsEmpty()||ptr!=NULL)//当point不为空或栈不为空时遍历
	{
		while(ptr!=NULL)
		{
			stk.Push(ptr);
			ptr=ptr->lchild;//所有左结点入栈
		}
		if(!stk.IsEmpty())
		{
			ptr=stk.Pop();
			if(ptr->data<temp->data)temp=ptr;//记住在的元素
			ptr=ptr->rchild;
		}
	}
	return temp;
}

template <class Type>
void BST<Type>::PrintTree()const
{
	Stack<BSTNode<Type> *> stk;
	BSTNode<Type> *temp=root;
	while(!stk.IsEmpty()||temp!=NULL)//当point不为空或栈不为空时遍历
	{
		while(temp!=NULL)
		{
			stk.Push(temp);
			temp=temp->lchild;//所有左结点入栈
		}
		if(!stk.IsEmpty())
		{
			temp=stk.Pop();
			cout<<temp->data<<setw(4);
			temp=temp->rchild;
		}
	}
}

//---------------返回以结点point的高度--------------//
template <class Type>
int	BST<Type>::Height(BSTNode<Type> *point)
{
	if(point==NULL)
		return 0;
	else
	{
		int dep1=Height(point->lchild);
		int dep2=Height(point->rchild);
		if(dep1>dep2)
			return dep1+1;
		else
			return dep2+1;
	}	
}

template<class Type> 
void BST<Type>::Destroy(BSTNode<Type> *point) 
{ 
	if(point!=NULL) 
	{ 
		Destroy(point->lchild); 
		Destroy(point->rchild); 
		delete point; 
	} 
} 

template <class Type>
void BST<Type>::SetBalance()
{
	rheight=Height(root->RChild());
	lheight=Height(root->LChild());
	balance=lheight-rheight;
	if(balance<-1)		//右高，则左旋
		RotateLeft(root);
	else if(balance>1)	//左高，则右旋
		RotateRight(root);
}

template <class Type>
void BST<Type>::RotateLeft()
{
	BSTNode<Type> *newtree;			//左单旋转的算法	//当右高时可以用此算法来平衡
	newtree=root->RChild();			//新根结为原根结点的右结点
	root->RChild()=newtree->LChild();//以前根结点的右指针指向其右结点的左子树，并一同来做为新树的左子树（下一个语句）
	newtree->LChild=root;			
	root=newtree;					//根回归
}

template <class Type>			//右单旋转的算法    //当左高时可以用此算法平衡
void BST<Type>::RotateRight()
{
	BSTNode<Type> *newtree;
	newtree=root->LChild();			//新根结点的原根结的左结点
	root->LChild()=newtree->RChild();//以前根结点的左指针指向其左结点的的右子树，并一同来做新树的右子树（下一个语句）
	newtree->RChild()=root;
	root=newtree;
}

/*template <class Type>
void BST<Type>::RightBalance()
{
	

}*/