Java 中序遍历全解析

简介

在计算机科学领域，树是一种非常重要的数据结构，而遍历树的节点是许多算法和应用的基础操作。中序遍历（Inorder Traversal）是二叉树遍历的一种重要方式，它在 Java 编程中有着广泛的应用。本文将深入探讨 Java 中中序遍历的基础概念、使用方法、常见实践以及最佳实践，帮助读者全面理解并高效运用中序遍历。

1. 基础概念

什么是中序遍历

中序遍历是一种用于遍历二叉树的算法。对于一棵二叉树，中序遍历按照“左子树 - 根节点 - 右子树”的顺序访问节点。也就是说，首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

示例二叉树

假设有如下二叉树：

中序遍历的结果是：1 -> 2 -> 3 -> 4 -> 5

2. 使用方法

递归实现

递归是实现中序遍历最直观的方法。以下是 Java 代码示例：

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

public class InorderTraversal {
    public static void inorderRecursive(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归遍历左子树
        inorderRecursive(root.left);
        // 访问根节点
        System.out.print(root.val + " ");
        // 递归遍历右子树
        inorderRecursive(root.right);
    }

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

        // 进行中序遍历
        inorderRecursive(root);
    }
}

迭代实现

迭代实现中序遍历通常使用栈来模拟递归调用的过程。以下是 Java 代码示例：

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class InorderTraversal {
    public static void inorderIterative(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // 遍历左子树，将节点压入栈中
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 弹出栈顶节点并访问
            current = stack.pop();
            System.out.print(current.val + " ");
            // 转向右子树
            current = current.right;
        }
    }

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

        // 进行中序遍历
        inorderIterative(root);
    }
}

3. 常见实践

验证二叉搜索树

中序遍历可以用于验证一棵二叉树是否为二叉搜索树（BST）。因为二叉搜索树的中序遍历结果是一个递增的有序序列。以下是 Java 代码示例：

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class ValidateBST {
    public static boolean isValidBST(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        inorderTraversal(root, inorder);
        for (int i = 1; i < inorder.size(); i++) {
            if (inorder.get(i) <= inorder.get(i - 1)) {
                return false;
            }
        }
        return true;
    }

    private static void inorderTraversal(TreeNode root, List<Integer> inorder) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, inorder);
        inorder.add(root.val);
        inorderTraversal(root.right, inorder);
    }

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

        // 验证是否为二叉搜索树
        System.out.println(isValidBST(root));
    }
}

4. 最佳实践

性能考虑

递归实现简单直观，但在处理大规模树时可能会导致栈溢出。迭代实现使用栈来模拟递归过程，避免了栈溢出的风险，但代码相对复杂。在实际应用中，应根据树的规模和性能要求选择合适的实现方式。

代码复用

将中序遍历的逻辑封装成独立的方法，方便在不同的场景中复用。例如，在验证二叉搜索树的代码中，将中序遍历的逻辑封装在 inorderTraversal 方法中。

小结

本文详细介绍了 Java 中中序遍历的基础概念、使用方法（递归和迭代实现）、常见实践（验证二叉搜索树）以及最佳实践（性能考虑和代码复用）。中序遍历是一种重要的二叉树遍历算法，在许多应用中都有广泛的应用。通过深入理解和掌握中序遍历，读者可以更好地处理二叉树相关的问题。

参考资料

《算法导论》
LeetCode 相关题目
GeeksforGeeks 网站关于二叉树遍历的文章