给定一个数组,将数组的值按层序构造一棵二叉树
时间: 2024-03-09 17:49:07 浏览: 62
使用数组实现二叉树
假设数组为arr,下标从1开始,空节点用null表示。按照层序构造一棵二叉树的具体步骤如下:
1. 创建一个空队列。
2. 创建一个根节点,根节点的值为arr[1]。
3. 将根节点入队。
4. 循环执行以下操作,直到队列为空:
a. 弹出队首节点,记为curNode。
b. 如果curNode的下标为i,则curNode的左子节点的下标为2i,右子节点的下标为2i+1。
c. 如果2i小于等于arr的长度,并且arr[2i]不为null,则创建一个左子节点,值为arr[2i],并将其入队。
d. 如果2i+1小于等于arr的长度,并且arr[2i+1]不为null,则创建一个右子节点,值为arr[2i+1],并将其入队。
这样就可以按层次顺序构造一棵二叉树了。下面是一个示例代码,实现将数组构造成二叉树的功能:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(arr):
if not arr:
return None
root = Node(arr[1])
queue = [root]
i = 1
while queue:
cur_node = queue.pop(0)
i += 1
if 2 * i <= len(arr) and arr[2 * i - 1]:
cur_node.left = Node(arr[2 * i - 1])
queue.append(cur_node.left)
i += 1
if 2 * i <= len(arr) and arr[2 * i - 1]:
cur_node.right = Node(arr[2 * i - 1])
queue.append(cur_node.right)
return root
```
这个函数可以根据输入的数组构造出一棵二叉树,并返回根节点。
阅读全文