树的遍历

[AymaxLi]

树的遍历

Demo

  <div id="a">
    <p id="haha"></p>
  </div>
  <div id="b">
    <div id="d">
      <span id="e"></span>
      <span id="f"></span>
    </div>
  </div>
  <div id="c"></div>

DFS

递归法

最弟弟的方法，当树的高度很大的时候函数调用栈会十分的深

// DFS 递归法实现
dfs(document.body, el => console.log(`${el.tagName}#${el.id}`))

function dfs (t, cb) {

  // 对当前节点进行处理
  cb(t)

  // 若该节点是叶子节点，直接返回
  if (!t.children.length) return

  // 若该节点是父节点，查询其叶子节点
  Array.prototype.forEach.call(t.children, el => dfs(el, cb))
}

迭代法（栈）

借助栈，复杂度为 O(n)，树高度很大时会优于递归法

// DFS 迭代法，栈实现
dsf_stack(document.body, el => console.log(`${el.tagName}#${el.id}`))

function dsf_stack (t, cb) {
  let stack = []
  
  stack.push(t)

  while (stack.length > 0) {
    let node = stack.pop() // 出栈

    cb(node)

    // 若该节点为父节点，则将其子节点压入栈中  
    if (node.children.length) Array.prototype.forEach.call(node.children, el => stack.push(el))        
  }
}

WFS

用迭代法实现，借助队列，复杂度也为 O(n)

// WFS 迭代法，队列实现
wsf_queue(document.body, el => console.log(`${el.tagName}#${el.id}`))

function wsf_queue (t, cb) {
  let queue = []
  
  queue.unshift(t)

  while (queue.length > 0) {
    let node = queue.pop() // 出队

    cb(node)

    // 若该节点为父节点，则将其子节点入队 
    if (node.children.length) Array.prototype.forEach.call(node.children, el => queue.unshift(el))        
  }
}