vlambda博客
学习文章列表

深度优先遍历 递归版本

const dfs1 = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node)
    const children = node.children || []
    for (let i = 0; i < children.length; i++) {
      dfs1(children[i], nodeList) // 展开子节点
    }
  }
  return nodeList
}

深度优先遍历 非递归实现

const dfs2 = (node) => {
  let nodes = []
  let stack = [] // 栈：先进后出
  if (node) {
    stack.push(node) // 第一个元素进来
    while (stack.length) {
      let item = stack.pop() // 弹出最后一个元素
      let children = item.children // 获取子元素
      nodes.push(item) // 将元素放进结果集
      for (let i = children.length - 1; i >= 0; i--) {
        // for循环是从反向遍历，最后一个元素先进入栈内，第一个元素在栈的最外层
        // while循环再次循环时，pop会取到第一个元素，因为第一个元素是最后入栈的
        // 然后再开展子元素，子元素被遍历时会添加到栈内。
        // 第一个元素被取出来之后进入的元素是第一个元素的子元素，while再次循环时取到的就是第一个子元素的children
        // 使用栈的特性完成深度优先遍历
        stack.push(children[i])
      }
    }
  }
  return nodes
}

广度优先遍历

const bfs = (node) => {
  let nodes = []
  let queue = [] // 广度优先遍历使用队列的特性
  if (node) {
    queue.push(node)
    while(queue.length) {
      let item = queue.shift() // 取数组第一项
      let children = item.children || []
      nodes.push(item) // 元素放入结果集
      for (let i = 0; i < children.length; i++) {
        /**
         * for 循环正向循环，将元素放入队列中，第一个元素就是当前元素的第一个children
         * while循环时会从队首取值然后将队首的子元素加到队列到末尾
         * 靠近队首的是最先被添加进去的，每次消费都是将前面的一级子元素添加到队列里
         * 以此实现广度优先遍历
         */
        queue.push(children[i])
      }
    }
  }
  return nodes
}