二叉树后序非递归遍历

问题

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

思路

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

思路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,因为判断进栈的条件是对指针进行比较