使用层次遍历创建二叉树
时间: 2023-01-12 08:13:05 浏览: 81
层次遍历是指从根节点开始,按照从上到下、从左到右的顺序依次访问每一个节点。
下面是一个示例代码,使用层次遍历创建二叉树:
```
from collections import deque
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def create_tree(arr):
if not arr:
return None
root = Node(arr[0])
queue = deque([root])
i = 1
while queue:
node = queue.popleft()
if i < len(arr):
if arr[i] is not None:
node.left = Node(arr[i])
queue.append(node.left)
if i+1 < len(arr):
if arr[i+1] is not None:
node.right = Node(arr[i+1])
queue.append(node.right)
i += 2
return root
# Example
arr = [1, 2, 3, 4, 5, 6, 7]
root = create_tree(arr)
```
在这个示例中,我们使用一个数组 `arr` 来表示二叉树的层次遍历结果。数组中的每一个元素对应二叉树中的一个节点,其中空节点用 `None` 表示。
首先,我们创建一个根节点 `root`,并将其添加到队列中。然后,我们不断取出队列的头节点,并按照从左到右的顺序依次为其创建子节点。最后,我们将创建的子节点加入队列中,继续遍历下一层。
上面的代码中,我们使用了一个双端队列 `queue` 来存储待遍历的节点。双端队列可