Как построить дерево с обходом BFS и DFS

Question

У меня есть BFS и DFS обход дерева. Как я могу восстановить дерево из этих обходов?

Например:

BFS Traversal : 4 3 5 1 2 8 7 6 

DFS Traversal : 4 3 1 7 2 6 5 8 

тогда дерево будет как ниже:

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

Answer 1

Это возможно только тогда, когда BFS и DFS использовать точно тот же порядок, чтобы пересечь детей:

Правило 1:

BFS Traversal : 4 3 5 1 2 8 7 6 
       | | | 
       | | |-------| 
       | |   | 
DFS Traversal : 4|3 1 7 2 6|5 8 

Как показывает этот пример, мы можем легко узнать, что (3 , 1 , 7 , 2 , 6) принадлежат поддерево, которое имеет 3 как корень. С 1 является как хорошо частью этого поддерева, мы можем получить, что 3 и 5 являются единственными детьми 4.

Правила 2:

BFS Traversal : 4 3 5 1 2 8 7 6 
       | | | 
       | | |-| 
       | | |   
DFS Traversal : 4 3 1 7 2 6 5 8 

Таким образом, мы можем показать, что 3 и 5 являются дети из 4.

Это как хорошо может быть сделано с использованием только подмножества BFS и DFS, которые держат узлы, которые принадлежат одному и тому же поддерева (этот пример поддерево найдено в демонстрации Правило 1):

используя Правило 1 :

BFS Traversal: 1 2 7 6 
       | | 
       | |-| 
       | | 
DFS Traversal: 1|7|2 6 

Это показывает, что 7 является единственным ребенком 1.

Использование Правило 2:

BFS Traversal: 1 2 7 6 
       | | 
       | |-| 
       | | 
DFS Traversal: 1 7 2 6 

Таким образом, 1 и 2 являются дети одного родителя (который был бы 3).

В переводе на псевдокод это будет выглядеть следующим образом:

addchild(int parent, int child) := add the child to the specified parent node 

void process(int[] bfs , int[] dfs) 
    int root = bfs[0] 

    //find all peers (nodes with the same level and parent in the tree) using Rule 2 
    int at = bfs.find(dfs[2]) 
    int peers[at - 1] 
    for int i in [1 , at[ 
     peers[i - 1] = bfs[i] 
     addchild(root , bfs[i]) 

    //for each of the childtree of the tree find it's children using Rule 1 
    for int i in [0 , length(peers)[ 
     //all nodes that are either peers[i] or a child of peers[i] 
     int[] children_dfs = dfs.subset(dfs.find(peers[i]) , (i < length(peers) - 1 ? dfs.find(peers[i + 1]) : length(dfs)) - 1) 
     //a subset of bfs containing peers[i] and it's children in the order they have in bfs 
     int[] children_bfs = bfs.allMatchingInOrder(children_dfs) 

     //generate the subtree 
     process(children_bfs , children_dfs) 

Answer 2

Look here. (при условии обхода DFS в порядке)

Это рекурсивный алгоритм.