二叉树后序遍历 -- 递归和非递归实现-蒲公英云

二叉树后序遍历 -- 递归和非递归实现

/*实现二叉树后序遍历 -- 采用递归和非递归方法
*经调试可直接运行源码如下：
***/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
using namespace std;
/*二叉树结点定义*/
typedef struct BTreeNode
{
    char elem;
    struct BTreeNode *pleft;
    struct BTreeNode *pright;
}BTreeNode;
/*
如果根节点为NULL，返回   
根节点不为NULL，先访问左子树，再访问右子树，最后访问根节点
*/
/*后序遍历 递归实现*/
void post_order_traverse(BTreeNode *proot)
{
    if (proot == NULL)
    {
        return;
    }
    post_order_traverse(proot->pleft);//左子树
    post_order_traverse(proot->pright);//右子树
    cout << "递归遍历节点" << proot->elem << endl;//访问根节点
    return;
}
/*后序遍历  非递归实现*/
/*
第一步：给定proot，判断proot是否为NULL；
       如果不为NULL，执行第二步；如果为NULL，执行第三步；
第二步：将proot入栈，并将proot的左结点赋给proot，执行第一步；
第三步：如果栈不为空，则将栈顶元素赋给proot，判断proot是否有右子树以及右子树是否访问过；
       如果没有右子树或者已经访问过右子树，则访问proot并出栈，然后执行第一步；
       如果有右子树并且右子树还没有访问过，则将proot右结点赋给proot，然后执行第一步。
*/
/*后序遍历非递归实现*/
void post_trvaverse(BTreeNode *proot)
{
    if (proot == NULL)
    {
        return;
    }
    stack <BTreeNode*> st;
    BTreeNode* pvisited = NULL;//已访问节点
    while (proot != NULL || !st.empty())
    {
        while (proot != NULL)
        {
            st.push(proot);
            proot = proot->pleft;
        }
        if (!st.empty())
        {
            proot = st.top();
            if (proot->pright == NULL || proot->pright == pvisited)
            {
                st.pop();
                cout << "非递归遍历节点" << proot->elem << endl;
                pvisited = proot;
                proot = NULL;//防止重复遍历
            }
            else
            {
                proot = proot->pright;
            }
        }
    }
    return;
}
/*初始化二叉树根节点*/
BTreeNode* btree_init(BTreeNode *&bt)
{
    bt = NULL;
    return bt;
}
/*先序创建二叉树*/
void pre_crt_tree(BTreeNode* &bt)
{
    char ch;
    cin >> ch;
    if (ch == '#')
    {
        bt = NULL;
    }
    else
    {
        bt = new BTreeNode;
        bt->elem = ch;
        pre_crt_tree(bt->pleft);
        pre_crt_tree(bt->pright);
    }
}
int main()
{
    BTreeNode *bt;
    btree_init(bt);//初始化根节点
    pre_crt_tree(bt);//创建二叉树
    post_trvaverse(bt);//非递归遍历
    post_order_traverse(bt);//递归遍历
    system("pause");
    return 0;
}
/*
运行结果：
a b # # c d # # e # #
---以上为输入---
---以下为输出---
非递归遍历节点b
非递归遍历节点d
非递归遍历节点e
非递归遍历节点c
非递归遍历节点a
递归遍历节点b
递归遍历节点d
递归遍历节点e
递归遍历节点c
递归遍历节点a
请按任意键继续. . .
本例创建的二叉树形状：
    a
b       c
      d   e
参考资料：
http://blog.csdn.net/beitiandijun/article/details/41927747
http://yuncode.net/code/c_505ea04f8f6186
*/