问树根节点的迭代后序遍历断裂

EN

也许在您使用的测试用例中，只有根处有一个无限循环，但我认为无限循环也可能发生在树的其他地方，这取决于特定的树。

问题是，我认为，当右侧存在子元素时，不能正确地继续弹出堆栈。

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

在第一个循环中，我们将1和0推到堆栈上。那么0没有左子，所以根变成空。堆栈不是空的，所以我们继续。0位于堆栈的顶部，没有正确的子级，因此我们输入if语句的第一个分支。然后我们打印出0，因为0是1的左子-- 1现在是堆栈的顶部--根目录变成2。

在这一点上，我们回到顶端。2是根，并被推到堆栈上。2没有左子，所以根目录变为空。堆栈不是空的。2在堆栈的顶部。它有一个正确的子项，所以我们输入if语句的第二个分支。这就形成了3的根。

我们回到外环的顶端。3是根，然后被推到堆栈上。3没有左子，所以根变为空。堆栈不是空的。3没有正确的子项，所以我们输入if语句的第一个分支。我们打印出3，因为3是2的正确子-- 2现在在堆栈的顶部--我们从堆栈中弹出2，打印出2，根目录变为空。

我们回到循环的顶端。根已经是空的，所以没有任何东西被推到堆栈上。堆栈不是空的。1在堆栈的顶部。此时，正确的做法是从堆栈中弹出1，因为我们已经处理了它的正确子级；但是，1位于堆栈的顶部，并且确实有一个正确的子级，因此我们输入if语句的第二个分支，2成为根。情况与前两段完全相同，堆栈上只有1个元素，根元素有2个，因此我们得到了一个无限循环。

如果我们更改了示例，使3也有一个正确的子程序名为4，那么，如果我正确地阅读，我们将永远不会打印出2，并循环打印出4和3。

要纠正这个问题，您应该继续弹出堆栈，只要您正在处理的元素是堆栈顶部的正确子元素。我还没有编译或测试过这一点，但我认为编写这样的东西是可行的

    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
        }
    }