小编典典

从其预购和后购清单重建树

algorithm

考虑这样一种情况,您有两个节点列表,您所知道的只是一个节点表示某个树的预遍历遍历,另一个表示同一棵树的后序遍历。

我相信可以从这两个列表中完全重建树,并且我认为我有一种算法可以做到,但尚未证明。因为这将是一个硕士项目的一部分,所以我必须绝对确定这是可能且正确的(已通过数学证明)。但是,这不会成为项目的重点,因此我想知道是否可以使用该资源(例如纸质或书籍)作为证明。(也许在TAOCP中?有人知道该部分吗?)

简而言之,我需要一种在报价资源中经过验证的算法,该算法可以根据其前后顺序遍历来重建树。


注意:所讨论的树可能不会是二叉树,平衡树,也不会是任何容易的树。

注意2:仅使用预购或后购清单会更好,但是我认为这是不可能的。

注意3:一个节点可以有任意数量的子代。

注意4:我只关心兄弟姐妹的顺序。只有一个孩子时,左或右无关紧要。


阅读 217

收藏
2020-07-28

共1个答案

小编典典

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

这是我尝试的解决方案:

使用预遍历作为了解数据顺序的一种方法。这是有道理的,因为您知道第一个节点是顶部,并且知道遍历左侧的数据属于树的左侧,依此类推。

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

      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的孩子。

现在,如果节点不是唯一的,则这可能不起作用,但至少是解决方案的开始。

编辑: 使用此解决方案可以保留子项的顺序,这仅是由于通过预顺序遍历了解节点的顺序,然后通过后顺序遍历了解结构。

Edit2:
证据可能在这里: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

2020-07-28