tree.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

/////////////////////////// 
//    // 
//   二叉树数据结构  BinTree.h       // 
//    // 
////////////////////////// 
#include"queue.h"
#include"stack.h"
#include<iostream.h> 
template<class Type>class BinTree; 
template<class Type> //定义二叉树的结点类
class TreeNode 
{ 
  public: 
	friend class BinTree<Type>; 
	TreeNode():lchild(NULL),rchild(NULL){} //构造
	Type data; 
	TreeNode *lchild;  //左，右子树 
	TreeNode *rchild; 
}; 

template<class Type> //定义二叉树类
class BinTree 
{ 
	friend void BinTree_PRE(BinTree<Type>& BinTreeOPP);  //友元函数 
	friend void BinTree_INO(BinTree<Type>& BinTreeOPP); 
	friend void BinTree_POS(BinTree<Type>& BinTreeOPP); 
	friend void BinTree_Destroy(BinTree<Type>& BinTreeOPP); 
public: 
	BinTree():root(NULL){} 
	void CreatTree();               //创建二叉树,主过程 
	void CreatTree(TreeNode<Type>* child,int k); //子过程 
	//void CreatTree(TreeNode<Type>	*a,int n);//以数组的中元素建立二叉树
	void PreOrder(TreeNode<Type> *point);     //先序遍历二叉树 
	void PreOrderN(TreeNode<Type> *point);		//先序非递归
	void InOrder(TreeNode<Type> *point);  //中序遍历二叉树 
	void InOrderN(TreeNode<Type> *point);	//中序非递归
	void PostOrder(TreeNode<Type> *point);  //后序遍历二叉树 
	void PostOrderN(TreeNode<Type> *point);	//后序非递归
	void Destroy(TreeNode<Type> *point);     //销毁二叉树 
	bool IsEmpty(); 
	int Depth(TreeNode<Type> *point);//返回以point根结点的子树的深度
	int CountNode(TreeNode<Type> *point);
	//int CountX(TreeNode<Type> *point);						//返回树中值为X的结点的个数
	//TreeNode<Type> *Max(TreeNode<Type> *point);				//返回树中值中最大值的结点
	void DelSubTree(TreeNode<Type> *&t);
	TreeNode<Type> *GetRoot(){return root;}
	void CountLeaf(TreeNode<Type> *&t,int &count);
protected: 
	TreeNode<Type>* root; 
	
}; 


template<class Type> 
void BinTree<Type>::CreatTree() 
{ 
	CreatTree(root,1); 
} 

template<class Type> 
void BinTree<Type>::CreatTree(TreeNode<Type>* child,int k) 
{ 
	TreeNode<Type>* point; 
	point=new TreeNode<Type>; 
	cout<<"输入节点数据项 :"; 
	cin>>point->data; 
	switch(k) 
	{ 
		case 1: root=point; break; 
		case 2: child->lchild=point;break; 
		case 3: child->rchild=point;break; 
	} 
	char temp; 
	cout<<"该"<<point->data<<"节点是否有左子树 Y / 任意键 :"; 
	cin>>temp; 
	if(temp=='y'||temp=='Y') 
	{ 
		CreatTree(point,2); 
	} 
	cout<<"该"<<point->data<<"节点是否有右子树 Y / 任意键 :"; 
	cin>>temp; 
	if(temp=='y'||temp=='Y') 
	{ 
		CreatTree(point,3); 
	} 
} 

template<class Type> 
void BinTree<Type>::PreOrder(TreeNode<Type> *point) 
{ 
	if(point!=NULL) 
	{ 
		cout<<" "<<point->data; 
		PreOrder(point->lchild); 
		PreOrder(point->rchild); 
	} 
} 
template<class Type>
void BinTree<Type>::PreOrderN(TreeNode<Type> *point)	//先序的非递归算法
{
	Stack<TreeNode<Type> *> stk;
	while(!stk.IsEmpty()||point!=NULL)//当point不为空或栈不为空时遍历
	{
		while(point!=NULL)
		{
			cout<<point->data<<setw(4);//访问结点
			if(point->rchild!=NULL)
				stk.Push(point->rchild);//右结点入栈
			point=point->lchild;		//遍历左结点
		}
		if(!stk.IsEmpty())point=stk.Pop();
	}
}

template<class Type> 
void BinTree<Type>::InOrder(TreeNode<Type> *point) 
{ 
	if(point!=NULL) 
	{   
		InOrder(point->lchild); 
		cout<<" "<<point->data; 		
		InOrder(point->rchild); 
	}	 
} 
template<class Type>
void BinTree<Type>::InOrderN(TreeNode<Type> *point)//中序的非递归
{
	Stack<TreeNode<Type> *> stk;
	while(!stk.IsEmpty()||point!=NULL)//当point不为空或栈不为空时遍历
	{
		while(point!=NULL)
		{
			stk.Push(point);
			point=point->lchild;//所有左结点入栈
		}
		if(!stk.IsEmpty())
		{
			point=stk.Pop();
			cout<<point->data;//出栈并访问
			point=point->rchild;
		}
	}
}

template<class Type> 
void BinTree<Type>::PostOrder(TreeNode<Type> *point) 
{ 
	if(point!=NULL) 
	{  
		PostOrder(point->lchild); 
		PostOrder(point->rchild); 		
		cout<<" "<<point->data; 
	} 
} 

template<class Type>
void BinTree<Type>::PostOrderN(TreeNode<Type> *point)//有点问题
{
	Stack<TreeNode<Type> *>stk;
	while(!stk.IsEmpty()||point!=NULL)
	{
		while(point!=NULL)
		{
			stk.Push(point);
			if(point->lchild!=NULL)
				point=point->lchild;
			else
				point=point->rchild;
		}
		point=stk.Pop();
		cout<<point->data<<setw(4);
		TreeNode<Type> *p;
		p=stk.GetTopValue();
		while(!stk.IsEmpty()&&(p->rchild==point))
		{
			point=stk.Pop();
			cout<<point->data<<setw(3);
			p=stk.GetTopValue();
		}
		if(!stk.IsEmpty())
			p=stk.GetTopValue()->rchild;
		else
			point=NULL;
	}
}

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

template<class Type>
int BinTree<Type>::Depth(TreeNode<Type> *point)
{
	if(point==NULL)
		return 0;
	else
	{
		int dep1=Depth(point->lchild);
		int dep2=Depth(point->rchild);
		if(dep1>dep2)
			return dep1+1;
		else
			return dep2+1;
	}	
}

template<class Type>
int BinTree<Type>::CountNode(TreeNode<Type> *point)
{
	if(point==NULL)
		return 0;
	else
		return CountNode(point->rchild)+CountNode(point->lchild)+1;
}

template<class Type> 
void BinTree<Type>::Destroy(TreeNode<Type> *point) 
{ 
	if(point!=NULL) 
	{ 
		Destroy(point->lchild); 
		Destroy(point->rchild); 
		delete point; 
	} 
} 
template <class Type>
void BinTree<Type>::DelSubTree(TreeNode<Type> *&t)
{
	if(t==NULL)return;
	TreeNode<type> *q=t->Left();
	TreeNode<type> *p;
	while(q!=NULL)
	{
		p=q->Right();
		DelSubTree(q);
		q=p;
	}
	delete t;
}

template <class Type>
void BinTree<Type>::CountLeaf(TreeNode<Type> *&t,int &count)//计算二叉树的叶子结点的个数,并存于count中
{
	if(t!=NULL)
	{
		CountLeaf(t->Left(),count);
		CountLeaf(t->Right(),count);
		if(t->Left()==NULL&&t->Right()==NULL)
			count++;
	}
}