-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDFS&BFS.html
108 lines (106 loc) · 3.12 KB
/
DFS&BFS.html
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
<html>
<body>
<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">
a
</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">
b
</div>
</div>
<div class="child-1-3">
c
</div>
</div>
<div class="child-2">
<div class="child-2-1">
<div class="child-2-1-1">
d
</div>
</div>
<div class="child-2-2">
<div class="child-2-2-1">
e
</div>
</div>
</div>
<div class="child-3">
<div class="child-3-1">
f
</div>
</div>
</div>
</body>
</html>
<script>
// 深度优先
// 1、递归
const deepTraversal1 = node => {
let nodeList = [];
if (node !== null) {
nodeList.push(node);
let children = node.children;
for (let i = 0; i < children.length; i++) {
nodeList.push.apply(nodeList, deepTraversal1(children[i]));
}
}
return nodeList;
}
// 2、循环
// 栈实现，循环中做的是push => pop => push => pop
// 也就是迭代的方式
const deepTraversal2 = (node) => {
let stack = [];
let nodes = [];
if (node) {
// 推入当前处理的node
stack.push(node);
// 栈， 先进后出
while (stack.length) {
let item = stack.pop();
let children = item.children;
let len = children.length;
nodes.push(item);
// 如果有 children，则将 children 入栈，
// 倒序 push，将最后的 children 放在栈底，每次 pop 最前的的 children，
for (let i = len - 1; i >= 0; i--) {
stack.push(children[i]);
}
}
}
return nodes;
}
const node = document.getElementsByClassName('parent')[0];
// 广度优先
// 队列实现， 循环中做的是push => shift => push => shift
// 也就是迭代的方式
const widthTraversal = node => {
let queue = [];
let nodes = [];
if (node) {
// 推入当前处理的node
queue.push(node);
// 队列， 先进先出
while (queue.length) {
// 先 push 的 先出
let item = queue.shift();
let children = item.children;
let len = children.length;
nodes.push(item);
// 如果有 children，则将 children 加入队列，
// 正序加入，则会是一层一层的遍历
for (let i = 0; i < len; i++) {
queue.push(children[i]);
}
}
}
return nodes;
}
console.log('deepTraversal1>>', deepTraversal1(node));
console.log('deepTraversal2>>', deepTraversal2(node));
console.log('widthTraversal>>>', widthTraversal(node));
</script>