二叉树的非递归遍历

递归转非递归 几乎都是用栈， 前序和中序遍历比较简单 ，后序遍历稍麻烦；

1. 前序遍历 ：

void preDis(NODE* head)         //前序遍历
{
    NODE* temp = head;
    stack<NODE*> st;
    while (temp != NULL||!st.empty())                    
    {
        while (temp != NULL)               //当前非空
        {
            cout<<temp->val<<' ';         //访问
            st.push(temp);                    //进栈 (可能有右子树)
            temp = temp->lchild;          //继续先序访问左子树
        }
        if (!st.empty())                           //栈非空
        {
            temp = st.top();                  //取头
            st.pop();
            temp = temp->rchild;         //访问头的右子树(进栈的元素都访问过了 但是右子树还没有)
        }
    }
}

2. 中序遍历：唯一和前序不同的是访问当前节点的时间

void midDis(NODE* head)                   //中序遍历
{
    NODE* temp = head;
    stack<NODE*> st;
    while (temp != NULL||!st.empty())
    {
        while (temp != NULL)            //当前非空
        {
            st.push(temp);                       //进栈
            temp = temp->lchild;             //左子树进栈
        }
        if (!st.empty())
        {
            temp = st.top();
            st.pop();
            cout<<temp->val<<' ';               //与前序的不同 再次出栈才访问
            temp = temp->rchild;
        }
    }
}

3. 后序遍历：

比前两者都要麻烦的多，不过基本思路还是一样的，就是访问当前节点的时候，若当前节点没有子树，又或者当前节点的子树都已经访问过了，则可以访问当前节点；

否则，将该节点的子树压栈(压栈的顺序是，先右子树，后左子树)

void posDis(NODE* head)                    //后续
{
    stack<NODE*>st;
    NODE* cur;                                            
    NODE* pre = NULL;
    st.push(head);
    while (!st.empty())
    {
        cur = st.top();
        if ((cur->lchild == NULL&&cur->rchild == NULL)||(pre != NULL&&(pre == cur->lchild||pre == cur->rchild)))    //当前结点没有子树或子树都被访问      
                                                                                                                                                                       //过了，才访问根节点
        {
            cout<<cur->val<<' ';
            st.pop();                                                                //访问过了就弹出栈
            pre = cur;                                                               //更新前一个访问的节点
        }
        else                                              //当前节点有子树 且没有被访问过
        {
            if (cur->rchild != NULL)              //右子树进栈
            {
                st.push(cur->rchild);
            }
            if (cur->lchild != NULL)           //左子树进栈
            {
                st.push(cur->lchild);
            }
        }
    }
}