写出二叉树的先序、中序、后序遍历算法
时间: 2025-02-16 17:13:45 浏览: 17
二叉树的遍历主要有三种:先序遍历(Preorder Traversal)、中序遍历(Inorder Traversal)和后序遍历(Postorder Traversal)。以下是每种遍历的具体步骤:
1. **先序遍历(根-左-右)**:
- 从根节点开始;
- 先访问根节点(打印或记录);
- 然后递归地对左子树进行先序遍历;
- 最后递归地对右子树进行先序遍历。
2. **中序遍历(左-根-右)**:
- 从根节点开始;
- 递归地对左子树进行中序遍历;
- 访问根节点(打印或记录);
- 后续对右子树进行中序遍历。
3. **后序遍历(左-右-根)**:
- 从根节点开始;
- 递归地对左子树进行后序遍历;
- 递归地对右子树进行后序遍历;
- 最后访问根节点(打印或记录)。
以下是这三种遍历的伪代码形式:
```plaintext
// 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 先序遍历
def preorder_traversal(root):
if root is not None:
print(root.val) # 打印或记录值
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历
def inorder_traversal(root):
if root is not None:
inorder_traversal(root.left)
print(root.val) // 打印或记录值
inorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if root is not None:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val) // 打印或记录值
```
阅读全文
相关推荐


















