c - 有没有办法在不构建树的情况下从后序遍历中找到严格二叉树的前序遍历？

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

去年关闭。




Improve this question




我得到了严格二叉树的后序遍历，并被要求找到它的前序遍历。通常，我会先构建树，然后找到前序遍历。但是，我想知道是否有任何方法可以在不实际构建树的情况下找到预序遍历。

Answer 1

[ 编辑 :我首先回答了这个问题，假设给定的后序来自严格排序的二叉搜索树。 OP 现在指出了我的错误并提供了一个例子。然而，两种算法的基本原理是相同的:找到左右子树之间的边界。]

让我们考虑以下全二叉树的后序遍历，其中每个节点要么是叶子要么是具有两个叶子的分支:

1, 2, B, 3, 4, D, 5, C, A

我们知道数字是叶子，字母是 Twig 。我们也知道节点 A 是根，因为它在后序遍历中排在最后。为了重构前序遍历，我们必须存储根，然后考虑左子树，然后递归地考虑右子树。

但是哪些节点属于左子树，哪些属于右子树？在完整或 strictly binary tree有 L 个叶子，有 N = 2·L − 1 个节点。所以在存储了根之后，我们从右边遍历剩余的子数组并跟踪节点数 N 和叶子数 L。当条件 N = 2·L − 1 为真时，我们停止。我们看到的一切都属于右子树，其余的属于左子树。

所以:

int is_leaf(int c)
{
    return !isalpha(c);     // non-alphas are leaves
}

void reconst(int **pre, const int *post, int lo, int hi)
{
    printf("%d :: %d\n", lo, hi);

    if (lo < hi) {
        int k = --hi;           // will be boundary between l/r
        int root = post[k];
        int leaves = 0;
        int nodes = 0;

        while (k > lo && nodes != 2 * leaves - 1) {
            if (is_leaf(post[k - 1])) leaves++;
            nodes++;
            k--;
        }

        *(*pre)++ = root;
        reconst(pre, post, lo, k);
        reconst(pre, post, k, hi);
    }
}

像这样调用它:

int post[] = {'1', '2', 'B', '3', '4', 'D', '5', 'C', 'A'};
int n = 9;
int pre[9];
int *p = pre;
int i;

reconst(&p, post, 0, n);

for (i = 0; i < n; i++) {
    printf("%c ", pre[i]);
}

puts("pre");

上面的代码依赖于几件事: (a) pre数组必须与 post 一样大数组来保存重建的预购。 (b) 输入必须格式良好。该算法依赖于找到正确的完整子树。 (计数器防止超出下限，但仅此而已。)

[试图从没有重复值的二叉搜索树的后序中找到前序的原始帖子，即严格排序。不错的答案，但因为误解了要求，而不是 OP 想要的。对于那个很抱歉。]

假设你得到一个像这样的后序遍历:

3, 1, 7, 9, 8, 5

您知道顶部节点是 (5)，所有较小的节点 (3, 1) 都在左分支中，所有较大的节点 (7, 8, 9) 都在右分支中。顶部节点在先序遍历中首先进入。这样做，然后在代表左分支的子数组上递归，然后是右分支。

这是一个执行此操作的函数:

void reconst(int **pre, const int *post, int lo, int hi)
{
    if (lo < hi) {
        int k = --hi;                // k will be the boundary between l/r
        int parent = post[k];        // remove parent from this subarray

        // find boundary between left and right branches
        while (k > lo && post[k - 1] > parent) k--;

        *(*pre)++ = parent;          // write parent to pre-order array
        reconst(pre, post, lo, k);   // do the left subarray
        reconst(pre, post, k, hi);   // do the right subarray
    }
}

pre数组通过指向指针的指针填充:顶级指针跟踪 pre 中的位置。数组，二级指针访问底层数组。 (你可以传递一个数组和一个索引，如果这太巴洛克了，你可以前进。)

像这样调用函数:

int post[] = {3, 1, 7, 9, 8, 5};
int n = 6;
int pre[6];
int *p = pre;
int i;

reconst(&p, post, 0, n);

for (i = 0; i < n; i++) {
    printf("%d ", pre[i]);
}

puts("pre");

当然，保存前序数据的数组必须和后序数组一样大。从后序数据重建树的代码看起来非常相似，所以我不知道这是否真的符合条件。