René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"第 63 期(数据结构-队列)：队列的应用","articleBody":"上一期介绍了 [队列和队列的模拟](https://github.com/fezaoduke/fe-practice-hard/issues/65)，这一期来看看队列的应用。\r\n\r\n这是一道经典的面试题，要求不使用递归广度遍历下面的二叉树：\r\n\r\n\u003e 要求在控制台依次输出遍历结果：1, 2, 3, 4, 5, 6, 7, 8\r\n\r\n**测试数据：**\r\n```json\r\n{\r\n  \"value\": 1,\r\n  \"left\": {\r\n    \"value\": 2,\r\n    \"left\": {\r\n      \"value\": 4\r\n    }\r\n  },\r\n  \"right\": {\r\n    \"value\": 3,\r\n    \"left\": {\r\n      \"value\": 5,\r\n      \"left\": {\r\n        \"value\": 7\r\n      },\r\n      \"right\": {\r\n        \"value\": 8\r\n      }\r\n    },\r\n    \"right\": {\r\n      \"value\": 6\r\n    }\r\n  }\r\n}\r\n```\r\n\r\n**思路：**\r\n\r\n广度遍历的特点是从根节点开始，沿着树的宽度一层一层进行遍历，直到所有节点都被遍历完为止，我们可以利用队列来实现这个算法。\r\n\r\n核心思路是用一个队列来临时保存节点。遍历开始时先将根节点加入队列，然后从队列中取出第一个元素（此时是根节点），同时将该节点的子节点（如有）加入队列，以此循环操作，直至队列为空。参照下图示意（点击可查看大图）：\r\n\r\n![image](https://user-images.githubusercontent.com/9009389/61541463-47da6700-aa72-11e9-834d-7b0b3a2d2a0a.png)\r\n\r\n**上码：**\r\n\r\n```js\r\nfunction levelOrderTraversal(tree) {\r\n  var queue = [];  // 使用数组模拟队列\r\n\r\n  queue.push(tree);  // 根节点入队列\r\n  while (queue.length !== 0) {\r\n    tree = queue.shift();  // 取出队列第一个节点\r\n\r\n    console.log(tree.value);\r\n\r\n    if (tree.left) {\r\n      queue.push(tree.left);  // 左子节点入队列\r\n    }\r\n    if (tree.right) {\r\n      queue.push(tree.right);  // 右子节点入队列\r\n    }\r\n  }\r\n}\r\n```\r\n","author":{"url":"https://github.com/wingmeng","@type":"Person","name":"wingmeng"},"datePublished":"2019-07-19T14:26:24.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/66/fe-practice-hard/issues/66"}