25

考虑这样一种情况，您有两个节点列表，您所知道的是，一个是对某棵树的前序遍历的表示，另一个是对同一棵树的后序遍历的表示。

我相信完全可以从这两个列表中重建树，并且我认为我有一个算法可以做到这一点，但还没有证明。由于这将是硕士项目的一部分，我需要绝对确定它是可能的并且是正确的（经过数学证明）。然而，它不会是该项目的重点，所以我想知道那里是否有我可以引用的来源（即纸张或书籍）作为证明。（也许在TAOCP？有人可能知道该部分吗？）

简而言之，我需要一个在可引用资源中经过验证的算法，从它的前后顺序遍历中重建一棵树。

注意：有问题的树可能不是二元的，或平衡的，或任何使它太容易的东西。

注2：只使用预购或后购清单会更好，但我认为这是不可能的。

注意 3：一个节点可以有任意数量的子节点。

注4：我只关心兄弟姐妹的顺序。只有一个孩子时，左或右无关紧要。

4

7 回答 7

33

前序和后序不唯一地定义一棵树。

一般来说，单棵树的遍历并不能唯一地定义树的结构。例如，正如我们所见，对于以下两棵树，中序遍历产生 [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] 与上面第一棵树的后序遍历匹配。

于 2009-07-16T11:54:15.340 回答
9

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

这是我的解决方案尝试：

使用您的前序遍历作为了解数据顺序的一种方式。这是有道理的，因为您知道第一个节点是顶部，并且您知道遍历左侧的数据属于树的左侧，等等。

您的后序遍历可以确定树的深度。例如，假设我有这样的结构：

      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 的孩子。等等。

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

编辑：这个解决方案保留了孩子的顺序，这仅仅是因为通过前序遍历知道节点的顺序，然后通过后序遍历知道结构。

Edit2：证据可能在这里：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

于 2009-07-16T11:54:47.943 回答
4

将任意树T视为四元组 (A, B, C , D )，其中 A 是根节点，B 是第一个子节点的根节点，C是 B 的任何非空子节点的向量，D是 B 的任何非空兄弟的向量。C和D的元素本身就是树。

A、B、C和D中的任何一个都可以为空。如果 B 为空，则C和D也必须为空；如果A，那么一切。

由于节点是唯一的，因此包含在C和D中任何位置的节点集是不相交的，既不包含 A 也不包含 B。

函数pre()和post()生成以下形式的有序序列：

预（T） = [A，B，预（C），预（D） ]

帖子（T） = [帖子（C），B，帖子（D），A]

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

现在考虑以下情况：

  • 如果 A 为空，则两个函数的输出都是空序列 []
  • 如果 B 为空，则两个函数的输出只是 [A]
  • 如果C和D为空，则pre(T) = [A, B] 和 post(T) = [B, A]
  • 如果只有C为空，则pre(T) = [A, B, D' ] 和post(T) = [B, D'' , A] （其中素数表示D中包含的节点的某种排列）
  • 如果只有D为空，则pre(T) = [A, B, C' ] 和post(T) = [ C'' , B, A]
  • 如果没有一个为空，则pre(T) = [A, B, C' , D' ] 和post(T) = [ C'' , B, D'' , A]

在所有情况下，我们都可以通过使用 A 和 B（如果存在）作为分隔符，将两个输出序列的成员明确划分为适当的子序列。

那么问题是，我们也可以分割向量序列吗？如果可以，那么每个都可以递归处理，我们就完成了。

由于pre()的结果总是以 A 节点开头的序列链，而post()的结果总是以 A 节点结尾的序列链，我们确实可以将它们分开，前提是 A 节点永远不会是空的。

在具有固定子节点的二叉树（或实际上任何树）可能独立为空的情况下，这就是该过程失败的地方。然而，在我们的例子中，我们将C和D定义为仅包含非空节点，因此可以保证重建工作。

嗯，反正我是这么认为的。显然这只是一个论证，而不是正式的证明！

于 2010-04-22T18:43:09.330 回答
1

创建具有此限制的二叉树，该二叉树至少有一个节点，该节点只有一个孩子（右或左，没有区别）。

现在，编写它的预购和后购列表。然后尝试从这些列表中重建树。你意识到在那个节点上你不能决定它的孩子是右还是左。

于 2011-12-30T08:25:09.700 回答
1

假设节点是唯一命名的，前序和后序遍历足以重建树。创建算法的关键是理解

X 是 Y 的祖先，当且仅当 X 在前序中在 Y 之前并且在后序中在 Y 之后。

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

还有一个基于堆栈的实现，它遍历预排序节点，并将任何候选节点保留在堆栈上，作为下一个预排序节点的直接父节点。对于每个预购节点，重复从堆栈中弹出所有不是下一个预购节点的父节点的节点。使该节点成为堆栈顶部节点的子节点，并将子节点压入堆栈。

于 2013-10-09T20:28:03.993 回答
1

正如其他人已经指出的那样，仅使用前序和后序遍历不能重建二叉树。单个子节点具有不明确的遍历，无法识别它是左子还是右子，例如考虑以下前序和后序遍历：前序：a，b 后序 b，a

它可以产生以下两种树

aa \ / bb 如果没有像中序遍历这样的附加信息，根本不可能知道 b 是 a 的左孩子还是右孩子。

于 2015-11-02T07:27:18.043 回答
0

不可能从前序和后序遍历构造一个通用的二叉树（参见this）。但是如果知道二叉树是满的，我们就可以毫无歧义地构造二叉树。让我们借助以下示例来理解这一点。

让我们将两个给定数组视为 pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} 和 post[] = {8, 9, 4, 5, 2, 6, 7 , 3, 1}; 在 pre[] 中，最左边的元素是树的根。由于树已满且数组大小大于 1。pre[] 中 1 旁边的值必须是 root 的左孩子。所以我们知道 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 7 / \
8 9

于 2015-04-10T05:09:48.457 回答