深度与广度优先遍历

一、树是什么？

在计算机领域，树是一种分层数据的抽象模型。在前端工作中常见的树包括：DOM树、级联选择、树形控件……。在JS中没有树，但是可以用 Object 和 Array 构建树。示例如下：

{
    value: 'zhejiang',
     label: 'ZheJiang',
  children: [
    {
      value: 'hangzhou',
      label: 'HangZhou',
      children: [
        {
            value: 'xihu',
          label: 'West Lake'
        }
    }
  ]
}

树的常用操作：深度/广度优先遍历、先中后序遍历，这几种遍历非常重要！！！

二、深度与广度优先遍历

深度优先遍历(dfs)
深度优先遍历是尽可能深的搜索树的分支。

如图所示，展示了一个树该如何进行深度优先遍历，其中数字代表访问节点的顺序。

广度优先遍历(bfs)
广度优先遍历是先访问离根节点最近的节点。

如图所示，a 是根节点，先访问离根节点最近的 b 和 c。

以看书为例，将 a 节点想象成一本书的书名，b、c节点想象成一本书的目录，d、e则是每章的页面，深度优先遍历则是我们一页一页翻看这本书。而广度优先遍历则是先看标题，再看目录，再看每章页面。

三、技术实现

深度优先遍历算法口诀

• 访问根节点；
• 对根节点的 children 挨个进行深度优先遍历；
• 对第一步和第二步不断进行重复(递归)；

示例

const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: []
        },
        {
          val: 'e',
          children: []
        },
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: []
        },
        {
          val: 'g',
          children: []
        },
      ]
    }
  ]
}
const dfs = (root) => {
  console.log(root.val)  // 第一步：访问根节点
  root.children.forEach(dfs) // 第二部：对节点进行依次遍历
}
dfs(tree)

总结下来深度优先遍历就是一个递归。

广度优先遍历算法口诀

• 新建一个队列，把根节点入队；
• 把队头出队并访问；
• 把队头的children挨个入队；
• 重复第二、三步，直到队列为空；

示例

const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: []
        },
        {
          val: 'e',
          children: []
        },
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: []
        },
        {
          val: 'g',
          children: []
        },
      ]
    }
  ]
}
const bfs = (root) => {
  const queue = [root]   // 第一步：新建队列，根节点入队
  while (queue.length > 0) {
    const current = queue.shift() // 第二步：队头出队
    console.log(current.val)
    current.children.forEach(child => queue.push(child)) // 第三步：队头的 children 入队
  }
}
bfs(tree)