binarytree.h

数据结构-遍历实验

#include<iostream.h>
#include"Stack_SingleList.h"


template<class type> class BinTree;
template<class type> class BinTreeNode
{
	friend class BinTree<type>; 
	public:
		BinTreeNode(type item,BinTreeNode<type> * left=NULL,BinTreeNode<type> * right=NULL):data(item),leftChild(left),rightChild(right){};    //
	private:
		BinTreeNode<type> * leftChild, * rightChild;
		type data;
};


template<class type> class BinTree
{
	public:
		BinTree()
		{
			cout<<endl<<"输入一个用于表示结束的结束符 : ";
			cin>>RefValue;
			root=NULL;
		    crt_BinTree(root);
		};
		///////////////////////////////////////
		void rec_InOrder(BinTreeNode<type> *);
		void InOrder(BinTreeNode<type> *);
		//////////////////////////////////////
		virtual ~BinTree(){destroy(root);};                    
	   
		int Size(BinTreeNode<type> * t);

		BinTreeNode<type> * GetRoot()
		{
			return root;
		}			  
		
	private:
		BinTreeNode<type> * root;
		type RefValue;
		crt_BinTree(BinTreeNode<type> *&);	
		void destroy(BinTreeNode<type> * current);    
		
};


template<class type>void BinTree<type>::destroy(BinTreeNode<type> * current)
{
	if(current!=NULL)
	{
		destroy(current->leftChild);
		destroy(current->rightChild);
		delete current;
		//cout<<endl<<"成功的销毁二叉树";
	}
	
};

template<class type> BinTree<type>::crt_BinTree(BinTreeNode<type> *& current)
{   
	type ch;
	cout<<endl<<"请输入结点值(结束符为 "<<RefValue<<" )";
	cin>>ch;
	if(ch!=RefValue)
	{
		current=new BinTreeNode<type>(ch);
		crt_BinTree(current->leftChild);
		crt_BinTree(current->rightChild);
	}
	else current=NULL;
}

template<class type>int BinTree<type>::Size(BinTreeNode<type> * t)
{
	if(t==NULL)
		return 0;
	else return 1+Size(t->leftChild)+Size(t->rightChild);
}


///////////////////////////////////////////////////////////////////////////////////////////
// 中序递归遍历
template<class type>void BinTree<type>::rec_InOrder(BinTreeNode<type> * current)
{
	if(current!=NULL)
	{
		InOrder(current->leftChild);
		cout<<"->"<<current->data;
		InOrder(current->rightChild);
	}

}

//////////////////////////////////////////////////////////////////////////////////////////
//　利用栈的非递归中序遍历

template<class type> void BinTree<type>::InOrder(BinTreeNode<type> * current)
{
	int top=-1;
	Stack<BinTreeNode<type> *> s;
	while(current!=NULL||!s.IsEmpty())
	{
		while(current!=NULL)
		{
			s.Push(current);
			current=current->leftChild;
		}
		if(!s.IsEmpty())
		{
			current=s.Pop();
			cout<<"->"<<current->data;
			current=current->rightChild;


		}
	}

}
////////////////////////////////////////////////////////////////////////////////////////