Java树遍历完全指南（从零开始掌握二叉树的递归与非递归遍历方法）

三种遍历方式简介

• 前序遍历（Pre-order）：根 → 左子树 → 右子树
• 中序遍历（In-order）：左子树 → 根 → 右子树
• 后序遍历（Post-order）：左子树 → 右子树 → 根

第一步：定义二叉树节点

在开始遍历之前，我们先定义一个简单的二叉树节点类：

class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;        this.left = null;        this.right = null;    }}

第二步：递归遍历实现

递归遍历是最直观、最容易理解的方式。下面是三种遍历的递归实现：

// 前序遍历public void preOrder(TreeNode root) {    if (root == null) return;    System.out.print(root.val + " ");    preOrder(root.left);    preOrder(root.right);}// 中序遍历public void inOrder(TreeNode root) {    if (root == null) return;    inOrder(root.left);    System.out.print(root.val + " ");    inOrder(root.right);}// 后序遍历public void postOrder(TreeNode root) {    if (root == null) return;    postOrder(root.left);    postOrder(root.right);    System.out.print(root.val + " ");}

第三步：非递归遍历实现

虽然递归写法简洁，但在某些情况下（如树很深时）可能导致栈溢出。因此，掌握非递归遍历也很重要。我们通常使用栈（Stack）来模拟递归过程。

以下是非递归的前序遍历示例：

import java.util.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);        }    }}

中序和后序的非递归实现稍微复杂一些，但核心思想相同：利用栈来保存待访问的节点。

总结

通过本教程，你已经掌握了Java树遍历的核心知识：

• 理解了二叉树的基本结构
• 学会了三种遍历方式的逻辑
• 掌握了递归遍历与非递归遍历的代码实现

无论是面试还是实际开发，这些技能都非常实用。建议你动手编写代码并调试，加深理解。如果你对二叉树遍历还有疑问，欢迎在评论区留言交流！