<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">
<div>342</div>
</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">d</div>
<div class="child-2-2">e</div>
</div>
<div class="child-3">
<div class="child-3-1">f</div>
</div>
</div>
这里用一棵dom树来做说明
深度优先遍历
假设初始状态的时候图中的所有顶点均未被访问，则从某个个顶点v出发，首先访问该顶点，然后从它的各个未被访问的邻接点出发进行向下遍历
- 递归操作
const deepTraversal1 = (node, nodeList = []) => {
if (node !== null) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
deepTraversal1(children[i], nodeList)
}
}
return nodeList
}
- 非递归
// 深度遍历 方法一： 非递归方式实现
const deepTraversal2 = (node) => {
let stack = []
let nodes = []
if (node) {
// 推入当前处理的node
stack.push(node)
while (stack.length) {
let item = stack.pop()
let children = item.children
nodes.push(item)
// node = [] stack = [parent]
// node = [parent] stack = [child3,child2,child1]
// node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
// node = [parent, child1-1] stack = [child3,child2,child1-2]
for (let i = children.length - 1; i >= 0; i--) { // mei
stack.push(children[i])
}
}
}
return nodes
}
解释下最后一个：（可能会后面的广度优先冲突）
这个是深度优先的，你看看它最后的循环，是从末尾开始，也就是说，再下一次循环进来的时候，每次出栈都是从后面最后一个开始[其实已经到了子节点的范畴了】，[(当前节点的子节点是被放在栈的后面）
广度优先遍历
从图中的某个顶点v出发，在访问v之后依次访问v的各个未曾相邻的邻接节点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
const widthTraversal = (node) => {
let nodes = []
let queue = []
console.log('start')
if (node) {
queue.push(node)
while (queue.length) {
let item = queue.shift()
let children = item.children
console.log(item)
nodes.push(item)
// 队列，先进先出
// nodes = [] stack = [parent]
// nodes = [parent] stack = [child1,child2,child3]
// nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
// nodes = [parent,child1,child2]
for (let i = 0; i < children.length; i++) {
queue.push(children[i])
}
}
}
return nodes
}
const parent = document.querySelector('.parent')
// const result = deepTraversal1(parent) // 深度遍历 递归
// const result = deepTraversal2(parent) // 深度遍历 非递归
console.log('123')
const result = widthTraversal(parent) // 广度遍历
console.log(result)
参考：https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/9
