bitree.h

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

template <class T> 
class BiTree
{
private:
	BiTreeNode<T> *root;							//根结点指针

	void Destroy(BiTreeNode<T>* &t);
	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:
	//构造函数和析构函数
	BiTree(void):root(NULL){};						//构造函数
	~BiTree(void){};								//析构函数

	//构造二叉树
	void MakeTree(const T item, BiTree<T> &left, BiTree<T> &right);
	void Destroy(void);								//构造二叉树

	void PreOrder(void (*Visit)(T item));			//前序遍历	
	void InOrder(void (*Visit)(T item));			//中序遍历
	void PostOrder(void (*Visit)(T item));			//后序遍历
};

template <class T>
void BiTree<T>::Destroy(void)							//析构函数
{
	Destroy(root);
}

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

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

	if(t != NULL)
	{
		cout << t->data << "   ";				//此语句只是为了方便测试
		delete t;
	}
}

template <class T>
void BiTree<T>::MakeTree(const T item, BiTree<T> &left, BiTree<T> &right)
//构造数据域为item左子树为left右子树为right的二叉树
{
	root = new BiTreeNode<T>(item, left.root, right.root);
}

template <class T>
void BiTree<T>::PreOrder(void(*Visit)(T item))
//用Visit()函数前序遍历访问二叉树
{
	PreOrder(root, Visit);
}

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