如何重新创建树，其顺序遍历存储在文件中 [英] How to re-create tree whose inorder traversal is stored in the file

问题描述

给出一种特殊类型的树，其中所有叶都用不同的符号标记，并且所有其他节点被标记为虚拟字符0.每个节点可以具有0个节点或至多2个节点。树的顺序遍历写入文件。

解决方案

问题解释的问题是无法解决的，因为对于给定的有序遍历可以存在多于一个树，即使树叶是众所周知的。 （在附加的示例中，两个树的顺序是1,2,3,4,5和1,3,5是两者中的叶子）。

你可能希望同时存储无序遍历和预先prder 遍历，并且从那里，有一个简单的递归算法来重建树：

 重构（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 =重构（left_pre，left_in）
 right_in = inOrder.filter（right，root）（*）
 right_pre = preOrder.filter（right，root）（*）
 root.right = reconstruction right_pn，right_in）
 return root 
  

到根（按顺序）并返回它，对于预订，它返回同一组节点按顺序返回，但它们出现在预订列表中。

attached：上面的例子：

EDIT：为递归算法添加了停止条件。

/ strong>

过滤器看起来像这样（伪代码）（假设每个元素都是唯一的）：

  inOrderFilter（list，root）：
i < -  0 
 left<  -  []（空列表）
 right < -  [] 
 while 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 ，left_in，right_in）：
 left < -  [] 
 right < -  [] 
对于列表中的每个e：
如果在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相同的元素，但他们应该保留在原来的预订顺序。 / p>

A special type of tree is given, Where all leaf are marked with distinct symbols and all others nodes are marked with dummy character 0. every node can have 0 or at most 2 nodes. Trees inorder traversal is written to file. Please give a algorithm to build tree from this traversal.

解决方案

the problem as explained in the question is unsolveable, because there can be more then one tree for a given in-order traversal, even if the leaves are well known. (in the example attached, the in order for both trees is 1,2,3,4,5 and 1,3,5 are leaves in both).

you might want to store both inorder traversal and pre-prder traversal, and from there, there is a simple recursive algorithm to reconstruct the tree:

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

(*) the filter finds all elements left/right to the root (in the in-order) and returns it, for pre-order it returns the same set of nodes in-order returned, but as they appear in the pre-order list.

attached: example described above:

EDIT: added stop condition for the recursive algorithm.

EDIT 2:
the filter will look something like that (pseudo code) (assuming each element is unique):

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)

basically, for the left_in you need everything left of the root, and for right_in you need everything right of the root (left and right according to the in order list).
for left_pre, and right_pre: you need a permutations of left_in,right_in, each of them should have the same elements that XXX_in has, but they should retain the order they had in the original pre-order.

这篇关于如何重新创建树，其顺序遍历存储在文件中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！