DOM树遍历--BFS和DFS

数据结构中，树或图有两种遍历方法，BFS--广度优先搜索、DFS--深度优先搜索。

DOM树也是一种树的实现。

如果我们有如下一颗DOM树，如果我们想要遍历它的每一个节点，应该怎么做呢。

<div id="app">
   <div id="header">
     <div id="logo"></div>
     <div id="menu"></div>
   </div>
   <div id="content">
     <div id="article">
       <div id="para1"></div>
       <div id="para2"></div>
       <div id="para3"></div>
     </div>
   </div>
 </div>

DFS

function DFS(node, cb) {
  let deep = 1;  
  DFSdom(node,deep,cb)
}

function DFSdom(node, deep, cb) {
  if(!node)
    return;

  cb(node,deep)

  if(!node.childNodes.length) {
    return;
  }

  deep++;

  Array.from(node.childNodes).forEach(item => DFSdom(item,deep,cb))
}

使用：

DFS(document.getElementById("app"),function (node,deep) {
  if(node.nodeType == 3) // 排除文本节点
    return
  console.log(node,deep);
})

打印结果：

Object {node: div#app, deep: 1}
Object {node: div#header, deep: 2}
Object {node: div#logo, deep: 3}
Object {node: div#menu, deep: 3}
Object {node: div#content, deep: 2}
Object {node: div#article, deep: 3}
Object {node: div#para1, deep: 4}
Object {node: div#para2, deep: 4}
Object {node: div#para3, deep: 4}

DFS的实现是利用递归，递归实现是利用堆栈。所以使用DFS有爆栈的风险。

BFS

function BFS(node,cb) {
  if(!node)
    return;

  var queue = [{
    node: node,
    depth: 1
  }]

  while(queue.length) {
    var current = queue.shift();

    cb(current)

    current.node.childNodes.length && Array.from(current.node.childNodes).forEach(item => {
      queue.push({
        node: item,
        depth: current.depth + 1
      })
    })
  }
}

使用：

BFS(document.getElementById("app"),function (node) {
  if(node.node.nodeType == 3) // 排除文本节点
    return
  console.log(node);
})

打印结果：

Object {node: div#app, depth: 1}
Object {node: div#header, depth: 2}
Object {node: div#content, depth: 2}
Object {node: div#logo, depth: 3}
Object {node: div#menu, depth: 3}
Object {node: div#article, depth: 3}
Object {node: div#para1, depth: 4}
Object {node: div#para2, depth: 4}
Object {node: div#para3, depth: 4}

BFS的实现是利用队列。