这只有在使用 BFS 和 DFS 时才有可能exactly遍历子节点的顺序相同:
Rule 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 的唯一子节点。
Rule 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)