二叉树中的遍历方法有三种，前序遍历，中序遍历，后序遍历

 

结点结构

template
     
      struct BinaryNode{    T elem;    BinaryNode *left;    BinaryNode *right;    BinaryNode(T d, BinaryNode *l=NULL, BinaryNode *r=NULL):elem(d), left(l),right(r){}};
     

　　

 

1、递归算法

递归算法比较简单，毕竟二叉树是按照递归的方法定义的

前序遍历递归算法

template
     
      void preOrder_recursive(BinaryNode
      
       * root){	if(!root)	{		visit(root);		preOrder_recursive(root->lchild);		preOrder_recursive(root->rchild);	}}
      
     

　　

中序遍历递归算法

template
     
      void inorder_recursive(BinaryNode
      
       * root){    if(!root)    {    	inorder_recursive(root->left);    	visit(root);    	inorder_recursive(root->right);    }    else    	return;}
      
     

　　

后序遍历递归算法

template
     
      void preOrder_recursive(BinaryNode
      
       * root){	if(!root)	{		visit(root);		preOrder_recursive(root->lchild);		preOrder_recursive(root->rchild);	}}
      
     

　　

2、非递归算法比较麻烦

都要利用栈结构来解决问题

前序遍历非递归算法

//前序遍历先访问根结点，再访问孩子结点/*用栈储存根结点，首先一直往左访问，直至NULL时，从栈中取栈顶元素，开始访问右方结点*/template
     
      void preOrder(BinaryNode
      
       * root){	stack
       
         bn;	BinaryNode* p=root;	while(p!=NULL||!bn.empty())	{		while(p!=NULL)		{			visit(p);			bn.push(p);			p=p->lchild;		}		if(!bn.empty())		{			p=bn.top();			bn.pop();			p=p->rchild;		}	}}
       
      
     

　　

中序遍历非递归算法

template
     
      void inorder(BinaryNode
      
       *root){    stack
       
         bn;    BinaryNode* p=root;        while(p!=NULL||!bn.empty())    {       while(p!=NULL)       {       	  bn.push(p);       	  p=p->lchild;       }       if(!bn.empty())       {       	  p=bn.top();       	  bn.pop();       	  visit(p);       	  p=p->rchild;       }    }}
       
      
     

　　

后序遍历非递归算法（挺难弄的）

两种方法

（1）法1

template
     
      typedef struct BinaryNodewithTag{    BinaryNode
      
       * bn;    bool tag;}BTag;template
       
        void postOrder1(BinaryNode
        
         * root){    stack
         
          
           *> s; BinaryNode
           
            * p=root; BTag
            
             * temp; while(p!=NULL||!s.empty()) { while(p!=NULL) { temp = new BTag(); temp->bn=p; temp->tag=true; s.push(temp); p=p->lchild; } if(!s.empty()) { temp=s.top(); s.pop(); if(temp->tag)//第一次访问 { temp->tag=false; s.push(temp); p=temp->bn->rchild;//访问右孩子 } else//第二次访问 { visit(temp->bn); p=NULL; delete temp; } } } }
            
           
          
         
        
       
      
     

　　

（2）法2

template
     
      void postOrder2(BinaryNode
      
       * root){	stack
       
         bn;	BinaryNode *cur;	BinaryNode *pre=NULL;//上一个被访问的结点    bn.push(root);	while(!bn.empty())	{		cur=bn.top();		if((cur->rchild==NULL&&cur->rchild==NULL)||			(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))		{//如果没有左右孩子或则左右孩子已被访问			visit(cur);			bn.pop();			pre=cur;		}		else		{			if(cur->rchild!=NULL)			{				bn.push(cur->rchild);			}			else(cur->lchild!=NULL)			{				bn.push(cur->lchild);			}		}	}}