树的广度优先遍历

树的广度优先遍历指的是，从根节点开始，遍历下一层中所有的子节点，然后再继续遍历下一层子节点，以此类推。

子节点可以从左到右遍历，也可以从右到左遍历。

因为遍历节点的顺序相对固定，所以广度优先遍历不区分前序、中序和后序。

同样的遍历方式也可以用于图中。

应用

广度优先遍历可以应用于搜索引擎爬虫、社交网站寻找人脉关系、导航寻找最短路径上。

思路

广度优先遍历的大体思路是（以二叉树为例），利用一个队列，把根节点放入队列中，然后开始从队列里取出节点，进行遍历，再把当前遍历节点的所有子节点追加到队尾。按照队列先进先出的原则，当这一层所有节点都遍历完成之后，才能轮到下一层节点，这样队列为空之后，所有节点就遍历完了。

代码

这里是代码，queue 就是维护的队列，result 是遍历结果，我们会把遍历到的节点值放到这个结果数组中。后面在循环中会判断 queue 是否为空，然后遍历其中的节点，并把节点的子节点追加到队尾：

breadthFirstTraversal() {
  let result = [];
  let queue = [];
  queue.push(this.root);
  while (queue.length) {
    let current = queue.shift();
    result.push(current.value);
    if (current.left) {
      queue.push(current.left);
    }
    if (current.right) {
      queue.push(current.right);
    }
  }
  return result;
}