如何用它的 BFS 和 DFS 遍历构造一棵树
How to construct a tree with it's BFS and DFS traversal
我有树的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
这只有在 BFS 和 DFS 使用 完全 相同的顺序遍历时才有可能 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 中唯一的 children。
规则 2：
BFS Traversal : 4 3 5 1 2 8 7 6
| | |
| | |-|
| | |
DFS Traversal : 4 3 1 7 2 6 5 8
这样，我们可以证明3和5是4的children
这也可以仅使用包含属于同一子树的节点的 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 是同一个 parent 的 children（即 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遍历。我怎样才能从这些遍历中重建树？
例如：
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
这只有在 BFS 和 DFS 使用 完全 相同的顺序遍历时才有可能 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 中唯一的 children。
规则 2：
BFS Traversal : 4 3 5 1 2 8 7 6
| | |
| | |-|
| | |
DFS Traversal : 4 3 1 7 2 6 5 8
这样，我们可以证明3和5是4的children
这也可以仅使用包含属于同一子树的节点的 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 是同一个 parent 的 children（即 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)