树的深度优先搜索与广度优先搜索
广度优先搜索（BFS）和深度优先搜索（DFS）是计算机科学和数据分析中使用的两种基本算法，用于遍历和搜索图、树等数据结构。
这些算法可以应用于许多问题，例如找到两点之间的最短路径，检查图中的循环，或搜索数据结构中的特定元素。
1
/ \
2 3
/ \ / \
4 5 6 7
1
2
3
4
5
2
3
4
5
以上结构，javascript 代码表达如下：
let tree = [
{
id: '1',
name: '1',
children: [
{
id: '2',
name: '2',
children: [
{
id: '4',
name: '4',
children: []
},
{
id: '5',
name: '5',
children: []
}
]
},
{
id: '3',
name: '3',
children: [
{
id: '6',
name: '6',
children: []
},
{
id: '7',
name: '7',
children: []
}
]
}
]
},
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
深度优先遍历（Depth-First Search, DFS）
递归实现
function dfs(tree, func) {
tree.forEach((node) => {
func(node)
node.children && dfs(node.children, func)
})
}
1
2
3
4
5
6
2
3
4
5
6
循环实现
function dfs(tree, func) {
let node, curTree = [...tree]
while ((node = curTree.shift())) {
func(node)
node.children && curTree.unshift(...node.children)
}
}
1
2
3
4
5
6
7
2
3
4
5
6
7
输出结果：
dfs(tree, (node) => {
console.log(node.name);
})
// 1, 2, 4, 5, 3, 6, 7
1
2
3
4
2
3
4
广度优先遍历（Breadth-First Search, BFS）
function bfs(tree, func) {
let node, curTree = [...tree]
while ((node = curTree.shift())) {
func(node)
node.children && curTree.push(...node.children)
}
}
1
2
3
4
5
6
7
2
3
4
5
6
7
输出结果：
bfs(tree, (node) => {
console.log(node.name);
})
// 1, 2, 3, 4, 5, 6, 7
1
2
3
4
2
3
4