二叉树的前序, 中序, 后序非递归算法

什么是前序, 中序, 后序

首先先介绍一下三种遍历二叉树的方法:

1. 前序：先根结点后左孩子最后右孩子
2. 中序：先左孩子后根结点最后右孩子
3. 后序：先左孩子后右孩子最后根结点
   
   二叉树例子
   
   例如上图中的二叉树我们的遍历输出分别为:
   前序: GDAFEMHZ
   中序: ADEFGHMZ
   后序: AEFDHZMG

代码部分

#include<cstdio>
#include<iostream>
#include<stack>//这是关于C++队列以及栈的库模板调用
#include<queue>//我的博客中有一篇关于这些库函数的使用
#include<iomanip>
#include<cstdlib>
#define MAXSIZE 100

using namespace std;

int flag[MAXSIZE];

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;//定义二叉树的结构体

void CreateBiTree(BiTree &T)
{
    char ch;
    cin>>ch;
    if(ch == '#') T = NULL;
    else
    {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T -> lchild);//输入左子树
        CreateBiTree(T -> rchild);//输入右子树
    }
}//采用先序递归的形式创建二叉树, 当用户输入"#"时,为空作用域
//例如我们上面的例子,输入上面的图片中二叉树时这个函数的输入格式为:
//GDA##FE###MH##Z###

void show_DLR(BiTree &T)//先序遍历
{
    BiTree p, l, k;
    p = T;
    l = new BiTNode;
    k = new BiTNode;
    stack<BiTree>m;//这个遍历我采用栈压入元素, 队列弹出元素的
                   //格式
    queue<BiTree>n;
    while(p || !n.empty())
    {
        if(p)//遍历左子树
        {
            m.push(p);//分别将二叉树的结点压入栈和队列中
            n.push(p);
            p = p->lchild;
        }
        else
        {
            k = n.front();
            n.pop();//注意此时弹出的为队列中的第一个元素
            cout<<setw(4)<<k->data;
            l = m.top();
            m.pop();
            p = l->rchild;
        }
    }
    cout<<endl;
}

void show_LDR(BiTree &T)//中序遍历
{
    BiTree p, q;
    stack<BiTree>s;//和上面的先序遍历很像
                   //只不过在中序遍历中我们只用一个栈就可以完成
    p = T;
    q = new BiTNode;
    while(p || !s.empty() )
    {
        if(p)
        {
            s.push(p);
            p = p->lchild;
        }
        else
        {
            q = s.top();
            s.pop();
            cout<<setw(4)<<q->data;
            p = q->rchild;
        }
    }
    cout<<endl;
}

void show_LRD(BiTree &T)//后序遍历是最为头疼的
{//这里我设置了一个全局数组为flag
    BiTree p, m, n;
    stack<BiTree>s;
    int i = 0;
    p = T;
    while(p)
    {//将当前左子树全部压入堆栈中
        s.push(p);
        flag[s.size()] = 0;//栈中的库函数s.size()返回当前栈中
                           //元素的个数
                           //其目的主要是设置一个标志位看看
                           //当前节点是否被访问过
        p = p->lchild;
    }
    while(!s.empty())
    {
        p = s.top();
        if(!p->rchild || flag[s.size()])
        {//没有右子树或者当前的结点的右子树被访问过就输出
            m = s.top();
            s.pop();
            cout<<setw(4)<<m->data;
        }
        else
        {
            flag[s.size()] = 1;//已访问
            m = p->rchild;
            while(m)
            {//因为为后序遍历,将当前结点的左子树分别再压入堆栈
                s.push(m);
                flag[s.size()] = 0;
                m = m->lchild;
            }
        }
    }
}

int main()
{
    BiTree L;
    CreateBiTree(L);
    show_DLR(L);
    show_LDR(L);
    show_LRD(L);
    return 0;
}