实现JavaScript中二叉树的广度优先遍历算法

资源摘要信息:"二叉树的广度优先遍历（Breadth-First Search, BFS），也称为层序遍历（Level Order Traversal），是一种按照树的层次从上到下、从左到右进行遍历的算法。在JavaScript中实现二叉树的广度优先遍历通常需要使用队列这种数据结构来追踪待访问的节点。该算法的基本思想是从根节点开始，首先访问离根最近的节点，然后逐层向下，先访问距离较近的节点，再访问距离较远的节点。 在具体编码实现时，首先需要定义二叉树节点的数据结构，通常包含值、左子节点和右子节点三个属性。然后定义一个队列，将根节点入队。在队列不为空的情况下，循环执行以下步骤： 1. 节点出队，访问该节点。 2. 如果该节点有左子节点，则将左子节点入队。 3. 如果该节点有右子节点，则将右子节点入队。 重复以上步骤，直到队列为空，此时遍历结束，已经完成了对二叉树的广度优先遍历。 以下是一个简单的JavaScript代码示例，展示了如何实现二叉树的广度优先遍历： ```javascript function TreeNode(val) { this.val = val; this.left = this.right = null; } function levelOrder(root) { let result = []; let queue = []; if (root === null) { return result; } queue.push(root); while (queue.length > 0) { let levelSize = queue.length; let currentLevel = []; for (let i = 0; i < levelSize; i++) { let currentNode = queue.shift(); // 出队操作 currentLevel.push(currentNode.val); if (currentNode.left !== null) { queue.push(currentNode.left); // 左子节点入队 } if (currentNode.right !== null) { queue.push(currentNode.right); // 右子节点入队 } } result.push(currentLevel); } return result; } // 使用示例 let root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); console.log(levelOrder(root)); ``` 上述代码中，`TreeNode`构造函数用于创建二叉树节点，`levelOrder`函数用于执行广度优先遍历。遍历结果会以二维数组的形式返回，其中每个子数组代表树的一层。 广度优先遍历的时间复杂度为O(n)，其中n为树中节点的数量。空间复杂度也为O(n)，因为在最坏的情况下，需要存储所有的节点到队列中。 此外，广度优先遍历不仅可以用于二叉树，还可以用于其他图结构的遍历。例如，在处理图的最短路径问题时，BFS常常被用来找到从一个节点到其他所有节点的最短路径。"