迭代的方式来遍历树（前序中序后序）百度一面-蒲公英云

迭代的方式来遍历树（前序中序后序）百度一面

递归的方式来进行遍历树很简单。
但是通过迭代的方式遍历树。
首先
中序遍历
中序遍历就主要在于先走到最左节点，然后从这个节点进行左中右的顺序。因为到了最左的节点也要往回走，而为了支持这个回溯类似的方式，用栈来保存数据，进入一个下一个节点的就通过换一个节点继续从开头（所有左部分节点压入）

code：

void PreOrderWithoutRecursion1(BTNode* root)
{ 
    if (root == NULL)
        return;
    node* p = root;
    stack<node*> s;
    while (!s.empty() || p)
    { 
        //
        while (p)
        {         //如果是前序遍历，就是在这里进行操作。
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明根和左子树都遍历完了，该进入右子树了
        if (!s.empty())
        { 
            p = s.top();
            s.pop();
            cout<<p->data;    //如果是中序；在这里输出
            p = p->rchild;
        }
    }
    cout << endl;
}

不同的是后序遍历
用一个保存上一个节点，
先完全进入左节点，然后判断当前节点的右边节点是不是空 || 当前节点是不是上一个节点，就是已经访问过了

//后序遍历
void PostOrderWithoutRecursion(BTNode* root)
{ 
    if (root == NULL)
        return;
    stack<BTNode*> s;
    BTNode* pCur, *pLastVisit;
    pCur = root;
    pLastVisit = NULL;
    //先把pCur移动到左子树最下边
    while (pCur)
    { 
        s.push(pCur);
        pCur = pCur->lchild;
    }
    while (!s.empty())
    { 
        //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        pCur = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
        { 
            cout << pCur->data;
            //修改最近被访问的节点
            pLastVisit = pCur;
        }
        else
        { 
            s.push(pCur);
            //进入右子树，且可肯定右子树一定不为空
            pCur = pCur->rchild;
            while (pCur)
            { 
                s.push(pCur);
                pCur = pCur->lchild;
            }
        }
    }
    cout << endl;
}