第 63 期(数据结构-队列)：队列的应用 #66
Description
上一期介绍了 队列和队列的模拟，这一期来看看队列的应用。
这是一道经典的面试题，要求不使用递归广度遍历下面的二叉树：
要求在控制台依次输出遍历结果：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); // 右子节点入队列
}
}
}