考虑这样一种情况,您有两个节点列表,您所知道的只是一个节点表示某个树的预遍历遍历,另一个表示同一棵树的后序遍历。
我相信可以从这两个列表中完全重建树,并且我认为我有一种算法可以做到,但尚未证明。因为这将是一个硕士项目的一部分,所以我必须绝对确定这是可能且正确的(已通过数学证明)。但是,这不会成为项目的重点,因此我想知道是否可以使用该资源(例如纸质或书籍)作为证明。(也许在TAOCP中?有人知道该部分吗?)
简而言之,我需要一种在报价资源中经过验证的算法,该算法可以根据其前后顺序遍历来重建树。
注意:所讨论的树可能不会是二叉树,平衡树,也不会是任何容易的树。
注意2:仅使用预购或后购清单会更好,但是我认为这是不可能的。
注意3:一个节点可以有任意数量的子代。
注意4:我只关心兄弟姐妹的顺序。只有一个孩子时,左或右无关紧要。
您不能只使用一个列表,因为您将无法理解树的深度。因此,您肯定需要两个或多个列表。
这是我尝试的解决方案:
使用预遍历作为了解数据顺序的一种方法。这是有道理的,因为您知道第一个节点是顶部,并且知道遍历左侧的数据属于树的左侧,依此类推。
您的订单遍历可以确定树的深度。例如,假设我有一个这样的结构:
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的孩子。
现在,如果节点不是唯一的,则这可能不起作用,但至少是解决方案的开始。
编辑: 使用此解决方案可以保留子项的顺序,这仅是由于通过预顺序遍历了解节点的顺序,然后通过后顺序遍历了解结构。
我认为您需要购买该文档,但是…
以下是作为解决方案的书面证明:
http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa- cse/tutorials/tutorial09-solutions.pdf