erchashu.txt

二叉树的各种遍历

#include<iostream>
#include<string>
using namespace std;
/*#ifndef BITREE_H
#define BITREE_H
#include<iostream>
#include<string>*/



template <class T>
struct BiNode   
{
  T data;       
  BiNode<T> *lchild, *rchild;
};

template <class T>
class BiTree
{
public:
    BiTree( );             //构造函数，初始化一棵二叉树，其前序序列由键盘输入
    ~BiTree(void);         //析构函数，释放二叉链表中各结点的存储空间
	BiNode<T>* Getroot();  //获得指向根结点的指针
    void PreOrder(BiNode<T> *root);     //前序遍历二叉树
    void InOrder(BiNode<T> *root);      //中序遍历二叉树
    void PostOrder(BiNode<T> *root);    //后序遍历二叉树
    void LeverOrder(BiNode<T> *root);   //层序遍历二叉树
    void PreOrdercount(BiNode<T> *root);  //叶子节点
private:
    BiNode<T> *root;         //指向根结点的头指针
    BiNode<T> *Creat( );     //有参构造函数调用
    void Release(BiNode<T> *root);   //析构函数调用 
};
//#endif


int n=0;

template<class T>
BiTree<T>::BiTree( )
{
	this->root = Creat( );
}

template<class T>
BiTree<T>::~BiTree(void)
{
	Release(root);
}

template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
	return root;
}

template<class T>    //前序排列
void BiTree<T>::PreOrder(BiNode<T> *root)
{
	if(root==NULL)  return;
	else{		
		cout<<root->data<<" ";
        PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}


template <class T>   //中序排列
void BiTree<T>::InOrder (BiNode<T> *root)
{
    if (root==NULL)  return;      //递归调用的结束条件	          
    else{	
        InOrder(root->lchild);    //中序递归遍历root的左子树
        cout<<root->data<<" ";    //访问根结点的数据域
        InOrder(root->rchild);    //中序递归遍历root的右子树
	}
}

template <class T>   //后序排列
void BiTree<T>::PostOrder(BiNode<T> *root)
{ 
    if (root==NULL)   return;       //递归调用的结束条件
    else{	
        PostOrder(root->lchild);    //后序递归遍历root的左子树
        PostOrder(root->rchild);    //后序递归遍历root的右子树
        cout<<root->data<<" ";      //访问根结点的数据域
	}
}

template <class T>     //层序排列
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
	const int MaxSize = 100;

	int front = 0;
	int rear = 0;  //采用顺序队列，并假定不会发生上溢

	BiNode<T>* Q[MaxSize];
    BiNode<T>* q;

	if (root==NULL) return;
	else{
		Q[rear++] = root;
		while (front != rear)
		{
			q = Q[front++];
     		cout<<q->data<<" "; 		
    		if (q->lchild != NULL)    Q[rear++] = q->lchild;		
			if (q->rchild != NULL)    Q[rear++] = q->rchild;
		}
	}
}


template<class T>      //计算叶子节点 
void BiTree<T>::PreOrdercount(BiNode<T> *root)
{
	
	if(root)
	{   
		
		if(!root->lchild&&!root->rchild)  n++;		
        PreOrdercount(root->lchild);
		PreOrdercount(root->rchild);
		
   
	}
	
}



template <class T>       //生成树
BiNode<T>* BiTree<T>::Creat( )
{
	BiNode<T>* root;
	T ch;
	cout<<"请输入创建一棵二叉树的结点数据"<<endl;
	cin>>ch;
    if (ch=="#") root = NULL;
    else{ 
	     root = new BiNode<T>;       //生成一个结点
         root->data=ch;
         root->lchild = Creat( );    //递归建立左子树
         root->rchild = Creat( );    //递归建立右子树
    } 
    return root;
}




template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
  if (root != NULL){                  
	  Release(root->lchild);   //释放左子树
      Release(root->rchild);   //释放右子树
      delete root;
  }  
}




int main()
{	
	
	int t=-1;
	BiTree<string> bt; //创建一棵树
	BiNode<string>* root = bt.Getroot( );  //获取指向根结点的指针 
	cout<<"二叉树创建完成"<<endl;

while(t!=0)
	{
		cout<<" ***************************菜单****************************"<<endl;
		cout<<" *               1.------前序遍历------                         *"<<endl;
		cout<<" *               2.------中序遍历------                         *"<<endl;
        cout<<" *               3.------后序遍历------                         *"<<endl;
		cout<<" *               4.------层序遍历------                         *"<<endl;
	    cout<<" *               5.------计算叶子结点数------                       *"<<endl;
		cout<<" *               0.结束操作                                     *"<<endl;
		cout<<" ***********************************************************"<<endl;
		cout<<"请选择你所要执行的操作数字:"<<endl;
		     cin>>t;
		switch(t)

		{	
			case 1: cout<<"------前序遍历------    "<<endl;
					
			   try
					{
				         bt.PreOrder(root);
					}
					catch(char* wrong)
					{
						cout << wrong;    
					}
					cout<<endl; break;  
					
			case 2: cout<<"------中序遍历------ "<<endl;
					
				    
					try
					{
				          bt.InOrder(root);
					}
				   	catch(char* wrong)
					{
						cout << wrong;    
					}
					cout<<endl; break;          
			case 3:cout<<"------后序遍历------ "<<endl;
				  
				   
				   	try
					{
						bt.PostOrder(root);
					}

				   	catch(char* wrong)
					{
						cout << wrong;    
					}
				   
				   cout<<endl;break;				 
			case 4:cout<<"------层序遍历------ "<<endl;
				  
				   try
				   {	
					   	bt.LeverOrder(root);  					                     
                
				   } 
						
				   	catch(char* wrong)
					{
						cout << wrong;    
					}
				   
				   cout<<endl;break;			
			case 5:cout<<"------ 计算二叉树的叶子结点数------ :"<<endl;
					try

				   {	
					   bt.PreOrdercount(root);  					                     
                      cout<<"叶子节点数  "<<n<<endl;
				   } 
						
				   	catch(char* wrong)
					{
						cout << wrong;    
					}
				   
				   cout<<endl;break;
				   
			case 0:cout<<"结束操作"<<endl;break;
                
				   
		
		
		
		}
	
	}


      return 0;

}