对顺序存储方式存放的二叉树,给出前序、中序和后序遍历的递归算法实现。
时间: 2024-10-01 09:07:08 浏览: 37
对于顺序存储方式存放的二叉树,其结构通常是以数组的形式表示,每个节点包含左右子节点的索引。这里提供三种常见的二叉树遍历的递归算法:
1. **前序遍历(Preorder Traversal)**:
- 基本步骤:先访问根节点,然后对左子树进行前序遍历,最后遍历右子树。
```python
def preorder_traversal(root):
if root is not None:
print(root.value) # 先访问根
preorder_traversal(root.left) # 再遍历左子树
preorder_traversal(root.right) # 最后遍历右子树
```
2. **中序遍历(Inorder Traversal)**:
- 基本步骤:先遍历左子树,然后访问根节点,最后遍历右子树。
```python
def inorder_traversal(root):
if root is not None:
inorder_traversal(root.left) # 遍历左子树
print(root.value) # 访问根
inorder_traversal(root.right) # 遍历右子树
```
3. **后序遍历(Postorder Traversal)**:
- 基本步骤:先遍历左子树,然后遍历右子树,最后访问根节点。
```python
def postorder_traversal(root):
if root is not None:
postorder_traversal(root.left) # 左子树
postorder_traversal(root.right) # 右子树
print(root.value)