c++ - 如何重新创建其中序遍历存储在文件中的树

Question

给出了一种特殊类型的树，其中所有叶子都用不同的符号标记，所有其他节点都用虚拟字符 0 标记。每个节点可以有 0 个或最多 2 个节点。 Trees inorder 遍历被写入文件。请给出一个算法来从这个遍历中构建树。

Answer 1

问题中解释的问题是无法解决的，因为对于给定的中序遍历可以有不止一棵树，即使叶子是众所周知的。 (在所附的示例中，两棵树的顺序是 1,2,3,4,5，而 1,3,5 都是叶子)。

你可能想同时存储inorder遍历和pre-prder遍历，从那里，有一个简单的递归算法来重建树:

reconstruct(List preOrder,List inOrder):
   if preOder.empty() == true:
          return nil
   root.value<-preOrder[0]
   left_in = inOrder.filter(left,root) (*) 
   left_pre = preOrder.filter(left,root) (*) 
   root.left = reconstruct(left_pre,left_in)
   right_in = inOrder.filter(right,root) (*) 
   right_pre = preOrder.filter(right,root) (*) 
   root.right= reconstruct(right_pre,right_in)
   return root

(*) 过滤器找到根左/右的所有元素(按顺序)并返回它，对于预排序它返回相同的一组节点按顺序返回，但因为它们出现在预购 list 。

附:上面描述的例子:

编辑:为递归算法添加停止条件。

编辑 2:
过滤器看起来像这样(伪代码)(假设每个元素都是唯一的):

inOrderFilter(list,root):
  i <- 0
  left <- [] (empty list)
  right <- []
  while (list[i] != root):
    left.add(list[i])
    i <- i+1
  while (i < list.size):
    right.add(list[i[)
    i <- i+1
  return pair(left,right)

preOrderFilter(list,left_in,right_in):
  left <- []
  right <- []
  for each e in list:
    if e in left_in:
       left.add(e)
    else if e in right_in:
       right.add(e)
  return pair (left,right)

基本上，对于 left_in，您需要根左侧的所有内容，而对于 right_in，您需要根右侧的所有内容(根据顺序列表的左侧和右侧)。
对于 left_pre 和 right_pre:您需要 left_in、right_in 的排列，它们中的每一个都应该具有与 XXX_in 相同的元素，但它们应该保留它们在原始预序中的顺序。