第 63 期(数据结构-队列)：队列的应用

[wingmeng]

上一期介绍了 队列和队列的模拟，这一期来看看队列的应用。

这是一道经典的面试题，要求不使用递归广度遍历下面的二叉树：

要求在控制台依次输出遍历结果：1, 2, 3, 4, 5, 6, 7, 8

测试数据：

{
  "value": 1,
  "left": {
    "value": 2,
    "left": {
      "value": 4
    }
  },
  "right": {
    "value": 3,
    "left": {
      "value": 5,
      "left": {
        "value": 7
      },
      "right": {
        "value": 8
      }
    },
    "right": {
      "value": 6
    }
  }
}

思路：

广度遍历的特点是从根节点开始，沿着树的宽度一层一层进行遍历，直到所有节点都被遍历完为止，我们可以利用队列来实现这个算法。

核心思路是用一个队列来临时保存节点。遍历开始时先将根节点加入队列，然后从队列中取出第一个元素（此时是根节点），同时将该节点的子节点（如有）加入队列，以此循环操作，直至队列为空。参照下图示意（点击可查看大图）：

上码：

function levelOrderTraversal(tree) {
  var queue = [];  // 使用数组模拟队列

  queue.push(tree);  // 根节点入队列
  while (queue.length !== 0) {
    tree = queue.shift();  // 取出队列第一个节点

    console.log(tree.value);

    if (tree.left) {
      queue.push(tree.left);  // 左子节点入队列
    }
    if (tree.right) {
      queue.push(tree.right);  // 右子节点入队列
    }
  }
}