如何重新創建索引遍歷存儲在文件中的樹

Question

給出了一種特殊類型的樹，其中所有的葉子都用不同的符號標記，而其他所有的節點都用虛擬字符0標記。每個節點可以有0或最多2個節點。遍歷的樹被寫入文件。請給出一個算法從這個遍歷構建樹。

Answer 1

問題中解釋的問題是難以解決的，因爲對於給定的有序遍歷，即使樹葉是衆所周知的，也可能有多棵樹。 （在附上的例子中，爲了兩棵樹都是1,2,3,4,5和1,3,5都是葉子）。

你可能要同時存儲序遍歷和預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 

（*）濾鏡找到所有元素保持在根的左邊/右邊（按順序）並返回它，對於預定單，它將按順序返回相同的一組節點，但它們出現在預定單列表中。

附：

編輯：：例如如上所述添加停止條件的遞歸算法。

編輯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相同的元素，但它們應保留它們在原始預訂中的順序。