从树的预排序和后排序列表重建树

您不能只使用一个列表,因为您将无法了解树的深度。因此,您肯定需要两个或更多列表。

下面是我的一个解决方案:

使用预排序遍历作为了解数据顺序的方法。这是有意义的,因为您知道第一个节点是顶部,并且您知道遍历左侧更远处的数据属于树的左侧,等等。

后序遍历可以确定树的深度。例如,假设我有这样一个结构:

      1
  2   5   6
 3 4  7

Where 2 is the parent of 3 and 4, and 5 is the parent of 7.

Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1

我们知道我们从1开始,因为它是预购遍历中的第一个节点。然后我们看下一个数字,2。在后序中,因为数字2在节点1之前,所以我们知道2必须是1的子级。接下来我们看3。3在2之前,因此3是2的孩子。4是2之前3之后,所以我们知道4是2的孩子,而不是3的孩子。等。

现在,如果节点不是唯一的,这可能不起作用,但至少是解决方案的开始。

编辑: 这个解决方案保留了子级的顺序,这仅仅是因为通过预排序遍历了解节点的顺序,然后通过后排序遍历了解结构。

编辑2: 证据可能就在这里: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203

不过,我认为你需要购买文件……

以下是一份书面证明,作为解决方案:

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf

Preorder and postorder do not uniquely define a tree.

通常,单个树遍历不能唯一地定义 树的结构。例如,正如我们所看到的,这两个方面 下面的树,一个无序的遍历产生[1,2,3,4,5,6]。

    4                     3
   / \                   / \
  2   5                 2   5
 / \   \               /   / \
1   3   6             1   4   6

对于预订单和后订单,同样存在歧义。 遍历。上面第一棵树的预排序遍历是 [4、2、1、3、5、6]。这是一棵不同的树,有相同的预订 遍历。

    4
   / \
  2   1
     / \
    3   6
     \
      5

同样,我们可以很容易地构建另一个树,它的后序 遍历[1,3,2,6,5,4]与上面第一棵树的匹配。

考虑任意树 T 作为四联(A,B, C , D ,其中a是根节点,b是第一个子节点的根节点, C 是b的任何非空子代的向量,并且 D 是b的任何非空兄弟姐妹的向量。 C 和 D 它们本身就是树。

任何A,B, C 和 D 可能是空的。如果B是空的,那么必须是 C 和 D 如果是,那么一切。

由于节点是唯一的,因此包含在 C 和 D 是不相交的,两者都不包含a或b。

功能 前() 和 后() 生成表单的有序序列:

预(t) =,A,B, 预(前) C ) , 预(前) D ) ]

柱(t) = 帖子( C ) , 帖子( D ) ,a]

其中,应用于向量的函数被定义为序列的串联,这是将函数依次应用于每个元素所产生的结果。

现在考虑这些案例:

• 如果a为空,则两个函数的输出都是空序列[]
• 如果b为空,则两个函数的输出只是[a]
• 如果 C 和 D 是空的, 预(t) = [a,b] 柱(t) = [b,a]
• 如果只是 C 是空的, 预(t) =,A,B, D’ 及 柱(t) = D’ ,a)(其中素数表示包含在 D )
• 如果只是 D 是空的, 预(t) =,A,B, C’ 及 柱(t) = C’ ,b,a]
• 如果没有空的, 预(t) =,A,B, C’ , D’ 及 柱(t) = C’ , D’ ,a]

在所有情况下,我们都可以使用a和b(如果存在)作为定界符,明确地将两个输出序列的成员划分为适当的子序列。

问题是,我们也可以对向量序列进行划分吗?如果可以的话,那么每一个都可以被递归处理,我们就完成了。

因为结果 前() 总是一连串的序列 启动 有一个节点,结果是 后() 总是一连串的序列 结束 有了一个节点,我们真的可以把它们分开, 假如 A节点从不为空。

对于具有独立空的固定子级的二叉树(或任何树),这就是进程下降的地方。然而,在我们的案例中,我们已经定义了 C 和 D 只包含非空节点,因此重建是可以保证的。

嗯,我想是的,不管怎样。显然,这只是一个论点,而不是一个正式的证据!

使用此限制创建二叉树,其中至少有一个节点只有一个子节点(右或左,没有区别)。

现在,写下它的预订单和后订单列表。然后尝试从这些列表中重建树。你知道在那个节点上,你不能决定它的子节点是右的还是左的。

正如其他人已经指出的,二叉树不能只用前序和后序遍历来重建。单个子节点具有不明确的遍历,无法确定它是左子节点还是右子节点,例如,请考虑以下预排序和后排序遍历: 前序:A,B 后订单B

它可以同时产生以下两种树木

A \/ 乙乙 如果没有诸如无序遍历之类的任何附加信息,就不可能知道B是A的左子还是右子。

如果节点的名称是唯一的,那么预排序和后排序遍历就足以重建树。创建这样做的算法的关键是理解

x是y的祖先,如果x在前序中先于y,在后序中在y之后。

因此,我们总是可以找到任何节点的所有子节点。X的后代总是紧跟在前序的X之后,在后序的X之前。因此,一旦我们知道我们有兴趣生成在x上生根的子树,我们就可以提取在x上生根的子树的前序和后序遍历。这自然会导致递归算法,一旦我们意识到x后面的节点必须是它的最左边的子节点,如果它是一个后代的话。

还有一个基于堆栈的实现,它遍历预订单节点,并将任何候选节点保留在堆栈上,以作为下一个预订单节点的直接父节点。对于每个预订单节点,重复地将不是下一个预订单节点父节点的所有节点从堆栈中弹出。使该节点成为堆栈上顶部节点的子节点,并将该子节点推到堆栈上。

不可能从预排序和后排序遍历构造一个通用的二叉树(请参阅此部分)。但是,如果知道二叉树是满的,我们就可以在不产生歧义的情况下构造二叉树。让我们通过下面的例子来理解这一点。

让我们将这两个给定数组视为pre[]=1、2、4、8、9、5、3、6、7和post[]=8、9、4、5、2、6、7、3、1_ 在前[]中,最左边的元素是树的根。因为树已满,数组大小大于1。[]之前的1旁边的值必须是根的子级。所以我们知道1是根,2是留子。如何查找左子树中的所有节点?我们知道2是左子树中所有节点的根。post[]中2之前的所有节点都必须在左子树中。现在我们知道1是根,元素8、9、4、5、2在左子树中,元素6、7、3在右子树中。

              1
            /   \
           /      \
 {8, 9, 4, 5, 2}     {6, 7, 3}

我们递归地遵循上面的方法并得到下面的树。

      1
    /   \
  2       3
/  \     /  \

4 5 6 6 / \
8 9