原二叉树非递归前序中序后序遍历的模板写法

作者在 2011-04-08 10:28:44 发布以下内容

话不多说，上代码

前中序需要一个栈： stack<struct tree*> st;

后序需要带标记的栈： stack<struct flagNode> sk;

struct flagNode

{

struct tree *ptr;

bool right;

}

前序遍历：

   cout << "前序遍历\n";
    p = root;
    while(p != NULL || !st.empty())
    {
        if(p != NULL)
        {
            cout << p->data << ' ';
            if(p->rchild != NULL)
                st.push(p->rchild);
            p = p->lchild;
        }
        else
        {
            p = st.top();
            st.pop();
        }
    }
    cout << endl;

中序遍历：

   cout << "中序遍历\n";
    p = root;
    while(p != NULL || !st.empty())
    {
        if(p != NULL)
        {
            st.push(p);
            p = p->lchild;
        }
        else
        {
            cout << st.top()->data << ' ';
            p = st.top()->rchild;
            st.pop();
        }
    }
    cout << endl;

后序遍历：

   cout << "后序遍历\n";
    stack<flagNode> sk;
    struct flagNode w;
    struct tree *p = root; // traversal pointer
    while(p != NULL || !sk.empty())
    {
        if(p != NULL)
        {
            w.right = false;
            w.ptr = p;
            sk.push(w);
            p = p->lchild;
        }
        else
        {
            if(sk.top().right == false)
            {
                sk.top().right = true;
                p = sk.top().ptr->rchild;
            }
            else
            {
                cout << sk.top().ptr->data << ' ';
                sk.pop();
            }

        }
    }
    cout << endl;

原 二叉树非递归前序中序后序遍历的模板写法