当给出的唯一信息是后遍历时，如何构造严格的二叉树？

Question

[以前，我只在获得后遍历遍历后问过如何获得一棵树的前订购。但是，现在我很好奇，当只给定后遍历遍历时，如何构建一棵严格的二叉树（严格的二叉树意味着一个节点有两个孩子或没有孩子）。我正在处理的一些示例数据：

7 8 2 // 8,2 are dimensions stored in the node, likewise for other nodes)
6 4 8
3 1 5
A
B

我知道树应该是什么样子：

               B
            /     \
           7       A
                 /    \
                6      3

但是我不知道如何编写一个函数，该函数实际上将根据给定的信息（后置遍历）构建此树（并存储在节点中的信息中。）我该怎么做？

Answer 1

根据后置顺序创建完整的二叉树，就像仅使用二元运算符从Reverse Polish Notation中创建语法树一样。分支是运算符，叶子是值。 （您必须能够分辨出哪个是哪个。在您的示例中，桦树是字母，树叶是数字。）

您可以处理数据。如果它是叶子，则创建一个节点并将其压入堆栈。它是一个分支，创建一个节点，将其左右分支弹出堆栈，然后推送新节点。如果收到的数据有效，则堆栈上应该有一个节点。那就是你的树的根。

因此，使用伪ish C代码：

Node *head = NULL;

while (!stream_empty()) {
    int data = stream_get();

    if (is_leaf(data)) {
        if (nstack == MAX) fatal("Stack overflow!");

        stack_push(make_node(data));
    } else {
        if (stack_size < 2) fatal("Stack underflow!");

        Node *node = make_node(data);

        node->right = stack_pop();
        node->left = stack_pop();
        stack_push(node);
    }
}

if (nstack != 1) fatal("Ill-formed full binary tree!");

head = stack[0];

当树的深度大于堆栈大小时，就会发生堆栈溢出。当输入数据格式不正确时，将在最后出现堆栈下溢或剩余节点。

这里是完整的example on ideone。

[Note：我已经完全重写了我的答案，因为OP已指定了新要求。我还以我原来对OP先前问题的回答为基础。我认为目前的做法更为优雅。不管that意味着什么。 :)]