通过队列来实现层次遍历构建二叉树
时间: 2023-06-11 11:10:21 浏览: 47
层次遍历是一种广度优先搜索算法,可以通过队列来实现。下面是构建二叉树的层次遍历实现过程:
1. 首先创建一个空队列和一个空树。
2. 将根节点插入队列中。
3. 当队列不为空时,执行以下步骤:
a. 从队列中取出一个节点。
b. 读取该节点的左子节点和右子节点。
c. 如果左子节点不为空,则将左子节点插入队列中。
d. 如果右子节点不为空,则将右子节点插入队列中。
e. 将该节点插入树中。
4. 当队列为空时,说明二叉树已经构建完成。
下面是一个示例代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(level_order):
if not level_order:
return None
root = Node(level_order[0])
queue = [root]
i = 1
while queue:
node = queue.pop(0)
if i < len(level_order) and level_order[i] is not None:
node.left = Node(level_order[i])
queue.append(node.left)
i += 1
if i < len(level_order) and level_order[i] is not None:
node.right = Node(level_order[i])
queue.append(node.right)
i += 1
return root
```
其中,`level_order` 是按层次遍历顺序排列的节点值列表,可以包括 `None` 表示空节点。返回的是构建好的根节点。