从预订单和后序列表重建树

Question

考虑这样一种情况:你有两个节点列表,其中你知道的一个是一个树的前序遍历的表示,另一个是同一树的后序遍历的表示.

我相信可以从这两个列表中精确地重建树,我想我有一个算法来做,但还没有证明.由于这将成为硕士项目的一部分,我需要绝对确定它是可能的和正确的(数学证明).然而,它不会是项目的重点,所以我想知道是否有一个来源(即纸张或书籍)我可以引用证明.(也许在TAOCP？有人可能知道这部分吗？)

简而言之,我需要在可引用资源中使用经过验证的算法,该算法可以从其前后顺序遍历中重构树.

---

注意:有问题的树可能不是二元的,或者是平衡的,或者任何使它太容易的东西.

注意2:仅使用预订单或后序列表会更好,但我认为不可能.

注3:节点可以有任意数量的子节点.

注4:我只关心兄弟姐妹的顺序.当只有一个孩子时,左或右并不重要.

Answer 1

预购和后序并不唯一地定义树.

通常,单个树遍历不会唯一地定义树的结构.例如,正如我们所看到的,对于以下两个树,一个inorder遍历产生[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]匹配上面第一棵树的遍历.

Answer 2

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

这是我尝试解决方案:

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

您的邮政订单遍历可以确定树的深度.例如,假设我有这样的结构:

      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