zuoye.cpp

二叉树的各种遍历。递归和非递归遍历以及层次遍历。

#include<iostream.h>
#include<assert.h>
//enum {DefaultSize=100};
template <class Type> class Queue;

template <class Type> class QueueNode {	
friend class Queue<Type>;
private: 
    Type data;				 //队列结点数据
    QueueNode<Type> *link;  //结点链指针
    QueueNode ( Type d=0, QueueNode
      *l=NULL ) : data (d), link (l) { }
};    
template <class Type> class Queue {	
public: 
    Queue ( ) : rear ( NULL ), front ( NULL ) { }
    ~Queue ( );						
    void EnQueue ( const Type & item );
    Type DeQueue ( );					
    Type GetFront ( );					
    void MakeEmpty ( ) { front = rear = NULL; }
    int IsEmpty ( ) const
                    { return front == NULL; }	
private: 
    QueueNode<Type> *front, *rear; //队列指针
};
template <class Type>Queue<Type>::~Queue ( ) {
//队列的析构函数
   QueueNode<Type> *p;
    while ( front != NULL ) {	 //逐个结点释放
        p = front;  front = front->link;  delete p;
    }
}
template <class Type>void  Queue<Type>:: EnQueue ( const Type & item ) {
//将新元素item插入到队列的队尾 
    if ( front == NULL )
	 front = rear = new QueueNode<Type> ( item, NULL );
    else 
     rear = rear->link = new QueueNode<Type> ( item, NULL );
}
template <class Type> Type
Queue<Type>::DeQueue ( ) {
//删去队头结点，并返回队头元素的值
    assert ( !IsEmpty ( ) );	//判队空的断言
    QueueNode<Type> *p = front;		
    Type retvalue = p->data;	//保存队头的值
    front = front->link;   delete p;	  //新队头
    return retvalue;				
}
template <class Type>
Type Queue<Type>::GetFront ( ) {
//若队不空，则函数返回队头元素的值; 
//若队空，则函数返回0。
    assert ( !IsEmpty ( ) );			
    return front->data;				
}

template <class Type> class Stack;			
template <class Type> class StackNode {
friend class Stack<Type>;
private: 
    Type  data;	                         //结点数据	
    StackNode<Type> *link;	 //结点链指针	
    StackNode ( Type d=0, StackNode<Type>
         *l=NULL ) : data (d), link (l) { }
};
template <class Type> class Stack {	
public:
    Stack ( ) : top ( NULL ) { }
    ~Stack ( );
    void Push ( const Type & item);
    Type Pop ( );
    Type GetTop ( );
    void MakeEmpty ( ) {top=NULL;}
    int IsEmpty ( ) const 
         { return top == NULL; }
private:
    StackNode<Type> *top;       //栈顶指针
};
template <class Type> Stack<Type>::~Stack ( )
 {
     StackNode <Type>  *p;
     while ( top != NULL )      //逐结点回收
 	 { p = top;  top = top->link;  delete p; }
}
template <class Type> void Stack<Type>::Push ( const Type &item )
 {
    top = new StackNode<Type> ( item, top );
    //新结点链入top之前, 并成为新栈顶
}
template <class Type> Type Stack<Type>::Pop ( ) 
{
    assert ( !IsEmpty ( ) );				
    StackNode<Type> *p = top;
    Type retvalue = p->data;	 //暂存栈顶数据
    top = top->link;		         //修改栈顶指针
    delete p;   return retvalue;	 //释放,返回数据
}					
template <class Type> Type Stack<Type>::GetTop ( ) 
{
    assert ( !IsEmpty ( ) );
    return top->data;
} 	

template <class Type> class BinaryTree;		

template <class Type> class BinTreeNode 
{
friend class BinaryTree;
public:
    BinTreeNode ( ) :parent(NULL), leftchild (NULL), rightchild (NULL) { }
    BinTreeNode (Type item, BinTreeNode<Type> *left = NULL,BinTreeNode<Type> *right = NULL ) :data (item),  leftchild (left), rightchild(right) { }
    Type & GetData ( ) const { return data; } 
	BinTreeNode<Type> *GetLeft ( ) const 
      { return leftchild; }		
    BinTreeNode<Type> *GetRight ( ) const
      { return rightchild; }
	 BinTreeNode<Type> *GetParent ( ) const
      { return parent; }		
    void SetData ( const Type & item )
   { data = item; }
    void SetLeft ( BinTreeNode <Type> *L )
     { leftchild = L; }	
    void SetRight ( BinTreeNode <Type> *R )
	{ rightchild = R; }
   void SetParent ( BinTreeNode <Type> *g )
	{ Parent = g; }
	void CreateBinaryTree(BinTreeNode<Type>* &root);
    void BinaryTreerse(BinTreeNode<Type> *&root);
void LevelOrder (  BinTreeNode<Type>*&current);
//private:
    BinTreeNode<Type> *leftchild,  *rightchild,*parent;      
    Type data;
};
template <class Type> class BinaryTree 
{	
public:
    BinaryTree ( ) : root (NULL) { }
    BinaryTree ( Type value ) : RefValue(value) { root=NULL;}		
    virtual ~BinaryTree ( ) { destroy ( root ); }
   void CreateBinaryTree(BinTreeNode<Type>* &root);
    virtual int IsEmpty ( ) 
    { return root == NULL ? 1 : 0;
	}	    
    virtual BinTreeNode <Type> *Parent ( BinTreeNode <Type> *current )	
    { return root == NULL || root == current?NULL:Parent(root, current); 
    }
   virtual BinTreeNode <Type> *leftchild (BinTreeNode <Type> *current )
   { return root != NULL?current->leftchild : NULL;
   }
   virtual BinTreeNode <Type> *rightchild (BinTreeNode <Type> *current)
    { return root != NULL ?current->rightchild : NULL;
	}
    void insert( BinTreeNode<Type> *&current,Type item);
    
    BinTreeNode <Type> *GetRoot ( ) const
        { return root; } 
    

	
	friend istream &operator >> (istream &in, BinaryTree<Type> &Tree ) ;
   
	friend ostream &operator << (ostream &out, BinaryTree <Type> &Tree );
   
void BinaryTreerse(BinTreeNode<Type> *&root);
void LevelOrder (  BinTreeNode<Type>*&current);
BinTreeNode <Type> *root,*current;

          private:
			  
    
			Type RefValue;
    
			BinTreeNode <Type> *Parent (BinTreeNode <Type> *start,BinTreeNode <Type> *current);
    
			int Insert ( BinTreeNode<Type> * &current,  Type item ) ;
    
			void Traverse ( BinTreeNode<Type> *current,ostream &out ) const;
    
			int Find ( BinTreeNode<Type> *current, const Type &item ) const  ;            
    
			void destroy(BinTreeNode<Type> *current);
};
template<class Type> void BinaryTree<Type>::insert( BinTreeNode<Type> *&current,Type item)
{  
if(current==NULL)
current=new BinTreeNode<Type>(item);
else if(current->data>item)
 insert(current->leftchild,item);
else if(current->data<=item)
 insert(current->rightchild,item);
}


