logo标签列表

从前序遍历和后序遍历列表重建树

algorithmlanguage-agnosticreferencetreetraversal
25
考虑这样一种情况，你有两个节点列表，你只知道其中一个代表某棵树的前序遍历，另一个代表同一棵树的后序遍历。
我相信可以从这两个列表完全重建树，而且我认为我有一种算法可以实现它，但还没有证明。由于这将是研究生项目的一部分，我需要绝对确定它是可能的和正确的（在数学上被证明）。但它不会成为项目的重点，所以我想知道是否有可引用的来源（例如论文或书籍）证明了这一点。（也许在TAOCP中？ 有人知道可能的章节吗？）
简而言之，我需要一种已经被证明的算法，在可引用的资源中，从其前序和后序遍历中重构出一棵树。
注意：所讨论的树可能不是二叉树，或平衡树，或者任何能够使它变得轻松的东西。
注2：仅使用前序或后序列表甚至更好，但我认为这是不可能的。
注3：一个节点可以有任意数量的子节点。
注4：我只关心兄弟姐妹的顺序。 当只有一个孩子时，左右并不重要。
我认为你需要澄清一下，你所说的树是指一个节点可能有任意数量的子节点。通常，树被定义为每个节点恰好有两个子节点，其中一个或两个子节点可以是“空”。在这种情况下，无法从前序遍历和后序遍历中重构树，因为你无法确定单个子节点是“左子节点”还是“右子节点”（请参见此处的讨论：http://profile.iiita.ac.in/pkmallick_03/pages/3_16.html）。 - Martin B
我提出的解决方案可以处理任意数量的子元素，并且可以正确地保留它们的顺序。 - AlbertoPL
顺便说一下，我认为证明这个问题的方法是通过反例。假设所描述的技术不起作用，然后找到一个矛盾。这只是一种直觉，但我认为这是正确的方法。 - AlbertoPL
仅澄清一下，反例证明最多只能给出一个存在性证明，而不能得到实际的算法。"假设它不起作用"的问题在于你必须假设任何可能导致它不起作用的原因和组合。 - MSalters
这是我的谷歌面试问题 ;) - JohnJohnGa
显示剩余5条评论
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] 与上述第一棵树相匹配。

1
啊...但我并不关心左孩子还是右孩子，只关心兄弟节点的顺序。我会编辑我的问题。感谢你提供的信息。+1。 - NomeN
这些遍历确实不能唯一地标识树。然而，如果包括空/叶节点，则遍历顺序可以唯一地标识树。 - Captain_Obvious
10

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

以下是我的解决方案：

使用先序遍历来确定数据的顺序。这很有意义，因为你知道第一个节点是顶部，而且你知道在遍历中更靠左的数据属于树的左侧等等。

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

      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
