介绍深度优先遍历（DFS）与广度优先便利（BFS)，如何实现

[luichooy]

深度优先遍历（DFS）

找到一个节点后，把它的后辈都找出来，最常用递归法。

利用递归实现深度优先遍历

// 方法1
function dfs(tree, list = []) {
  if(tree){
    list.push(tree)
    const children = tree.children
    children && children.forEach(child => {
      dfs(child)
    })
  }
  return list
}

// 方法2
function dfs(tree) {
  let list = []
  if(tree){
    list.push(tree)
    const children = tree.children;
    children && children.forEach(child => {
      list = list.concat(dfs(child))
    })
  }
  return list
}

利用 generator +Interator 接口实现深度优先遍历

function *dfs(tree) {
  yield tree
  const children = tree.children
  children && children.forEach(child => {
    yield *dfs(child)
  })
}
console.log([...dfs(tree)])

利用 while 实现深度优先遍历

function dfs(tree) {
  const stack = []
  const list = []
  if(tree){
    stack.push(tree)

    while(stack.length) {
      const node = stack.pop()
      list.push(node)
      const children = node.children

      children && children.forEach(child => {
        stack.push(child)
      })
    }
  }
  return list
}

广度优先遍历（BFS）

找到一个节点后，把他同级的兄弟节点都找出来放在前边，把孩子放到后边，最常用 while

利用 while 实现广度优先遍历

function bfs(node) {
  const queue = []
  const list = []
  if(node){
    queue.push(node)
    while(queue.length) {
      const node = queue.shift()
      list.push(node)
      const children = node.children
      children && children.forEach(child => {
        queue.push(child)
      })
    }
  }
  return list
}