二叉树的前序、中序和后序遍历：详解与实现

1. 前序遍历（Pre-order Traversal）

1.1 定义

前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

1.2 访问顺序

对于任意节点：

1. 访问根节点。

2. 递归遍历左子树。

3. 递归遍历右子树。

1.3 示例

假设我们有以下二叉树：

        A/ \B   C/ \   \D   E   F

前序遍历的结果是：A -> B -> D -> E -> C -> F。

1.4 递归实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}public class BinaryTree {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.add(root.val); // 访问根节点res.addAll(preorderTraversal(root.left)); // 递归遍历左子树res.addAll(preorderTraversal(root.right)); // 递归遍历右子树return res;}
}

1.5 应用场景

• 构建表达式树：前序遍历可以生成表达式的前缀表达式。

• 复制二叉树：通过前序遍历可以复制一个二叉树。

• 序列化二叉树：前序遍历可以用于将二叉树序列化为一个字符串。

2. 中序遍历（In-order Traversal）

2.1 定义

中序遍历的顺序是：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

2.2 访问顺序

对于任意节点：

1. 递归遍历左子树。

2. 访问根节点。

3. 递归遍历右子树。

2.3 示例

假设我们有以下二叉树：

        A/ \B   C/ \   \D   E   F

中序遍历的结果是：D -> B -> E -> A -> C -> F。

2.4 递归实现

public class BinaryTree {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.addAll(inorderTraversal(root.left)); // 递归遍历左子树res.add(root.val); // 访问根节点res.addAll(inorderTraversal(root.right)); // 递归遍历右子树return res;}
}

2.5 应用场景

• 二叉搜索树（BST）：中序遍历可以生成一个递增的有序序列。

• 表达式树：中序遍历可以生成表达式的中缀表达式。

3. 后序遍历（Post-order Traversal）

3.1 定义

后序遍历的顺序是：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

3.2 访问顺序

对于任意节点：

1. 递归遍历左子树。

2. 递归遍历右子树。

3. 访问根节点。

3.3 示例

假设我们有以下二叉树：

        A/ \B   C/ \   \D   E   F

后序遍历的结果是：D -> E -> B -> F -> C -> A。

3.4 递归实现

public class BinaryTree {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.addAll(postorderTraversal(root.left)); // 递归遍历左子树res.addAll(postorderTraversal(root.right)); // 递归遍历右子树res.add(root.val); // 访问根节点return res;}
}

3.5 应用场景

• 删除二叉树：后序遍历可以确保在删除根节点之前先删除其子节点。

• 表达式树：后序遍历可以生成表达式的后缀表达式。

4. 总结

遍历方式	访问顺序	应用场景
前序遍历	根 -> 左 -> 右	构建表达式树、复制二叉树、序列化二叉树
中序遍历	左 -> 根 -> 右	生成有序序列、表达式树的中缀表达式
后序遍历	左 -> 右 -> 根	删除二叉树、表达式树的后缀表达式

4.1 递归实现的通用模板

public class BinaryTree {public List<Integer> traversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}// 递归遍历左子树res.addAll(traversal(root.left));// 访问根节点（根据遍历方式调整位置）res.add(root.val);// 递归遍历右子树res.addAll(traversal(root.right));return res;}
}