根据二叉树的特性,创建二叉树的存储结构,并对二叉树进行层次遍历
时间: 2023-11-14 08:09:38 浏览: 70
二叉树是一种树形结构,每个节点最多有两个子节点。一个节点的左子树包含的所有节点的值都小于该节点的值,右子树包含的所有节点的值都大于该节点的值。
二叉树的存储结构可以使用指针来实现,每个节点包含三个指针,分别指向该节点的左子节点、右子节点和父节点(可选)。如果某个节点没有左子节点或右子节点,则对应指针指向空。
下面是一个简单的二叉树层次遍历的示例代码,其中使用队列来存储待访问的节点:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def level_order_traversal(root):
if not root:
return []
result = []
queue = [root]
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.pop(0)
current_level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
# 示例
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(level_order_traversal(root)) # [[1], [2, 3], [4, 5, 6, 7]]
```
以上代码实现了基本的二叉树层次遍历,时间复杂度为 O(n),其中 n 表示二叉树的节点数。
阅读全文