如何用它的 BFS 和 DFS 遍历构造一棵树 [英] How to construct a tree with it's BFS and DFS traversal

问题描述

我有BFS 和DFS 遍历一棵树.如何从这些遍历中重建树?

I have the BFS and DFS traversal of a tree. How can I reconstruct the tree from these traversals?

例如:

BFS Traversal : 4 3 5 1 2 8 7 6

DFS Traversal : 4 3 1 7 2 6 5 8

那么树就会像下面这样:

then the tree would be like bellow:

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

推荐答案

这只有在 BFS 和 DFS 使用完全相同的顺序来遍历子级时才有可能:

This is only possible if BFS and DFS use exactly the same order to traverse children:

规则 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 的唯一孩子.

As this example shows, we can easily know that (3 , 1 , 7 , 2 , 6) belong to a subtree that has 3 as root. Since 1 is aswell part of that subtree, we can derive that 3 and 5 are the only children of 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 的孩子.

This way, we can show that 3 and 5 are the children of 4.

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

This can aswell be done using only subsets of BFS and DFS that hold nodes that belong to the same subtree (this example is the subtree found in the demonstration of Rule 1):

使用规则 1:

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

这表明 7 是 1 的独生子.

This shows that 7 is the only child of 1.

使用规则 2:

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

因此 1 和 2 是同一父级的子级(即 3).

Thus 1 and 2 are children of the same parent (which would be 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)

这篇关于如何用它的 BFS 和 DFS 遍历构造一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！