迭代后序遍历在树的根节点中断

Question

我实现了一种迭代打印二叉树后序遍历的算法。整个算法都有效，除了它在到达树的根部时进入无限循环。

有人能指出我正确的方向吗？我已经被这个问题困扰了 2 天了。

void postorder_nonrec_2(treenode *root)
{
    stack_t *s;
    stack_init(&s, 100);
    treenode *temp = root;

    while(1)
    {
        while(root)
        {
            push(s, root);
            root = root -> left;
        }

        if(stack_isEmpty(s))
            break;

        if(!top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);

            if(root == top(s) -> left)
            {
                root = top(s) -> right;
            }
            else if(root == top(s) -> right)
            {
                printf("%d ", pop(s) -> data);

                root = NULL;
            }
        }
        else
        {
            root = top(s) -> right;
        }

    }
}

Answer 1

也许你使用的测试用例，只有根部有无限循环，但我认为无限循环也可能发生在树的其他地方，具体取决于具体的树。

问题我觉得是当children存在右边的时候你没有正确的继续弹出栈

考虑一个简单的例子，我们有一个根节点 1，左 child 0 和右 child 2，并假设 2 有一个名为 3 的右 child。

在第一个循环中，我们将 1 和 0 压入堆栈。那么0就没有左child了，所以root就变成了null。堆栈不为空，所以我们继续。 0在栈顶，没有权利child，所以我们进入if语句的第一个分支。然后我们打印出 0，因为 0 是 1 的左边 child——1 现在是栈顶——根变成 2.

至此我们return到了顶部。 2 是根并被压入堆栈。 2 没有左child，所以根变为空。堆栈不为空。 2 在堆栈的顶部。它有一个正确的child，所以我们进入if语句的第二个分支。这使 3 成为根。

我们return到外循环的顶部。 3 是根并被压入堆栈。 3 没有左child，所以根变为空。堆栈不为空。 3没有权利child，所以我们进入if语句的第一个分支。我们打印出 3。然后因为 3 是 2 的右边 child -- 2 现在在堆栈的顶部 -- 我们将 2 弹出堆栈，打印出 2，并且根变为空。

我们return到循环的顶部。根已经为空，因此没有任何内容被压入堆栈。堆栈不为空。 1 在堆栈的顶部。此时正确的做法是从堆栈中弹出 1，因为我们已经处理了它的右边 child；然而，1 在堆栈的顶部并且确实有一个右 child，因此我们进入 if 语句的第二个分支并且 2 成为根。情况和前两段完全一样，1是栈上唯一的元素，2是根，所以我们得到一个无限循环回到那里。

如果我们更改示例，使 3 也有一个名为 4 的权利 child，那么，如果我没看错的话，我们将永远不会打印出 2，而是会循环打印出 4 和 3。

要更正此问题，只要您正在处理的元素位于堆栈顶部的右侧 child，您就应该继续弹出堆栈。我还没有编译或测试过这个，但我认为写一些像

这样的东西会奏效

    if (!top(s) -> right)
    {
        root = pop(s);
        printf("%d ", root -> data);

        while (!stack_isEmpty(s) && root == top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);
        }
        if (!stack_isEmpty(s) && root == top(s) -> left)
        {
            // checking root == top(s) -> left is probably redundant,
            // since the code is structured so that root is either
            // a child of top(s) or null if the stack is not empty
            root = top(s) -> right;
        }
        else
        {
            root = NULL;
            // could actually break out of outer loop here, but
            // to be more consistent with code in the question
        }
    }

Answer 2

发布此答案以提供@Evan VanderZee 建议的解决方案的完整代码

void postorder_nonrec_2(treenode *root)
{
    stack_t *s;
    stack_init(&s, 100);


    while(1)
    {
        while(root)
        {
            push(s, root);
            root = root -> left;
        }

        if(stack_isEmpty(s))
            break;

        if (!top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);

            while (!stack_isEmpty(s) && root == top(s) -> right)
            {
                root = pop(s);
                printf("%d ", root -> data);
            }

            root = NULL;
        }
        else
        {
            root = top(s) -> right;
        }
    }
}

迭代后序遍历在树的根节点中断

Iterative postorder traversal breaks at root node of tree

c

algorithm

data-structures

binary-tree

postorder