考虑这样一种情况:你有两个节点列表,其中你知道的一个是一个树的前序遍历的表示,另一个是同一树的后序遍历的表示.
我相信可以从这两个列表中精确地重建树,我想我有一个算法来做,但还没有证明.由于这将成为硕士项目的一部分,我需要绝对确定它是可能的和正确的(数学证明).然而,它不会是项目的重点,所以我想知道是否有一个来源(即纸张或书籍)我可以引用证明.(也许在TAOCP？有人可能知道这部分吗？)
简而言之,我需要在可引用资源中使用经过验证的算法,该算法可以从其前后顺序遍历中重构树.
注意:有问题的树可能不是二元的,或者是平衡的,或者任何使它太容易的东西.
注意2:仅使用预订单或后序列表会更好,但我认为不可能.
注3:节点可以有任意数量的子节点.
注4:我只关心兄弟姐妹的顺序.当只有一个孩子时,左或右并不重要.