二叉树的遍历方法

在二叉树中，遍历是指按照某种顺序访问树中的每一个节点。常见的二叉树遍历方法有三种：前序遍历、中序遍历和后序遍历。每种遍历方法都有其特定的访问顺序，理解这些方法有助于掌握树的基本操作。

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

前序遍历的访问顺序是：根节点 → 左子树 → 右子树。

1.1 递归实现

前序遍历的递归过程可以描述为：

访问根节点。
递归遍历左子树。
递归遍历右子树。

1.2 代码案例（递归）

// 二叉树节点类
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
    }
}

// 前序遍历递归实现
public class BinaryTreeTraversal {
    
    // 前序遍历：根 -> 左 -> 右
    public void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        // 访问根节点
        System.out.print(root.val + " ");
        // 递归遍历左子树
        preOrderTraversal(root.left);
        // 递归遍历右子树
        preOrderTraversal(root.right);
    }

    public static void main(String[] args) {
        // 构建一个示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        BinaryTreeTraversal tree = new BinaryTreeTraversal();
        System.out.print("前序遍历结果: ");
        tree.preOrderTraversal(root); // 输出: 1 2 4 5 3
    }
}

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

中序遍历的访问顺序是：左子树 → 根节点 → 右子树。

2.1 递归实现

中序遍历的递归过程可以描述为：

递归遍历左子树。
访问根节点。
递归遍历右子树。

2.2 代码案例（递归）

// 中序遍历：左 -> 根 -> 右
public void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    // 递归遍历左子树
    inOrderTraversal(root.left);
    // 访问根节点
    System.out.print(root.val + " ");
    // 递归遍历右子树
    inOrderTraversal(root.right);
}

public static void main(String[] args) {
    // 使用上面定义的二叉树
    BinaryTreeTraversal tree = new BinaryTreeTraversal();
    System.out.print("中序遍历结果: ");
    tree.inOrderTraversal(root); // 输出: 4 2 5 1 3
}

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

后序遍历的访问顺序是：左子树 → 右子树 → 根节点。

3.1 递归实现

后序遍历的递归过程可以描述为：

递归遍历左子树。
递归遍历右子树。
访问根节点。

3.2 代码案例（递归）

// 后序遍历：左 -> 右 -> 根
public void postOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    // 递归遍历左子树
    postOrderTraversal(root.left);
    // 递归遍历右子树
    postOrderTraversal(root.right);
    // 访问根节点
    System.out.print(root.val + " ");
}

public static void main(String[] args) {
    // 使用上面定义的二叉树
    BinaryTreeTraversal tree = new BinaryTreeTraversal();
    System.out.print("后序遍历结果: ");
    tree.postOrderTraversal(root); // 输出: 4 5 2 3 1
}