algorithm - 从两个平面表示重新创建树

Question

我有一棵树的两个平面表示，例如:

List 1:        List 2:

Event1      Event1
Event1      State1
Event2      Event1
State1      Event2
Event2      Event2
Event1      State2
Event2      StateI1
StateI1     Event1
Event1      Event2
Event1      Event1
Event2      StateI2
StateI2     Event1
Event2      Event2
Event1      Event2
Event2      StateI3
StateI3     Event1
State2      Event2
Event3      Event3

树是:

Event1 
State1
  Event1 
  Event2 
Event2 
State2
  StateI1
    Event1 
    Event2 
  Event1 
  StateI2
    Event1 
    Event2 
  Event2 
  StateI3
    Event1 
    Event2 
Event3

如您所见，一个状态可以包含多个事件和状态。不要介意名称，它们无关紧要，它们只是表示元素的类型。

我相信第一个列表是深度优先、自下而上的树遍历，第二个列表是深度优先、自上而下的遍历。

我需要从两个平面列表中重新创建树，即将每个 State 或 Event 分配给其父 State(或顶层)。这可能吗？如果是，怎么办？

我的代码中基本上发生的是:

TraverseTreeBottomUpExecutingFunction(tree, &myfunc_bottomup)

second_list = TraverseTreeTopDown(tree)

recreated_tree = myfunc_recreate_tree(second_list, optional_first_list_created_using_myfunc_bottomup)

我无法更改 Traverse* 函数。

Answer 1

基本上，一棵不是二叉树的树可以按两个顺序遍历:前序(枚举卡在其上的子树之前的内部节点)和后序(枚举卡在其上的子树之后的内部节点)。我猜想在您的问题中，“自下而上”是后序，“自上而下”是前序。

让我们进一步假设所有对象都可以彼此分离，即它们具有不同的值或指针。如果所有对象都是相同的，即都是相同的状态，则不能仅从遍历列表推断出树的形状，因为它们看起来是相同的。

现在的问题是，如果有一棵树 T，并且前序和后序遍历为其生成节点列表，则该树的 ROOT 是前序列表中的第一个节点和后序列表中的最后一个节点。这为您提供了以下重建方法:

您有两个列表，前序和后序遍历节点列表。称这些为 R (pRe) 和 O (pOst)。

• R 的第一个元素是根节点。从 R 中删除它
• 从 O 中删除最后一个元素并检查它是否是同一个根节点(应该是)
• 现在检查R的第一个元素，它是最左边子树的根
• 从O中找到相同的节点；假设它是 O
上的第 k 个节点
• 现在最左边的子树上有 k 个节点；从列表 R 和 O 中取出前 k 个节点，并递归地执行此算法以重建最左边的子树
• 继续R和O的剩余部分，迭代这个，重构根节点的剩余子树

伪代码 - 返回树的递归过程。输入:两个遍历列表 r = preorder, o = postorder

def mktree(r, o):
  l = len(r)
  assert l == len(o)
  root = r[0]
  assert root == o[l - 1]
  if l == 1:
     return mknode(root)
  else:
     myroot = mknode(root)
     r = r[1:l]     # sublist that excludes first element 
     o = o[0:l-1]   # sublist that excludes last element
     while len(r) > 0: # iterate and construct subtrees
       first = r[0]
       lim = -1
       for i in 0..l - 1:
         if o[i] == first:
            lim = i + 1
            break
       assert lim != -1
       myroot.add_rightmost_child(mktree(r[0:lim], o[0:lim])
       r = r[lim:len(r)] # sublist from lim until end of list
       o = o[lim:len(o)] # sublist from lim until end of list
     return myroot

这是它如何工作的一个例子:

原始树:

            1
          / | \
         2  3  4
        /     / \
       5      6  7

前序遍历(“自上而下深度优先”):1 2 5 3 4 6 7

后序遍历(“自下而上”):5 2 3 6 7 4 1

算法执行:

mktree(1253467, 5236741)
    myroot = 1
    r = 253467, o = 523674
    loc = 1 (location of '2' in o)
         mktree(25, 52)
              myroot = 2
              mktree(5, 5) -> returns singleton tree 5
         list exhausted -> returns tree 2[5] (5 only child of 2)
    add 2[5] to myroot as right child, tree at myroot 1[2[5]]
    r = 3467, o = 3674 (stripped away "25" that was processed)
    loc = 0 (location of '3' in o)
         mktree(3, 3) returns singleton tree 3
    add 3 to myroot as right child, tree at myroot 1[2[5], 3]
    r = 467, o = 674 (stripped away "3" that was processed)
    loc = 2 (location of '4' in o)
         mktree(467, 674)
              myroot = 4
              r = 67, o = 67
              (recursive calls return first singleton 6, then 7)
              returns tree 4[6,7]
    add 4[6,7] to myroot as right child, tree at myroot 1[2[5],3,4[6,7]]
    list exhausted, return tree

结果，原来的树被重建了。

作为引用，这里定义了伪代码中的前序和后序遍历:

 def preorder(t):
     l = [root_node(t)]     # BEFORE recursion = PREorder
     for c in t.children(): # in left to right order
         l.append(preorder(c))
     return l

 def postorder(t):
     l = []
     for c in t.children(): # in left to right order
         l.append(postorder(c))
     l.append(root_node(t)) # AFTER recursion = POSTorder
     return l