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

Question

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

Answer 1

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

您可能想要存储中序遍历和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 相同的元素，但它们应保留原始前序中的顺序。