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

首先一点:桟和递归本质是一样的,这也是为什么非递归实现需要借助桟(借助桟的先进后出属性)

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