，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

void postOrder3(BinTree *root)     //非递归后序遍历
{
    stack
  
    s;
   
    BinTree *cur;                      //当前结点 
   
    BinTree *pre=NULL;                 //前一次访问的结点 
   
    s.push(root);
   
    while(!s.empty())
   
    {
   
        cur=s.top();
   
        if((cur->lchild==NULL&&cur->rchild==NULL)||
   
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
   
        {
   
            cout<
   
    data<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过 
    
 s.pop();
    
 pre=cur; 
    
 }
    
 else
    
 {
    
 if(cur->rchild!=NULL)
    
 s.push(cur->rchild);
    
 if(cur->lchild!=NULL) 
    
 s.push(cur->lchild);
    
 }
    
 } 
    
}
   
  

四.整个程序完整的代码

/*二叉树的遍历* 2011.8.25*/ 

#include 
  
   
#include
   
    
#include
     
     
using namespace std;
     

     
typedef struct node
     
{
     
 char data;
     
 struct node *lchild,*rchild;
     
}BinTree;
     

     
typedef struct node1
     
{
     
 BinTree *btnode;
     
 bool isFirst;
     
}BTNode;
     

     

     
void creatBinTree(char *s,BinTree *&root) //创建二叉树，s为形如A(B,C(D,E))形式的字符串 
     
{
     
 int i;
     
 bool isRight=false;
     
 stack
     
       s1; //存放结点 
      
 stack
      
        s2; //存放分隔符
       
 BinTree *p,*temp;
       
 root->data=s[0];
       
 root->lchild=NULL;
       
 root->rchild=NULL;
       
 s1.push(root);
       
 i=1;
       
 while(i
       
         {
        
 if(s[i]=='(')
        
 {
        
 s2.push(s[i]);
        
 isRight=false;
        
 } 
        
 else if(s[i]==',') 
        
 {
        
 isRight=true;
        
 }
        
 else if(s[i]==')')
        
 {
        
 s1.pop();
        
 s2.pop();
        
 }
        
 else if(isalpha(s[i]))
        
 {
        
 p=(BinTree *)malloc(sizeof(BinTree));
        
 p->data=s[i];
        
 p->lchild=NULL;
        
 p->rchild=NULL;
        
 temp=s1.top();
        
 if(isRight==true) 
        
 {
        
 temp->rchild=p;
        
 cout<
        
         data<<"的右孩子是"<
         
           }
          
 else
          
 {
          
 temp->lchild=p;
          
 cout<
          
           data<<"的左孩子是"<
           
             }
            
 if(s[i+1]=='(')
            
 s1.push(p);
            
 }
            
 i++;
            
 } 
            
}
            

            
void display(BinTree *root) //显示树形结构 
            
{
            
 if(root!=NULL)
            
 {
            
 cout<
            
             data;
             
 if(root->lchild!=NULL)
             
 {
             
 cout<<'(';
             
 display(root->lchild);
             
 }
             
 if(root->rchild!=NULL)
             
 {
             
 cout<<',';
             
 display(root->rchild);
             
 cout<<')';
             
 }
             
 }
             
}
             

             
void preOrder1(BinTree *root) //递归前序遍历 
             
{
             
 if(root!=NULL)
             
 {
             
 cout<
             
              data<<" ";
              
 preOrder1(root->lchild);
              
 preOrder1(root->rchild);
              
 }
              
}
              

              
void inOrder1(BinTree *root) //递归中序遍历
              
{
              
 if(root!=NULL)
              
 {
              
 inOrder1(root->lchild);
              
 cout<
              
               data<<" ";
               
 inOrder1(root->rchild);
               
 }
               
} 
               

               
void postOrder1(BinTree *root) //递归后序遍历
               
{
               
 if(root!=NULL)
               
 {
               
 postOrder1(root->lchild);
               
 postOrder1(root->rchild);
               
 cout<
               
                data<<" ";
                
 } 
                
} 
                

                
void preOrder2(BinTree *root) //非递归前序遍历 
                
{
                
 stack
                
                  s;
                 
 BinTree *p=root;
                 
 while(p!=NULL||!s.empty())
                 
 {
                 
 while(p!=NULL)
                 
 {
                 
 cout<
                 
                  data<<" ";
                  
 s.push(p);
                  
 p=p->lchild;
                  
 }
                  
 if(!s.empty())
                  
 {
                  
 p=s.top();
                  
 s.pop();
                  
 p=p->rchild;
                  
 }
                  
 }
                  
}
                  

                  
void inOrder2(BinTree *root) //非递归中序遍历
                  
{
                  
 stack
                  
                    s;
                   
 BinTree *p=root;
                   
 while(p!=NULL||!s.empty())
                   
 {
                   
 while(p!=NULL)
                   
 {
                   
 s.push(p);
                   
 p=p->lchild;
                   
 }
                   
 if(!s.empty())
                   
 {
                   
 p=s.top();
                   
 cout<
                   
                    data<<" ";
                    
 s.pop();
                    
 p=p->rchild;
                    
 }
                    
 } 
                    
} 
                    

                    
void postOrder2(BinTree *root) //非递归后序遍历
                    
{
                    
 stack
                    
                      s;
                     
 BinTree *p=root;
                     
 BTNode *temp;
                     
 while(p!=NULL||!s.empty())
                     
 {
                     
 while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点 
                     
 {
                     
 BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
                     
 btn->btnode=p;
                     
 btn->isFirst=true;
                     
 s.push(btn);
                     
 p=p->lchild;
                     
 }
                     
 if(!s.empty())
                     
 {
                     
 temp=s.top();
                     
 s.pop();
                     
 if(temp->isFirst==true) //表示是第一次出现在栈顶 
                     
 {
                     
 temp->isFirst=false;
                     
 s.push(temp);
                     
 p=temp->btnode->rchild; 
                     
 }
                     
 else //第二次出现在栈顶 
                     
 {
                     
 cout<
                     
                      btnode->data<<" ";
                      
 p=NULL;
                      
 }
                      
 }
                      
 } 
                      
} 
                      

                      
void postOrder3(BinTree *root) //非递归后序遍历
                      
{
                      
 stack
                      
                        s;
                       
 BinTree *cur; //当前结点 
                       
 BinTree *pre=NULL; //前一次访问的结点 
                       
 s.push(root);
                       
 while(!s.empty())
                       
 {
                       
 cur=s.top();
                       
 if((cur->lchild==NULL&&cur->rchild==NULL)||
                       
 (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
                       
 {
                       
 cout<
                       
                        data<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过 
                        
 s.pop();
                        
 pre=cur; 
                        
 }
                        
 else
                        
 {
                        
 if(cur->rchild!=NULL)
                        
 s.push(cur->rchild);
                        
 if(cur->lchild!=NULL) 
                        
 s.push(cur->lchild);
                        
 }
                        
 } 
                        
}
                        

                        

                        
int main(int argc, cha