本文参考了其他文章，并非原创，文末有原文链接

首先一点：桟和递归本质是一样的，这也是为什么非递归实现需要借助桟（借助桟的先进后出属性）

1. 节点数据结构

//Binary Tree Node
typedef struct node
{
    int data;
    struct node* lchild;  //左孩子
    struct node* rchild;  //右孩子
}BTNode;

前序、中序、后序遍历的非递归实现中，前序和中序最简单，后序遍历实现起来有点难度。

2. 前序遍历

  • 核心：由于遍历右节点需要借助根节点，所以我们在遍历根节点的同时需要将根节点存储在stack中 
void PreOrderWithoutRecursion1(BTNode* root)
{
    if (root == NULL)
        return;
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        //边遍历边打印，并存入栈中，以后需要借助这些根节点进入右子树
        while (p)
        {
            cout << setw(4) << p->data;
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明根和左子树都遍历完了，该进入右子树了
        if (!s.empty())
        {
            p = s.pop();
            p = p->rchild;
        }
    }
    cout << endl;
}

3. 中序遍历

  • 核心：由于遍历右节点需要借助根节点，所以我们在遍历根节点的同时需要将根节点存储在stack中 
//中序遍历
void InOrderWithoutRecursion1(BTNode* root)
{
    //空树,直接返回
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    //桟用于存储所有根节点
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p)
        {
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty())
        {
            p = s.pop();
            cout << setw(4) << p->data;
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
            p = p->rchild;
        }
    }
}

4. 后序遍历

  • 核心：后序遍历和前序，中序遍历有点不同，在对根节点（每个树的相对根节点）进行访问前，需要先判断是不是已经访问过右孩子节点了 
//后序遍历
void PostOrderWithoutRecursion(BTNode* root)
{
    if (root == NULL)
        return;
    stack<BTNode*> s;
    //pCur:当前访问节点，pLastVisit:上次访问节点
    BTNode* pCur, *pLastVisit;
    //pCur = root;
    pCur = root;
    pLastVisit = NULL;
    //先把pCur移动到左子树最下边
    while (pCur)
    {
        s.push(pCur);
        pCur = pCur->lchild;
    }
    while (!s.empty())
    {
        //开始从桟中取出存储的根节点
        pCur = s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
        {
            cout << setw(4) << pCur->data;
            //修改最近被访问的节点
            pLastVisit = pCur;
        }
        //不满足上面的条件，说明当前根节点有右孩子节点，且其右孩子节点还未被访问，必须先访问右孩子节点
        else
        {
            //根节点再次入栈
            s.push(pCur);
            //进入右子树
            pCur = pCur->rchild;
            //进入有子树后，需要将右子树的所有根节点也存放到桟中
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->lchild;
            }
        }
    }
    cout << endl;
}

原文链接：https://blog.csdn.net/zhangxiangDavaid/article/details/37115355#commentBox