bisearchtree.h

包含各种测试,查找和算法等代码,如冒泡算法,树的遍历,链表,队列,堆栈等

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);	//删除

	//前序、中序和后序遍历，访问操作为Visit()函数
	void PreOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
	void InOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
	void PostOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
public:
//构造函数和析构函数
	BiSearchTree():root(NULL){};	//注意：生成的二叉排序树不带根结点
	~BiSearchTree(){};

	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)	//取左孩子结点
		{return root != NULL ? current->Left() : NULL;}
	BiTreeNode<T>* &RightChild(BiTreeNode<T>* &current)	//取右孩子结点
		{return root != NULL ? current->Right() : NULL;}

	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)
{
	if(root != NULL)
	{
		BiTreeNode<T> *temp = root;
		while(temp != NULL)
		{
			if(temp->data == item) return temp;			//查找成功

			if(temp->data < item) 
				temp = temp->Right();				//在右子树继续
			else 
				temp = temp->Left();				//在左子树继续
		}
	}
	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(item < ptr->data) 
		Insert(ptr->Left(), item);					//在左子树递归
	else if(item > ptr->data) 
		Insert(ptr->Right(), item);					//在右子树递归
}

template <class T>
void BiSearchTree<T>::Delete(BiTreeNode<T>* &ptr, const T &item)
{
	BiTreeNode<T> *temp;
	if(ptr != NULL)
	{
		if(item < ptr->data) Delete(ptr->Left(), item);
		else if(item > ptr->data) Delete(ptr->Right(), item);
		else if(ptr->Left() != NULL && ptr->Right() != NULL)
		//要删除结点左右子树均存在的情况
		{
			BiTreeNode<T> *min;
			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();	
			else if(ptr->Right() == NULL) 
				ptr = ptr->Left();

			delete temp;					//删除等于item的结点
		}
	}
}

template <class T>
void BiSearchTree<T>::PreOrder(BiTreeNode<T>* &t, void(*Visit)(T item))
{
	if(t != NULL)
	{
		Visit(t->data);
		PreOrder(t->Left(),Visit);
		PreOrder(t->Right(),Visit);
	}
}

template <class T>
void BiSearchTree<T>::InOrder(BiTreeNode<T>* &t, void (*Visit)(T item))
{
	if(t!=NULL)
	{
		InOrder(t->Left(),Visit);
		Visit(t->data);
		InOrder(t->Right(),Visit);
	}
}

template <class T>
void BiSearchTree<T>::PostOrder(BiTreeNode<T>* &t, void (*Visit)(T item))
{
	if(t!=NULL)
	{
		PostOrder(t->Left(),Visit);
		PostOrder(t->Right(),Visit);
		Visit(t->data);
	}
}

template <class T>
istream &operator>> (istream &in, BiSearchTree<T>* &tree)
{
	T item;
	in >> item;
	while(item != StopMark)
	{
		tree.Insert(item);
		in >> item;
	}
	return in;
}