从前序和后序列表重建一棵树 [英] reconstructing a tree from its preorder and postorder lists
问题描述
考虑这样一种情况，您有两个节点列表，您只知道其中一个是某棵树的前序遍历的表示，另一个是同一棵树的后序遍历的表示.
Consider the situation where you have two lists of nodes of which all you know is that one is a representation of a preorder traversal of some tree and the other a representation of a postorder traversal of the same tree.
我相信可以完全从这两个列表中重建树，并且我认为我有一个算法可以做到这一点，但尚未证明.由于这将是硕士项目的一部分，我需要绝对确定它是可能的和正确的(数学证明).但是，它不会是项目的重点，所以我想知道是否有可以引用的来源(即论文或书籍)作为证明.(也许在 TAOCP 中?有人知道这个部分吗?)
I believe it is possible to reconstruct the tree exactly from these two lists, and I think I have an algorithm to do it, but have not proven it. As this will be a part of a masters project I need to be absolutely certain that it is possible and correct (Mathematically proven). However it will not be the focus of the project, so I was wondering if there is a source out there (i.e. paper or book) I could quote for the proof. (Maybe in TAOCP? anybody know the section possibly?)
简而言之，我需要在可引用资源中使用经过验证的算法，该算法可以根据前后序遍历重建一棵树.
In short, I need a proven algorithm in a quotable resource that reconstructs a tree from its pre and post order traversals.
注意:所讨论的树可能不是二元树、平衡树或任何会使它变得太容易的东西.
Note: The tree in question will probably not be binary, or balanced, or anything that would make it too easy.
注2:只使用前序或后序列表会更好，但我认为这是不可能的.
Note2: Using only the preorder or the postorder list would be even better, but I do not think it is possible.
注3:一个节点可以有任意数量的子节点.
Note3: A node can have any amount of children.
注4:我只关心兄弟姐妹的顺序.只有一个孩子时，左或右无所谓.
Note4: I only care about the order of siblings. Left or right does not matter when there is only one child.
推荐答案
你不能只使用一个列表，因为你不会感觉到树的深度.因此，您肯定需要两个或更多列表.
You cannot use only one list, because you'll get no sense of the depth of the tree. Thus, you definitely require two or more lists.
这是我尝试的解决方案:
Here's my attempt at a solution:
使用预序遍历作为了解数据排序的一种方式.这是有道理的，因为您知道第一个节点是顶部，并且您知道遍历左侧的数据属于树的左侧，依此类推.
Use your preorder traversal as a means of knowing the ordering of the data. This makes sense because you know the first node is the top, and you know that data further to the left of the traversal belongs to the left of the tree, etc.
您的后序遍历可以确定树的深度.例如，假设我有一个这样的结构:
Your post order traversal can determine the depth of the tree. For example, let's say I have a structure like this:
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 的孩子.等等.
We know we start with 1, because it is the first node in the preorder traversal. Then we look at the next number, 2. In the post order, because the number 2 comes BEFORE node 1, we know that 2 has to be a child of 1. Next we look at 3. 3 comes before 2, and thus 3 is a child of 2. 4 is before 2 but after 3, so we know 4 is a child of 2 but NOT a child of 3. Etc.
现在，如果节点不是唯一的，这可能不起作用，但至少它是解决方案的开始.
Now, this may not work if the nodes are not unique, but at the very least its a start to a solution.
这个解决方案保留了孩子的顺序，仅仅是因为通过前序遍历知道节点的顺序，然后通过后序遍历知道结构.
The order of the children is preserved with this solution, simply due to knowing the ordering of the nodes via the preorder traversal, and then knowing the structure via the postorder traversal.
我认为您需要购买文档，但是...
I think you need to purchase the document, however...
以下是作为解决方案的书面证明:
Here is a written proof presented to be a solution:
http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf
这篇关于从前序和后序列表重建一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
