binary.cpp

二叉树的遍历（前序中序算法的应用

#include<iostream.h>
#include<stdlib.h>
#include"LinkStack.h"
template<class T>
void LinkStack<T>::makeEmpty()
{
	LinkNode<T> *p;
	while(top!=NULL)
	{
		p=top;top=top->link;delete p;
	}
}

template<class T>
void LinkStack<T>::push(const T& x)
{
	top=new LinkNode<T>(x,top);
}
template<class T> 
bool LinkStack<T>::pop(T& x)
{
   if(isEmpty()==true)  return false;
   LinkNode<T> *p=top;
   top=top->link;
   x=p->data;
   delete p;
   return true;
}

template<class T>
bool LinkStack<T>::gettop(T& x)const
{
	if(isEmpty()==true)
              return false;
	x=top->data;
	return true;
}

template<class T>
int LinkStack<T>::getSize()const
{
	LinkNode<T> *p=top;
	int k=0;
	wehile(top!=NULL){top=top->link;k++;}
	return k;
}

 
template<class T>
void LinkStack<T>::output()
{
	LinkNode<T> *p=top;
	while(p!=NULL)
	{
		cout<<p->data<<"  ";
		p=p->link;
	}
}
//---------------------------------------------------------------------------------------------------------------------------------
template<class T>
struct BinTreeNode{
	T data;
	BinTreeNode<T> *leftChild, *rightChild;
	BinTreeNode():leftChild(NULL),rightChild(NULL){}
	BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL):data(x),leftChild(l),rightChild(r){}

};

template<class T>
class BinaryTree
{
	public:
		BinTreeNode<T> *root;
		T RefValue;
	   
		BinaryTree():root(NULL){}
        BinaryTree(T value):RefValue(value),root(NULL){}
		//用递归算法创建树(前序遍历)
		void CreateBinTree(BinTreeNode<T> * &subTree)
		{
			T item;
		    cin>>item;
		
			if(item!=RefValue)
			{
				
				subTree=new BinTreeNode<T>(item);
				if(subTree==NULL)
				{cerr<<"ERROR!"<<endl;exit(1);}
				CreateBinTree(subTree->leftChild);
				CreateBinTree(subTree->rightChild);
			
			}
				else subTree=NULL;
			
		}

		//前序遍历的非递归算法
/*	void PreOrder(BinTreeNode<T> *p)
		{
		
			LinkStack<BinTreeNode<T> *> S;	
         //  BinTreeNode<T> *q;
			S.push(root);
			while(!S.isEmpty())
			{
				S.pop(p);
				T i=(*p).data;
				cout<<i<<endl;
				cout<<"hello!"<<endl;
				if(p->rightChild!=NULL)
					S.push(p->rightChild);
				if(p->leftChild!=NULL)
					S.push(p->leftChild);
			}
		}

*/
	
			void PreOrder(BinTreeNode<T> *p)
			{
					LinkStack<BinTreeNode<T> *> S;
				//	p=root;
					S.push(NULL);
					while(p!=NULL)
					{
					 cout<<(*p).data<<"  ";
					if(p->rightChild!=NULL)
					S.push(p->rightChild);
			     	if(p->leftChild!=NULL)
						p=p->leftChild;
					else  S.pop(p);
					}
			}

		//用中序非递归算法遍历
		void InOrder(BinTreeNode<T> *p)
		{
			LinkStack<BinTreeNode<T> *> S;
			do{
				while(p!=NULL)
				{
					S.push(p);
				    p=p->leftChild;
				}
			if(!S.isEmpty())
			{
				S.pop(p);
				cout<<(*p).data<<"  ";
				p=p->rightChild;
			}
		}while(p!=NULL||!S.isEmpty());
		}

		//判断二叉树是否为空
		bool IsEmpty()
		{
			return (root==NULL)?true:false;
		}
		//返回左子女
		BinTreeNode<T> * LeftChild(BinTreeNode<T> * current)
		{
			return (current!=NULL)?current->leftChild:NULL;
		}
		//返回右子女
       	BinTreeNode<T> * RightChild(BinTreeNode<T> * current)
		{
			return (current!=NULL)?current->rightChild:NULL;
		}

//	protected:
	//	BinTreeNode<T> *root;
	//	T RefValue;
    	/*	friend istream& operator>>(istream &in,BinaryTree<T> &Tree)
		{	}
		*/

};

//栈的定义与实现



void main()
{
	cout<<"开始创建树："<<endl;
	cout<<"请以前序的方式输入树（递归）："<<endl;
	int a=0;
	BinTreeNode<int> * node;
  //  BinTreeNode<int> * r=node;
	BinaryTree<int> t(a);
	t.CreateBinTree(node);
    cout<<"以前序将树输出（非递归）："<<endl;
	t.PreOrder(node);
	cout<<endl;
	cout<<"以中序将树输出（非递归）："<<endl;
	t.InOrder(node);
	cout<<endl;
  //  cout<<(*node).data;
	
}