获取后序遍历树的最佳算法

Question

我有一棵包含大量节点的树，希望寻找最佳后序遍历算法。

注意:

1. 该算法不应考虑递归，因为大量节点可能导致堆栈溢出异常。
2. 该算法不应考虑视图标志。
3. 该算法不应对树结构进行更改，我需要它保持原样。
4. 算法应明智地使用内存。
5. 在一个节点中，我可以获取父节点的信息。

- Aboelnour

---

除非你的树实际上有成千上万个层级，否则递归不应该是一个问题。 - biziclop

你已经考虑并尝试过什么了呢？如果树的深度足够大，以至于耗尽了所有的堆栈，那么 Continuation Passing 是你的好朋友。请考虑以下 Stack OverFlow 问题的答案：https://dev59.com/p2ox5IYBdhLWcg3wQSKp - kkm

刚刚遍历一个抽象语法树.. + 我读到这个并且想问有没有人解决了它的后序遍历问题，“在1968年，Knuth提出了一个问题，设计一种无需堆栈、标签和递归的算法，能够按照中序遍历方式遍历树，并且最终保持树的不变。” - Aboelnour

Answer 1

有了父节点的可用性，可以进行迭代而不需要使用堆栈：该算法假设每个节点都有父节点、第一个子节点和下一个兄弟节点。

#include <stdio.h>

struct Node {
    int Data; Node *FirstChild, *NextSibling, *Parent;
};

void use_data(Node *node) {
    printf("%d\n", node->Data);
}

int main_visit_post(int, char **) {
    Node G[] = {
        {0, G+1,   0,   0},
        {1, G+2, G+3, G+0},
        {2,   0, G+4, G+1},
        {3, G+8,   0, G+0},
        {4, G+5, G+7, G+1},
        {5,   0, G+6, G+4},
        {6,   0,   0, G+4},
        {7,   0,   0, G+1},
        {8, G+9,   0, G+3},
        {9,   0,   0, G+8},
    };

    Node *node = G, *next;
    while (node) {
        next = node->FirstChild;
        if (!next) {
            use_data(node);
            next = node->NextSibling;
            if (!next) {
                while (node->Parent) {
                    next = node->Parent;
                    use_data(next);
                    if (next->NextSibling) {
                        next = next->NextSibling;
                        break;
                    }
                    else {
                        node = next;
                        next = 0;
                    }
                }
            }
        }
        node = next;
    }
    return 0;
}

这棵树的遍历顺序是：2、5、6、4、7、1、9、8、3、0。

- CapelliC

Answer 2

一种不使用标志或递归来解决这个问题的方法是简单地使用堆栈。对于后序遍历，我们可以使用两个堆栈。一个堆栈用于操作输入，另一个堆栈用于生成输出。

您可以在此处找到代码的详细信息。

- saurcery

---

实际上，您可以使用一个堆栈来完成它。http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal - Aboelnour