树的后序遍历（迭代版本）

#include <iostream>
#include <stack>

struct TreeNode
{
    int data;
    TreeNode *lchild;
    TreeNode *rchild;
};

using pNode = TreeNode *;

pNode create(int v)
{
    pNode node = new TreeNode;
    node->lchild = node->rchild = nullptr;
    node->data = v;
    return node;
}

void insert(pNode root, int v)
{
    pNode node = create(v);
    if (root == nullptr)
    {
        return;
    }
    pNode p = root;
    pNode r = nullptr;
    while (p && p->data != v)
    {
        r = p;
        if (v < p->data)
        {
            p = p->lchild;
        }
        else
        {
            p = p->rchild;
        }
    }
    if (p == nullptr)
    {
        if (v < r->data)
        {
            r->lchild = node;
        }
        else
        {
            r->rchild = node;
        }
    }
}

void in_order(pNode root)
{
    if (root == nullptr)
    {
        return;
    }
    in_order(root->lchild);
    std::cout << root->data << " ";
    in_order(root->rchild);
}

void post_order(pNode root)
{
    pNode p = root;
    pNode pre = nullptr;
    std::stack<pNode> s;
    while (p || !s.empty())
    {
        if (p)
        {
            s.push(p);
            p = p->lchild;
        }
        else if (s.top()->rchild && pre != s.top()->rchild)
        {
            p = s.top()->rchild;
        }
        else
        {
            pre = s.top();
            std::cout << pre->data << " ";
            s.pop();
        }
    }
}

int main()
{
    pNode root = nullptr;
    root = create(7);
    insert(root, 3);
    insert(root, 9);
    insert(root, 0);
    insert(root, 2);
    insert(root, 1);
    insert(root, 9);
    insert(root, 8);
    insert(root, 10);
    post_order(root);
    std::cout << std::endl;
}

yx@YX-PC:~$ make
g++ test.cpp
./a.out
1 2 0 3 8 10 9 7 
rm a.out