用顺序存储结构来存储一颗具有n个结点的二叉树,编写算法实现对该二叉树进行先序遍历,输出先序遍历序列。
时间: 2023-06-13 13:07:49 浏览: 204
各种二叉树的数据结构.rar_二叉树_二叉树 遍历_实现二叉树的先、中、后序递归遍历算_数据结构_数据结构 算法
对于顺序存储结构来存储二叉树,一般采用一维数组来存储,假设二叉树的根节点存储在数组下标为0的位置,则对于下标为i的节点,它的左子节点存储在下标为2i+1的位置,右子节点存储在下标为2i+2的位置。
按照先序遍历的顺序,先输出根节点,再遍历左子树,最后遍历右子树。因此,可以通过递归实现先序遍历。
具体实现如下:
```python
def preorder_traversal(tree, i):
if i >= len(tree) or tree[i] is None:
return
print(tree[i], end=' ')
preorder_traversal(tree, 2*i+1)
preorder_traversal(tree, 2*i+2)
```
其中,tree为存储二叉树的数组,i为当前节点的下标。如果当前节点不存在或者超出数组范围,则直接返回。否则,先输出当前节点,再递归遍历左子树和右子树。在输出节点时,使用end=' '来控制输出格式,使得每个节点之间用空格隔开。
调用该函数,可以实现对二叉树的先序遍历输出:
```python
tree = [1, 2, 3, 4, 5, 6, 7]
preorder_traversal(tree, 0) # 输出:1 2 4 5 3 6 7
```
以上代码实现的是递归形式的先序遍历,也可以使用栈来实现迭代形式的先序遍历,这里不再赘述。
阅读全文