template<class Type> void BinaryTree<Type>:: destroy ( BinTreeNode<Type> *current ) 
{
    if ( current != NULL )
	{
       destroy ( current->leftchild );
       destroy ( current->rightchild );
       delete current;
    }
}
template <class Type> BinTreeNode <Type> *BinaryTree <Type>::Parent ( BinTreeNode <Type>*start, BinTreeNode <Type> *current ) {
    if ( start == NULL ) return NULL;
    if ( start->leftchild == current || start->rightchild == current )
		return start;	
    BinTreeNode <Type> *p;
    if ( ( p = Parent ( start->leftchild, current ) ) != NULL ) return p;	
    else return Parent ( start->rightchild, current );
}
template <class Type> void BinaryTree<Type>::Traverse ( BinTreeNode <Type> *current, ostream &out ) const
 {
    if ( current != NULL )
	{					       
        out << current->data << "  ";
        Traverse ( current->leftchild, out );		
        Traverse ( current->rightchild, out );
    }
}
template <class Type> istream & operator>>( istream & in, BinaryTree <Type> &Tree ) 
{     Type item;
      
         cout << "构造二叉树:\n ";			    
        cout << "输入数据 (用 " << Tree.RefValue <<"结束): ";
       in >> item;						
       while ( item != Tree.RefValue ) {			
	   Tree.insert ( Tree.root,item );
       //cout << "输入数据 (用 " << Tree.RefValue <<"结束): "; 	
       in >> item;
    }
    return in;
}
template <class Type> ostream & operator<<( ostream & out, BinaryTree <Type> &Tree )
{   
    out << "递归二叉树的前序遍历.\n";
    Tree.Traverse ( Tree.root, out );
    out << endl;
    return out;
}
template<class Type>void BinaryTree<Type>::CreateBinaryTree(BinTreeNode<Type>* &root)
{
  //按前序序列输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树T.
  int ch;
  cin>>ch;
  while(ch!=10)
 {	cin>>ch;
  //if(ch==' ') root=NULL;
  //else{
      root=new BinTreeNode<Type>();
      //if(!t ) {cerr<<"建立不成功";     exit(1);}
      root->data=ch; 
  //}//成根结点
     CreateBinaryTree(root->leftchild); //构造左子树
     CreateBinaryTree(root->rightchild); //构造右于树
    
 }
 cout<<"建立成功";
}//／／CreateBinaryTree

template<class Type>void BinaryTree<Type>::BinaryTreerse(BinTreeNode<Type> * &root)
{
  //采用二叉链表存储结构
  Stack <BinTreeNode<Type>*>s;
  BinTreeNode<Type> *p=root; 
  s.MakeEmpty();
  //s.Push(p);//根指针进栈
  cout<<"非递归二叉数的中序遍历"<<endl;
  while(p!=NULL|| !s.IsEmpty())
  {
    while(p!=NULL)  { s.Push(p);p=p->leftchild;}//向左走到尽头
    if(!s.IsEmpty())
	{    //访问结点，向右一步
      p=s.Pop(); 
   
	  cout<<p->data<<"  ";
     p=p->rightchild;
    }//if
  }//while
  cout<<endl;
}// lnOrderTraverse 
template <class Type> void BinaryTree<Type>::LevelOrder ( BinTreeNode<Type>*&current)
 {

Queue<BinTreeNode<Type>*> Qu ;
// BinTreeNode<Type> *p;
//BinTreeNode<Type> *current1;

       Qu.EnQueue ( current );
	   cout<<"非递归层次遍历"<<endl;;
       while ( !Qu.IsEmpty ( ) ) 
	   {  //队列不空
	   current = Qu.DeQueue ( );  
	   
	  cout<<current->data<<"  ";//根进队列
	   //visit ( );		
            //退出队列,访问
	if(current->leftchild)
	  Qu.EnQueue ( current->leftchild ); 
	if(current->rightchild)
	 Qu.EnQueue(current->rightchild); 
	

        }
	   cout<<endl;
}
   



void main()
{

	BinaryTree <int>*Tree=new BinaryTree<int>(10);
//Tree->CreateBinaryTree(Tree->root);
cin>>*Tree;
Tree->BinaryTreerse(Tree->root);
cout<<*Tree;
 Tree->LevelOrder(Tree->root);


}