algorithm - 如何用它的 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 使用完全相同的顺序遍历 child 时才有可能:

规则 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 的 child 。

这也可以仅使用 BFS 和 DFS 的子集来完成，这些子集包含属于同一子树的节点(此示例是在规则 1 的演示中找到的子树):

使用规则 1:

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

这表明 7 是 1 的唯一 child 。

使用规则 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)