深度优先与广度优先方法对DOM树的遍历

发表于 |

image

深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

image

广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

DOM的结构和数据结构中的“树”型结构比较类似，所以很自然的就可以使用DFS和BFS进行遍历。

深度优先可以理解为“一条路走到黑”，只有在撞到了“南墙”才回头。具体到DOM树中来说就是，从根节点开始，继而访问它的直接子元素，并依此往复直到不存在子元素。下面通过JavaScript使用了递归的方法实现了DFS，在控制台依次打印出节点的元素名，类名和层次

1
2
3
4
5
6
7
8
9
10
11
const DFS = function(node) {
    if (!node) {
        return
    }
    let deep = arguments[1] || 1
    console.log(`${node.nodeName}.${node.classList}  ${deep}`)
    if (!node.children.length) {
        return
    }
    Array.from(node.children).forEach((item) => DFS(item, deep + 1))
}

广度优先可以理解为“一层一层的剥离”，对同一层次的元素全部遍历过后，再遍历下一层。广度优先适合使用队列这种数据结构来实现，将每层的节点依次放入队列，并根据队列“先入先出”的特性取出就可以了。在JavaScript中模拟队列的的方法可以使用数组方法的push和shift对应入队和出队操作。同样给出JavaScript实现的DOM树遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const BFS = (root) => {
    if (!root) { return }
    let queue = [{
        item: root,
        depth: 1
    }]
    while (queue.length) {
        let node = queue.shift()
        console.log(`${node.item.nodeName}.${node.item.classList}  ${node.depth}`)
        if (!node.item.children.length) {
            continue;
        }
        Array.from(node.item.children).forEach((item, index, arr) => {
            queue.push({
                item: item,
                depth: node.depth + 1
            })
        })
    }
}

在BFS实现时，打印出队元素的同时会将出队元素的直接子节点放入队列，因此在上面计算层次的时候，子节点的层次关系是由它的父级确定的。