binarytree.h

c++实现的二叉树

//200811220030
#include "queue_linked.h"

template<class T>
class BinaryTree;

template <class T>
class BinaryTreeNode
{
	friend class BinaryTree <T>;//声明友元
public:
	BinaryTreeNode(const T & item,BinaryTreeNode <T> *lptr=NULL,BinaryTreeNode <T> *rptr=NULL)
		:data(item),left(lptr),right(rptr){}
	BinaryTreeNode <T> * GetL() const {return left;}
	BinaryTreeNode <T> * GetR() const {return right;}
	void SetL(BinaryTreeNode <T> * l) {left=l;}
	void SetR(BinaryTreeNode <T> * r) {right=r;}
	T GetD() const {return data;}
	void SetD(T d) {data=d;}
private:
	T data;
	BinaryTreeNode <T> * left;
	BinaryTreeNode <T> * right;
};

template <class T>
class BinaryTree
{
public:
	BinaryTree():root(NULL){};
	BinaryTree(BinaryTreeNode <T> *r):root(r){};
	bool IsEmpty();
//	BinaryTreeNode <T> * GetRoot();
	BinaryTree <T> * MakeTree(T,BinaryTree <T> &,BinaryTree <T> &);
//	void BreakTree(T element,BinaryTree <T> &left,BinaryTree <T> &right);
//	int Depth();
//	int NodeNum();
//	int Clear();
	void PreOrder(void(*Visit)(BinaryTreeNode <T> *));//前序遍历
	void InOrder(void(*Visit)(BinaryTreeNode <T> *));//中序遍历
	void PostOrder(void(*Visit)(BinaryTreeNode <T> *));//后序遍历
	void LevelOrder(void(*Visit)(BinaryTreeNode <T> *));//层次遍历
	void PreCreat(BinaryTreeNode <T> *(*Visit)());
	void ClearTree();
private:
	BinaryTreeNode <T> *root;
	void PreOrder(void(*Visit)(BinaryTreeNode <T> *),BinaryTreeNode <T> *);//注：重载PreOrder，以便递归
	void InOrder(void(*Visit)(BinaryTreeNode <T> *),BinaryTreeNode <T> *);
	void PostOrder(void(*Visit)(BinaryTreeNode <T> *),BinaryTreeNode <T> *);
	void PreCreat(BinaryTreeNode <T> *(*Visit)(),BinaryTreeNode <T> * &);
	static void DeleteTree(BinaryTreeNode <T> *);//删除，由ClearTree()调用。注：类成员函数要用指针指向的，需要用static声明，why???
};

template <class T>
bool BinaryTree<T>::IsEmpty()
{
	return (root==NULL);
}

template <class T>
BinaryTree <T> * BinaryTree<T>::MakeTree(T element,BinaryTree <T> &left,BinaryTree <T> &right)
//将element、left、right这三棵不同的树合并成一棵新树
{
	root=new BinaryTreeNode <T> (element,left.root,right.root);//创建新树
	left.root=right.root=NULL;//阻止访问left和right
}

template <class T>
void BinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode <T> *))
{
	PreOrder(Visit,root);
}

template <class T>
void BinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode <T> *),BinaryTreeNode <T> *node)
{
	if(node!=NULL)
	{
		Visit(node);
		PreOrder(Visit,node->left);
		PreOrder(Visit,node->right);
	}
}

template <class T>
void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode <T> *))
{
	InOrder(Visit,root);
}

template <class T>
void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode <T> *),BinaryTreeNode <T> *node)
{
	if(node!=NULL)
	{
		InOrder(Visit,node->left);
		Visit(node);
		InOrder(Visit,node->right);
	}
}

template <class T>
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode <T> *))
{
	PostOrder(Visit,root);
}

template <class T>
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode <T> *),BinaryTreeNode <T> *node)
{
	if(node!=NULL)
	{
		PostOrder(Visit,node->left);
		PostOrder(Visit,node->right);
		Visit(node);
	}
}

template <class T>
void BinaryTree<T>::PreCreat(BinaryTreeNode <T> *(*Creat_fun)())
{
	if(root!=NULL)
	{
		cerr <<"Already created!Creating aborted!!!"<<endl;
		return;
	}
	PreCreat(Creat_fun,root);
}

template <class T>
void BinaryTree<T>::PreCreat(BinaryTreeNode <T> *(*Creat_fun)(),BinaryTreeNode <T> * & node)
//注：此处第二个参数引用指针
{
	node=Creat_fun();
	if(!node)
	{
		return;
	}
	PreCreat(Creat_fun,node->left);
	PreCreat(Creat_fun,node->right);
}

template <class T>
void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode <T> *))
{
	Queue_linked <BinaryTreeNode <T> *> q;
	BinaryTreeNode <T> *t;
	t=root;
	while(t)
	{
		Visit(t);
		if(t->left)
			q.En(t->left);//左孩子入队
		if(t->right)
			q.En(t->right);//右孩子入队
		if(!q.De(t))
		{
			return;
		}
	}
}

template <class T>
void BinaryTree<T>::DeleteTree(BinaryTreeNode <T> *p)
{
	delete p;
}

template <class T>
void BinaryTree<T>::ClearTree()
{
	PostOrder(DeleteTree);
	root=NULL;
}