如何使用广度优先搜索（BFS）和深度优先搜索（DFS）遍历构建一棵树

Question

如何使用广度优先搜索（BFS）和深度优先搜索（DFS）遍历构建一棵树

algorithmgraphdepth-first-searchbreadth-first-searchtree-traversal

3

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

例如:

BFS Traversal : 4 3 5 1 2 8 7 6

DFS Traversal : 4 3 1 7 2 6 5 8

那么树的结构将会如下所示：

- madMDT

您的树是错误的。它有节点3的子节点被颠倒了。 - beaker

1

“4 3 5”是什么情况？它既可以是一个以4为根节点，5和3为子节点的“完整”树；也可以是一个分支4-5-3。看起来需要一些额外的信息才能得出确定的答案。 - yurib

可能是重复的问题：如何从先序遍历和中序遍历构建二叉树。链接：https://dev59.com/W1TTa4cB1Zd3GeqPxPR7 - dfeuer

请参阅如何使用中序遍历加前序遍历构建唯一的二叉树。 - dfeuer

其实我不知道先序遍历和中序遍历。谢谢你提供那些链接。 - madMDT

我认为你不能总是用BFS和DFS正确地完成这个任务。考虑两个二叉树，包含标记为1、2、3的节点。第一个树将2和3作为1的子节点，而第二个树将2作为1的子节点，将3作为2的子节点。对于两个树，它们的BFS顺序可能是1、2、3。它们的DFS顺序也可能是1、2、3。仅通过考虑BFS和DFS遍历，无法区分它们。 - Patrick87

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4668606 · Accepted Answer

只有当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)