DOM树遍历之JS完成DFS&BFS

我们平常能够采纳DFS（深度优先遍历）和BFS（广度优先遍历）来遍历DOM树

引见 DFS & BFS

我们来连系详细例子举行剖析，给出HTML代码片断以下：

DFS老是先进入下一级节点，只要当下一级没有未遍历的子节点时才会进入到当前层级的别的节点。关于上面例子DFS遍历效果应为：

root, container, sidebar, menu, main, post, copyright

BFS则老是先遍历当前层级的一切节点，只要当当前层级一切节点都遍历完毕后才会进入下一层级。关于上面例子BFS遍历效果应为：

root, container, sidebar, main, menu, post, copyright

DFS的详细完成

DFS重要采纳递归完成，顺次遍历节点，假如遍历到的节点有子节点，则最先遍历子节点

const DFSTraverse = (rootNodes, rootLayer) => {
const roots = Array.from(rootNodes)
while (roots.length) {
const root = roots.shift()
printInfo(root, rootLayer)
// 假如有子节点，直接遍历子节点，同时将层级加1
if (root.children.length) {
DFSTraverse(root.children, rootLayer + 1)
}
}
}


BFS的详细完成

BFS采纳行列的头脑，采纳出队的体式格局遍历节点，假如遍历到的节点有子节点，则将子节点入队（这里处置惩罚节点层级的体式格局比DFS更庞杂一些，由于这里将一切节点都放到了同一个数组中举行处置惩罚）

const BFSTraverse = (rootNodes, rootLayer) => {
const roots = Array.from(rootNodes)
const rootsLayer = [] // 单用一个数组寄存每一个节点的的层级
// 初始化
for (let i = 0; i rootsLayer.push(rootLayer)
}
var rootIdx = 0 // 纪录当前处置惩罚roots中的第几个节点，轻易查找rootsLayer中对应的层级
while (roots.length) {
const root = roots.shift() // 出队
printInfo(root, rootsLayer[rootIdx])
// 假如有子节点，将子节点放到roots行列中
if (root.children.length) {
Array.prototype.push.apply(roots, Array.from(root.children))
// 将当前层级加1获得子节点的层级
rootLayer = rootsLayer[rootIdx] + 1
for (let i = 0; i rootsLayer.push(rootLayer)
}
}
// 处置惩罚下一个root节点
rootIdx++
}
}


效果

先给人人补全代码：

// 输入节点信息
const printInfo = (node, layer) => {
var str = ''
for (let i = 1; i str += ' '
}
console.log(`${layer}:${str}${node.tagName} .${node.className}`);
}
console.log('DFS *******************************');
DFSTraverse(document.querySelectorAll('.root'), 1);
console.log('BFS *******************************');
BFSTraverse(document.querySelectorAll('.root'), 1);


上面例子的运转效果为：

参考

破解前端口试（80% 应聘者不及格系列）：从 DOM 提及
Javascript-ONLY DOM Tree Traversal &＃8211; DFS and BFS?