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

刺骨的言语ヽ痛彻心扉 2022-07-28 08:59 194阅读 0赞

/*实现二叉树后序遍历 -- 采用递归和非递归方法
    *经调试可直接运行源码如下：
    ***/
    
    #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
    */