bitreelib.h

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

template <class T>
BiTreeNode<T> *GetTreeNode(const T item, BiTreeNode<T> *left = NULL, 
							BiTreeNode<T> *right = NULL)
//由结点构造二叉树的函数
{
	BiTreeNode<T> *p;
	p = new BiTreeNode<T> (item, left, right);
	return p;
}

template <class T>
void PreOrder(BiTreeNode<T> *t, void Visit(T item))
//使用Visit(item)函数前序遍历二叉树t
{
	if(t != NULL)
	{
		Visit(t->data);
		PreOrder(t->Left(), Visit);
		PreOrder(t->Right(), Visit);
	}
}

template <class T>
void InOrder(BiTreeNode<T> *t, void Visit(T item))
//使用Visit(item)函数中序遍历二叉树t
{
	if(t != NULL)
	{
		InOrder(t->Left(), Visit);
		Visit(t->data);
		InOrder(t->Right(), Visit);
	}
}

template <class T>
void PostOrder(BiTreeNode<T> *t, void Visit(T item))
//使用Visit(item)函数后序遍历二叉树t
{
	if(t != NULL)
	{
		PostOrder(t->Left(), Visit);
		PostOrder(t->Right(), Visit);
		Visit(t->data);
	}
}

template <class T>
void Destroy(BiTreeNode<T> *&root)
{
	if((root) != NULL && (root)->Left() != NULL)
		Destroy(root->Left());

	if((root) != NULL && (root)->Right() != NULL)
		Destroy(root->Right());

//	cout << root->data << " ";				//此语句只是为了方便测试
	delete root;
}

template <class T>
void PrintBiTree(BiTreeNode<T>* &root, int level)
//二叉树root第level层结点数据域值的横向显示
{
	if(root != NULL)								//如果二叉树不空
	{
		//二叉树root->Right()第level+1层结点数据域值的横向显示
		PrintBiTree(root->Right(), level+1);		

		if(level != 0)							
		{
			//走过6*(level-1)个空格
			for(int i = 0; i < 6*(level-1); i++) cout<<" ";
				cout << "  ----";						//显示横线----
		}
		cout << root->data << endl;					//显示结点的数据域值

		//二叉树root->Left()第level+1层结点数据域值的横向显示
		PrintBiTree(root->Left(), level+1);
	}
}

template <class T>
BiTreeNode<T> *Search(BiTreeNode<T> *t, T x)
{
	BiTreeNode<T> *p;

	if(t == NULL) return NULL;				//空二叉树时的查找失败出口
	if(t->data == x) return t;				//查找成功出口

	if(t->Left() != NULL)
	{
		p = Search(t->Left(), x);			//在左子树查找
		if(p != NULL) return p;				//查找成功时结束递归过程
	}

	if(t->Right() != NULL)
	{
		p = Search(t->Right(), x);			//在右子树查找
		if(p != NULL) return p;				//查找成功时结束递归过程
	}

	return NULL;							//查找失败出口
}
/*
template <class T>
BiTreeNode<T> *Find(BiTreeNode<T>* &root, T item)
//在二叉树root中回溯查找数据元素item。找到时返回该结点指针，否则返回空
{
	if(root == NULL) return NULL;
	if(root->data == item || root->data == item)
		return root;
	BiTreeNode<T> *p;
	if((p = Find(root->Left(), item)) != NULL) return p;
	if((p = Find(root->Right(), item)) != NULL) return p;
	return NULL;								//失败时返回空使算法回溯
}
*/