bitree.h

数据结构的一些教程....比较适于初学者

//二叉树模板类BiTree<T>的定义与实现(P.190)
#include "iostream.h"
#include "stdlib.h"
#include "BiTreeNode.h"

template<class T>
class BiTree
{
protected:
	BiTreeNode<T> *root;    //根结点指针
	//把三个遍历方法的算法封装在私有段
	//用visi访问函数前序遍历以t为根的二叉树
//	void PreOrder(BiTreeNode<T>* &t,void(*visit)(T item));
	//用visi访问函数中序遍历以t为根的二叉树
//	void InOrder(BiTreeNode<T>* &t,void(*visit)(T item));
	//用visi访问函数后序遍历以t为根的二叉树
//	void PostOrder(BiTreeNode<T>* &t,void(*visit)(T item)); 
public:
	BiTree()         //构造函数空二叉树
	{  root=NULL;  }    
	~BiTree()        //析构函数
	{   }
    //由左右子树及根结点数据建立二叉树
	void MakeTree(const T &item, BiTree<T> &left,BiTree<T> &right);
    BiTreeNode<T> * &Getroot(void)
	{ return root; }
	void PreOrder(BiTreeNode<T>* &t,void(*visit)(T item));
	//用visi访问函数中序遍历以t为根的二叉树
	void InOrder(BiTreeNode<T>* &t,void(*visit)(T item));
	//用visi访问函数后序遍历以t为根的二叉树
	void PostOrder(BiTreeNode<T>* &t,void(*visit)(T item));
};

//由左右子树及根结点数据建立二叉树
template<class T>
void BiTree<T>::MakeTree(const T &item, BiTree<T> &left,BiTree<T> &right)
{  root=new BiTreeNode<T>(item,left.Getroot(),right.Getroot());  }
/*
template<class T>
void BiTree<T>::MakeTree(const T &item, BiTree<T> &left,BiTree<T> &right)
{  root=new BiTreeNode<T>(item,left.root,right.root);  }
*/

//template<class T>
//void BiTree<T>::PreOrder(void(*visit)(T item))  //公有成员函数
//{  
//	PreOrder(root,visit);   //调用相应的私有成员函数
//}

template<class T>
void BiTree<T>::PreOrder(BiTreeNode<T>* &t,void(*visit)(T item)) //私有成员函数
{
	if(t!=NULL)
	{
		visit(t->GetData());      //访问根结点
		PreOrder(t->Left(),visit);//递归调用本成员函数遍历左子树
		PreOrder(t->Right(),visit);//递归调用本成员函数遍历右子树
	}
}

//template<class T>
//void BiTree<T>::InOrder(void(*visit)(T item))  //公有成员:中序遍历
////{ 
//	InOrder(root,visit); //调用相应的私有成员函数 
//}

template<class T>
void BiTree<T>::InOrder(BiTreeNode<T>* &t,void(*visit)(T item)) //私有成员
{
	if(t!=NULL)
	{		
		InOrder(t->Left(),visit);  //递归调用本成员函数遍历左子树
		visit(t->GetData());      //访问根结点
		InOrder(t->Right(),visit);  //递归调用本成员函数遍历右子树
	}
}

//template<class T>
//void BiTree<T>::PostOrder(void(*visit)(T item))  //公有成员
//{
//	PostOrder(root,visit);   //调用相应的私有成员函数
//}

template<class T>
void BiTree<T>::PostOrder(BiTreeNode<T>* &t,void(*visit)(T item))//私有成员
{
	if(t!=NULL)
	{		
		PostOrder(t->Left(),visit);    //递归调用本成员函数遍历左子树
		PostOrder(t->Right(),visit);   //递归调用本成员函数遍历右子树
		visit(t->GetData());        //访问根结点
	}
}