顺序存储二叉树实现先序遍历
时间: 2023-11-14 21:55:37 浏览: 90
要实现顺序存储二叉树的先序遍历,可以使用数组来表示二叉树的结构。假设数组的下标从0开始计数,根节点位于下标为0的位置。对于任意一个节点i,其左子节点的位置为2*i+1,右子节点的位置为2*i+2。
以下是一个示例代码,实现顺序存储二叉树的先序遍历:
```python
def preorder_traversal(tree, index=0):
if index >= len(tree) or tree[index] is None:
return
# 先访问当前节点
print(tree[index])
# 递归遍历左子树
preorder_traversal(tree, 2 * index + 1)
# 递归遍历右子树
preorder_traversal(tree, 2 * index + 2)
```
使用时,可以将二叉树以数组形式传入函数`preorder_traversal`。其中None表示空节点。
例如,对于二叉树[1, 2, 3, 4, None, 5, 6],可以按照先序遍历的顺序输出节点值:
```python
tree = [1, 2, 3, 4, None, 5, 6]
preorder_traversal(tree) # 输出结果为:1 2 4 3 5 6
```
注意,顺序存储二叉树适用于完全二叉树,如果是非完全二叉树,需要使用其他数据结构来表示。