数据结构树的遍历代码
时间: 2024-10-11 11:04:07 浏览: 2
数据结构中的树是一种非线性的数据结构,它由节点组成,每个节点可以有零个、一个或多个子节点。树的遍历主要有三种基本方法:
1. **前序遍历 (Preorder Traversal)**: 先访问根节点,然后递归地遍历左子树,最后遍历右子树。通常的顺序是 `根 -> 左 -> 右`。
```python
def preorder_traversal(root):
if root is not None:
print(root.val) # 访问当前节点
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.val)
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.val)
```
每种遍历都有其特定的应用场景,比如前序遍历常用于复制一棵树,中序遍历可用于构建表达式树等。