6
如果整个SO社区都不能证明它是错的，那么它可能是正确的 :P - AlbertoPL
我也是这样，因此问题就出现了...即使我擅长写证明，使用它也可以节省大量时间。 - NomeN
请检查我刚刚添加的第二个来源，它是该问题的书面解决方案。 - AlbertoPL
我担心这两个来源都是关于二叉树的。我不确定它是否可以推广到具有任意数量子节点的树。 - NomeN
1
虽然这不是你需要的，但这里有第一篇文章的免费版本--http://ntur.lib.ntu.edu.tw/bitstream/246246/2007041910032125/1/00017225.pdf。 - Richard Dunlap
显示剩余5条评论
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()生成形如以下有序序列： pre(T) = [A, B, pre(C), pre(D)] post(T) = [post(C), B, post(D), A]
其中应用于向量的函数被定义为串联依次对每个元素应用函数产生的序列。
现在考虑以下情况：
1. 如果A为空，则两个函数的输出是空序列[]。
2. 如果B为空，则两个函数的输出仅为[A]。
3. 如果C和D都为空，则pre(T)=[A, B]，post(T)=[B, A]。
4. 如果只有C为空，则pre(T)=[A, B, D']，post(T)=[B, D'', A]（其中撇号表示包含在D中的节点的某种排列）。
5. 如果只有D为空，则pre(T)=[A, B, C']，post(T)=[C'', B, A]。
6. 如果都不为空，则pre(T)=[A, B, C', D']，post(T)=[C'', B, D'', A]。
在所有情况下，我们可以通过使用A和B（如果存在）作为分隔符，将两个输出序列的成员无歧义地划分为适当的子序列。
那么问题是，我们能否也对向量序列进行分区？如果可以的话，每个向量序列都可以递归处理，我们就完成了。
由于pre（）的结果始终是以A节点开头的一系列序列，并且post（）的结果始终是以A节点结尾的一系列序列，因此我们确实可以将它们分割成几部分，前提是A节点永远不为空。
然而，在具有可能独立为空的固定子节点的二叉（或任何）树的情况下，这个过程失败了。但在我们的情况下，我们定义C和D仅包含非空节点，因此重建保证能够成功。
呃，我想是这样。显然，这只是一个论点，不是正式的证明！
1
我相信你想出来的算法跟我脑海中的完全一样，最终我把它写成了一篇小论文，因为我找不到可引用的资源。其基本思想是，由于(子)树的根在前序和后序中的位置，你可以递归地重建树，所有孩子都将位于这些位置之间。第一个孩子是在前序中那些节点中最左边的，第二个是左边第一个不是第一个孩子的节点等依次构建。 - NomeN
非常感谢您的努力，但我必须说...这是不是太玄学了？（无论如何+1） - NomeN
我刚好看到了这篇文章的首页，正巧进来看看（多亏了Komal的无关回答），引起了我的兴趣。不如发一下你论文的链接，以备将来参考？ - walkytalky
1
前序和后序遍历足以重建树，假设节点具有唯一名称。创建算法的关键是要理解：
X 是 Y 的祖先当且仅当 X 在前序中在 Y 之前，在后序中在 Y 之后。
有了这个条件，我们就可以找到任何节点的所有子孙。X 的子孙总是紧随在 X 之后的前序中，并在后序中在 X 之前。因此，一旦我们知道我们要生成以 X 为根的子树，我们就可以提取以 X 为根的子树的前序和后序遍历。这自然地导致了递归算法，一旦我们意识到 X 后面的节点必须是它最左边的子节点，如果它是一个后代的话。
还有一种基于堆栈的实现，它通过迭代前序节点，并将任何可能成为下一个前序节点的直接父节点的节点保留在堆栈上。对于每个前序节点，重复弹出堆栈上不是下一个前序节点的父节点的所有节点。将该节点作为堆栈顶部节点的子节点，并将子节点推入堆栈。
1
正如其他人指出的那样，仅使用先序遍历和后序遍历无法重建二叉树。单个子节点具有模糊的遍历方式，不能确定它是左子节点还是右子节点，例如考虑以下先序遍历和后序遍历： 先序遍历：a，b 后序遍历：b，a
它可以生成以下两棵树：
a a \ / b b
没有任何其他信息（例如中序遍历），无法确定b是a的左子节点还是右子节点。
在这种情况下，我不关心左孩子还是右孩子，只需要知道它是唯一的孩子就足够了。所以，是的，我同意遍历在技术上是有歧义的，但如果一个单独的孩子只被表示为“一条向下的直线”，那么它对于树的形状并没有实际影响。 - NomeN
1
使用以下约束条件创建一棵二叉树，该树至少有一个节点，该节点只有一个子节点（右侧或左侧没有区别）。

现在，编写其前序和后序列表。然后尝试从这些列表重建树。您会意识到，在该节点上无法决定其子节点是右侧还是左侧。
首先，真是太酷了，居然还有这么多新的补充！对于二叉树，算法可以从《计算机程序设计艺术》中复制，但是给定的树可能不是二叉树（或者说以前不是），所以恐怕这个问题就无法使用那个算法了。 - NomeN
好的，但你可以将我的答案概括到任何其他树上（不一定是二叉树，二叉树是你可以对其进行指令的最简单的树），试试吧！我知道你能行！;-)))) - Maryam A
在“Note4”中，提问者提到，在只有一个孩子的情况下，他不关心左右。 - danfuzz
0

从先序遍历和后序遍历无法构建一般的二叉树（请参见此处）。但是，如果知道二叉树是满的，我们可以无歧义地构建树。让我们通过以下示例来了解这一点。

假设我们将两个给定的数组视为pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7}和post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1}; 在pre[]中，最左边的元素是树的根。由于树是满的且数组大小大于1。在pre[]中，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 7 / \
8 9

1
你说“看这个”，但是那里没有链接。 - dfeuer
仅使用中序遍历足以重建一个完整的二叉树吗：所有层级都是满的，最后一层从左侧开始？ - Drimades Boy
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接