二叉树的后序遍历

如下图表示一颗二叉树，对它进行先序遍历操作，采用两种方法，递归和非递归操作。。

遍历结果为：4526731。。

1、递归操作：

思想：若二叉树为空，返回。否则

1）后序遍历右子树；2）后序遍历左子树；3）遍历根节点

代码：

void PostOrder(BiTree root)  
{  
    if(root==NULL)  
        return ;  
    PostOrder(root->lchild);      //递归调用，后序遍历左子树  
    PostOrder(root->rchild);      //递归调用，后序遍历右子树  
    printf("%c ", root->data);    //输出数据    
}  

2、非递归操作

代码：

void PostOrder_Nonrecursive(BiTree  T)  // 后序遍历的非递归    
{    
    stack<BiTree> S;    
    BiTree curr = T ;           // 指向当前要检查的节点  
    BiTree previsited = NULL;    // 指向前一个被访问的节点  
    while(curr != NULL || !S.empty())  // 栈空时结束    
    {    
        while(curr != NULL)            // 一直向左走直到为空  
        {    
            S.push(curr);    
            curr = curr->lchild;    
        }    
        curr = S.top();  
        // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点  
        if(curr->rchild == NULL || curr->rchild == previsited)    
        {    
            cout<<curr->data<<"  ";    
            previsited = curr;    
            S.pop();    
            curr = NULL;    
        }    
        else  
            curr = curr->rchild;      // 否则访问右孩子  
    }    
}   

或者采用双栈操作，代码：

void PostOrder_Nonrecursive1(BiTree  T)  // 后序遍历的非递归 --双栈法  
{    
    stack<BiTree> s1 , s2;    
    BiTree curr ;           // 指向当前要检查的节点  
    s1.push(T);  
    while(!s1.empty())  // 栈空时结束    
    {  
        curr = s1.top();  
        s1.pop();  
        s2.push(curr);  
        if(curr->lchild)  
            s1.push(curr->lchild);  
        if(curr->rchild)  
            s1.push(curr->rchild);  
    }  
    while(!s2.empty())  
    {  
        printf("%c ", s2.top()->data);  
        s2.pop();  
    }  
}