深度优先和广度优先遍历
# 前言
广度优先和深度优先之前只是觉得面试的时候会用到,后来有个需求,需要给用户提供一个页面的链接,用户访问这个链接时需要遍历他拥有的所有的页面权限,然后默认跳转到用户有权限的第一个页面。这个时候权限其实就是一个树结构的数据,我们需要遍历用户的权限树,这里就用到了深度优先遍历和广度优先遍历。
# 深度优先遍历
比如想遍历这个DOM树:
<div>
<p><h1>1</h1></p>
<p><h2>2</h2></p>
</div>
1
2
3
4
2
3
4
深度优先遍历的思想为:先遍历第一个p标签,然后是遍历第一个p标签的h1标签,接着是第二个p标签,然后是h2标签
// 递归版本
function depFirstSearch(node, result = []) {
result.push(node);
let children = node.children || [];
if (children.length) {
for (let i = 0; i < children.length; i++) {
depFirstSearch(children[i], result);
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
// 非递归版本 stack的使用是关键
function depSearch(node) {
const result = [];
if (node != null) {
const stack = [];
stack.push(node);
while (stack.length) {
let item = stack.pop();
result.push(item);
let children = item.children;
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i]);
}
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 广度优先遍历
比如想遍历和上面相同的DOM树:
<div>
<p><h1>1</h1></p>
<p><h2>2</h2></p>
</div>
1
2
3
4
2
3
4
广度优先遍历的思想为:先遍历第一个p标签,接着是第二个p标签;然后遍历第一个p标签的h1标签,最后是第二个p标签的h2标签
// 同样 使用了栈结构
function breadthFirstSearch(node) {
const queue = [];
const nodeList = [];
if (node !== null) {
queue.push(node);
while (queue.length > 0) {
const item = queue.shift();
nodeList.push(item);
Array.from(item.children).forEach((child) => {
queue.push(child);
});
}
}
return nodeList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
编辑 (opens new window)
上次更新: 2021/06/03, 18:52:11