二叉树后序非递归遍历

问题

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

思路

二叉树的后序非递归遍历是三种遍历中实现最为复杂的一个，麻烦在于它的遍历顺序为左，右，中。没有中间节点将它们联系起来，每次都是独立的过程。

思路1：两个栈实现。一个S1栈实现类似[前序非递归的遍历 ]前序非递归的遍历，得到中，右， 左。S1出栈后，不直接打印，而是压入S2。待整个树遍历完，所有节点也都全部压入S2栈内。最后统一弹出，得到左，右，中。

思路2：一个栈实现。我们需要两个变量。一个记录当前节点c，一个记录最近打印节点h。一开始就将根结点直接压入栈中。

左右孩子节点入栈规则：
若该节点有左孩子，且h既不是其左孩子，又不是其右孩子。左孩子入栈
若该节点有右孩子，且h不是其右孩子。右孩子入栈

栈顶节点出栈规则：
从左孩子返回，则左子树遍历完毕，开始遍历右子树 从右孩子返回，则右子树遍历完毕 整颗子树遍历完毕，弹出栈顶元素，并打印节点

代码如下

struct treeNode
{
    int data;
    treeNode *l;
    treeNode *r;

    //构造函数设置每个节点的左右孩子为空
    public: treeNode(int data)
    {
        this->data = data;
        this->l = NULL;
        this->r = NULL;
    }
};

void posOrderUnRecur(treeNode *h)
{
    if (h != NULL)
    {
        //栈必须保存树的节点指针treeNode*
        stack<treeNode*> stack;
        stack.push(h);
        treeNode* c = NULL;
        while (!stack.empty())
        {
            c = stack.top();
            // 第一个if中的h != c->r判断必须要，如果不加，从右子树返回
            // 的节点会再一次压入栈中
            if (c->l != NULL && h != c->l && h != c->r)
            {
                stack.push(c->l);
            }
            else if (c->r != NULL && h != c->r)
            {
                stack.push(c->r);
            }
            else
            {
                cout << (stack.top())->data << endl;
                stack.pop();
                h = c;
            }
        }
    }
}

int main()
{
    treeNode *t1 = new treeNode(1);
    treeNode *t2 = new treeNode(2);
    treeNode *t3 = new treeNode(3);
    treeNode *t4 = new treeNode(4);
    treeNode *t5 = new treeNode(5);
    treeNode *t6 = new treeNode(6);

    t1->l = t2; t1->r = t3;
    t2->l = t4; t2->r = t5;
    t3->l = t6;
    posOrderUnRecur(t1);
}

struct treeNode中构造函数对创建的节点初始化，使建树时，只需关注各节点之间的关系，而无需一一单独对叶子节点添加左右空孩子

有两个地方的代码实现值得注意：栈中保存的元素类型最好是指针形式。若栈中保存的是节点，作if判断时，需要重载==运算符。其次在出栈之前，必须用指针c更新h，因为判断进栈的条件是对指针进行比较