从入门到精通：Java实现二叉树遍历的完整代码示例

在Java开发中，树（Tree）是一种非常重要的非线性数据结构，广泛应用于文件系统、数据库索引、DOM解析等场景。掌握树的遍历方法是每个Java开发者必备的技能。本文将详细介绍Java中遍历树的5种经典方法，包括递归和非递归实现，并提供完整的代码示例和性能分析。

一、树的基本概念回顾

在开始讲解遍历方法之前，我们先简单回顾一下树的基本概念。树是由n(n≥0)个节点组成的有限集合，当n=0时称为空树。非空树具有以下特点：

1. 有且仅有一个特定的称为根(Root)的节点
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树

常见的树结构包括二叉树、二叉搜索树、平衡二叉树(AVL树)、红黑树等。本文将以二叉树为例进行讲解，但所述方法同样适用于其他树结构。

二、深度优先遍历(DFS)

深度优先遍历按照访问根节点的顺序不同，可分为三种方式：前序遍历、中序遍历和后序遍历。

1. 递归实现

递归是最直观的树遍历方法，代码简洁易懂。

前序遍历(Pre-order)

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

中序遍历(In-order)

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

后序遍历(Post-order)

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

2. 迭代实现

虽然递归实现简洁，但在处理大规模树结构时可能导致栈溢出。这时可以使用迭代方法，借助栈(Stack)来模拟递归过程。

前序遍历迭代实现

public void preOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");

        // 注意先压入右节点，再压入左节点
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

中序遍历迭代实现

public void inOrderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}

后序遍历迭代实现

后序遍历的迭代实现较为复杂，需要记录节点的访问状态：

public void postOrderIterative(TreeNode root) {
    if (root == null) return;

    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode curr = stack.peek();

        // 如果当前节点是叶子节点，或者前一个访问的节点是当前节点的子节点
        if ((curr.left == null && curr.right == null) || 
            (prev != null && (prev == curr.left || prev == curr.right))) {
            System.out.print(curr.val + " ");
            stack.pop();
            prev = curr;
        } else {
            if (curr.right != null) stack.push(curr.right);
            if (curr.left != null) stack.push(curr.left);
        }
    }
}

三、广度优先遍历(BFS)

广度优先遍历也称为层次遍历，它按照树的层次逐层访问节点。这种遍历方式需要使用队列(Queue)来实现。

基本广度优先遍历

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");

        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

带层次信息的广度优先遍历

有时我们需要知道每个节点所在的层次，可以稍作修改：

public void levelOrderWithLevel(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int level = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        System.out.print("Level " + level + ": ");

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        System.out.println();
        level++;
    }
}

四、Morris遍历算法

Morris遍历是一种空间复杂度为O(1)的树遍历算法，它通过临时修改树的结构来实现遍历，完成后会恢复树的结构。

Morris中序遍历

public void morrisInOrder(TreeNode root) {
    TreeNode curr = root;

    while (curr != null) {
        if (curr.left == null) {
            System.out.print(curr.val + " ");
            curr = curr.right;
        } else {
            TreeNode predecessor = curr.left;
            while (predecessor.right != null && predecessor.right != curr) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                predecessor.right = curr; // 创建临时链接
                curr = curr.left;
            } else {
                predecessor.right = null; // 恢复树结构
                System.out.print(curr.val + " ");
                curr = curr.right;
            }
        }
    }
}

五、遍历方法的选择与性能比较

1. 递归方法：代码简洁，但存在栈溢出风险，适合小规模树结构
2. 迭代方法：使用栈或队列，空间复杂度O(n)，适合大多数场景
3. Morris遍历：空间复杂度O(1)，但会临时修改树结构，适合内存受限环境

时间复杂度方面，所有方法都是O(n)，因为每个节点都需要访问一次。

六、实际应用场景

1. 前序遍历：用于复制树结构，序列化树
2. 中序遍历：二叉搜索树会得到有序序列
3. 后序遍历：用于删除树，计算表达式树
4. 广度优先遍历：用于查找最短路径，层次相关操作

七、完整示例代码

以下是包含TreeNode定义和测试代码的完整示例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) { val = x; }
}

public class TreeTraversal {
    // 这里包含前面所有的遍历方法实现

    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);

        System.out.println("递归前序遍历:");
        new TreeTraversal().preOrderTraversal(root);

        System.out.println("\n迭代前序遍历:");
        new TreeTraversal().preOrderIterative(root);

        // 其他遍历方法的测试类似
    }
}

八、总结

本文详细介绍了Java中遍历树的5种经典方法，包括递归和迭代实现的深度优先遍历、广度优先遍历以及空间复杂度最优的Morris遍历。每种方法都有其适用场景，开发者应根据具体需求选择最合适的遍历方式。

掌握这些树遍历方法不仅有助于解决算法面试题，更能帮助开发者在实际项目中高效处理树形结构数据。建议读者动手实现每种方法，并通过不同的树结构来测试和验证代码的正确性。