#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct Tree{    int x;    Tree *lchild, *rchild;    Tree(){        lchild = rchild = NULL;    }};typedef Tree* pT;void buildT(pT &T){    int n;    cin>>n;    if(n==-1)        return;    T = new Tree();    T->x = n;    buildT(T->lchild);    buildT(T->rchild);}/**************************************************************************/ /*     非递归先序遍历: 对于任一结点P：     1)访问结点P，并将结点P入栈;     2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P， 　　　　循环至1); 若不为空，则将P的左孩子置为当前的结点P;     3)直到P为NULL并且栈为空，则遍历结束。*/ void preOrderNorecursive(pT T){    stack
          
            s; s.push(T); while(!s.empty()){ while(T != NULL){ //左子树走到尽头 cout<
           
            x<<" "; T = T->lchild; s.push(T); } s.pop();//清除空指针 if(!s.empty()) { T = s.top(); s.pop(); s.push(T=T->rchild);//右子树走起 } }}void preOrderOutT(pT T){ if(T){ cout<
            
             x<<" "; preOrderOutT(T->lchild); preOrderOutT(T->rchild); }}/**************************************************************************/ /* 非递归中序遍历：对于任一结点P， 1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理； 2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子； 3)直到P为NULL并且栈为空则遍历结束*/ void inOrderNorecursive(pT T){ stack
             
               s; s.push(T); while(!s.empty()){ while(T!=NULL)//左子树走到尽头 s.push(T=T->lchild); s.pop();//清除空指针 if(!s.empty()) { T = s.top(); s.pop(); cout<
              
               x<<" "; s.push(T = T->rchild);//访问右子树 } }}void inOrderOutT(pT T){ if(T){ inOrderOutT(T->lchild); cout<
               
                x<<" "; inOrderOutT(T->rchild); }}/**************************************************************************/ /* 非递归后序遍历： 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。 如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子 都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈， 这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。*/ void postOrderNorecursive(pT T){ stack
                
                  s; s.push(T); pT pre = NULL;//后序遍历之前输出的节点 while(!s.empty()){ T = s.top(); if(T->lchild==NULL && T->rchild==NULL || (pre!=NULL && (T->lchild==pre || T->rchild==pre)) { cout<
                 
                  x<<" "; pre = T; s.pop(); } else { //依次将右子树和左子树放入栈中 if(T->rchild) s.push(T->rchild); if(T->lchild) s.push(T->lchild); } }}void postOrderOutT(pT T){ if(T){ postOrderOutT(T->lchild); postOrderOutT(T->rchild); cout<
                  
                   x<<" "; }}/**************************************************************************/ int main(){ pT T = NULL; buildT(T); /**************************************************************************/ cout<<"递归先序遍历:"<
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

1 2 2 -1 -1 4 7 -1 -1 -1 3 4 -1 8 -1 -1 5 -1 -1

递归先序遍历:

1 2 2 4 7 3 4 8 5

非递归先序遍历:

1 2 2 4 7 3 4 8 5

递归中序遍历:

2 2 7 4 1 4 8 3 5

非递归中序遍历:

2 2 7 4 1 4 8 3 5

递归后序遍历:

2 7 4 2 8 4 5 3 1

非递归后序遍历:

2 7 4 2 8 4 5 3 1

*/