btree.h

关于数据结构中二叉树的实验源代码

// BTree.cpp : Defines the entry point for the console application.
//

#include "iostream.h"



template<class T>
class BTree;

template<class T>
class BTNode
{
	friend class BTree<T>;
	friend void Visit(BTNode<T> *p);
	friend BTNode<T>* Find(BTNode<T>* &root,T item);
	private:
		T element;
		BTNode<T> *lc,*rc;
	public:
		BTNode(){lc=rc=NULL;}
		BTNode(const T e)//////////////////////构造函数
		{
			element=e;
			lc=rc=NULL;
		}
		BTNode(const T e,BTNode<T> *l,BTNode<T> *r)//////////////////////构造函数
		{
			element=e;
			lc=l;
			rc=r;
		}
		BTNode<T>* &Left(void)////////////////////////////////返回左指针
		{ return lc; }
		BTNode<T>* &Right(void)//////////////////////////////返回右指针
		{ return rc; }
};

template<class T>
void Visit(BTNode<T> *p)////////////////返回p所指的结点
{
	cout<<p->element<<"  ";
}

template<class T>
class BTree
{
	private:
		BTNode<T> *root;
		void PreOrder(BTNode<T> *t);
		void InOrder(BTNode<T> *t);
		void PostOrder(BTNode<T> *t);
	public:
		BTree(void){root=NULL;}//////////////////////构造函数
		BTree(BTNode<T> *p){root=p;}//////////////////////构造函数
		~BTree(){}
		int IsEmpty()const;/////////////////////////////////判定树是否为空
		T Root(void)const;/////////////////////////////返回根接点
		void PreOrder(void)///////////////////////////////先根序列
		{ PreOrder(root);}///////////////////////中根序列
		void InOrder(void)
		{ InOrder(root);}
		void PostOrder(void)
		{ PostOrder(root);}
		BTNode<T>* &BTRoot(void)
		{return root;} 

};

template<class T>
int BTree<T>::IsEmpty()const
{
	return root==NULL;
}

template<class T>
T BTree<T>::Root(void)const
{
	if IsEmpty() return 0;
	return root->element;
}

template<class T>
void BTree<T>::PreOrder(BTNode<T> *t)
{
	if(t!=NULL)
	{
		Visit(t);
		PreOrder(t->lc);
		PreOrder(t->rc);
	}
}

template<class T>
void BTree<T>::InOrder(BTNode<T> *t)
{
	if(t!=NULL)
	{
		InOrder(t->lc);
		Visit(t);
		InOrder(t->rc);
	}
}

template<class T>
void BTree<T>::PostOrder(BTNode<T> *t)
{
	if(t!=NULL)
	{
		PostOrder(t->lc);
		PostOrder(t->rc);
		Visit(t);
	}
}