非递归遍历二叉树

　　使用递归可以非常方便地实现二叉树的遍历。如果不使用递归呢，请听我一一道来。

首先给出二叉树遍历的递归版本：

struct BTNode {
    char data;
    BTNode *lchild, *rchild;
};

void visit(BTNode *p)
{
    cout<<p->data<<" ";
}
//先序遍历
void preOrder(BTNode *T)
{
    if(T != NULL)
    {
        visit(T);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}
//中序遍历
void inOrder(BTNode *T)
{
    if(T != NULL)
    {
        inOrder(T->lchild);
        visit(T);
        inOrder(T->rchild);
    }
}
//后序遍历
void postOrder(BTNode *T)
{
    if(T != NULL)
    {
        postOrder(T->lchild);
        postOrder(T->rchild);
        visit(T);
    }
}

下面给出二叉树遍历的非递归版本：

//非递归先序遍历
void preOrder1(BTNode *T)
{
    if(!T)
        return ;
    stack<BTNode*> s;
    s.push(T);
    while(!s.empty())
    {
        BTNode *tmp = s.top();
        visit(tmp);
        s.pop();
        if(tmp->rchild)
            s.push(tmp->rchild);
        if(tmp->lchild)
            s.push(tmp->lchild);
    }
}

void preOrder2(BTNode *T)
{
    stack<BTNode*> s;
    BTNode *p = T;
    while (p !=NULL || !s.empty())
    {
        while (p != NULL)
        {
            visit(p);
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
}
//非递归中序遍历
void inOrder1(BTNode *T)
{
    stack<BTNode*> s;
    BTNode *p = T;
    while (p !=NULL || !s.empty())
    {
        while (p != NULL)
        {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty())
        {
            p = s.top();
            visit(p);
            s.pop();
            p = p->rchild;
        }
    }
}
//非递归后序遍历
void postOrder1(BTNode *T)
{
    stack<BTNode*> s;
    BTNode *cur = T;
    BTNode *pre = NULL;
    while (cur != NULL || !s.empty())
    {
        while (cur != NULL)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        cur = s.top();
        // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点  
        if (cur->rchild == NULL || cur->rchild == pre)
        {
            visit(cur);
            pre = cur;
            s.pop();
            cur = NULL;
        }
        else
            cur = cur->rchild;
    }
}

参考文章：http://blog.csdn.net/hackbuteer1/article/details/6583988

              http://blog.csdn.net/kofsky/article/details/2886453

　　　　　http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

　　　　   http://wu-yudong.iteye.com/blog/1992542

　　　　   http://zisong.me/post/suan-fa/geng-jian-dan-de-bian-li-er-cha-shu-de-fang-fa

再补充一个层次遍历版本：

//层次遍历
void levelOrder(BTNode *T)
{
    if (T == NULL)
        return;
    queue<BTNode*> q;
    q.push(T);
    while (!q.empty())
    {
        BTNode *p = q.front();
        visit(p);
        q.pop();
        if (p->lchild != NULL)
            q.push(p->lchild);
        if (p->rchild != NULL)
            q.push(p->rchild);
    }
}

最后给大家一个实实在在的例子：
　　二叉树结构如下：

　　　　　　

创建二叉树：

//建立二叉树
void createBiTree(BTNode* &T)
{
    char ch = getchar();
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BTNode;
        T->data = ch;
        createBiTree(T->lchild);
        createBiTree(T->rchild);
    }
}

主函数代码：

int main()
{
    BTNode *T;
    cout<<"请按先序遍历顺序输入二叉树，‘#’表示空节点"<<endl;
    createBiTree(T);
    cout<<"递归先序遍历："<<endl;
    preOrder(T);
    cout<<endl;
    cout<<"递归中序遍历："<<endl;
    inOrder(T);
    cout<<endl;
    cout<<"递归后序遍历："<<endl;
    postOrder(T);
    cout<<endl;
    cout<<"非递归先序遍历："<<endl;
    preOrder1(T);
    cout<<endl;
    cout<<"非递归中序遍历："<<endl;
    inOrder1(T);
    cout<<endl;
    cout<<"非递归后序遍历："<<endl;
    postOrder1(T);
    cout<<endl;
    cout<<"层次遍历:"<<endl;
    levelOrder(T);
    cout<<endl;
    return 0;
}

　　输出：

　　　　

　　树是一种非常重要的数据结构，以后还会有相关文章发表。如有问题，欢迎来稿。