二叉树中序遍历java代码

### Java实现二叉树中序遍历 #### 方法一：递归实现 递归是一种直观且易于理解的方式来实现二叉树的中序遍历。以下是基于递归方式的具体代码示例： ```java public class BinaryTree { public static void inOrder(TreeNode root) { if (root == null) { return; } // 递归访问左子树 inOrder(root.left); // 访问根节点 System.out.print(root.val + " "); // 递归访问右子树 inOrder(root.right); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } } ``` 上述代码展示了如何通过递归的方式完成二叉树的中序遍历[^3]。 --- #### 方法二：迭代实现 对于不希望使用递归或者受限于递归调用栈的情况，可以采用迭代法来实现中序遍历。这种方法通常借助显式的栈数据结构来模拟递归过程。 以下是具体的迭代实现代码： ```java import java.util.ArrayList; import java.util.List; import java.util.Stack; public class BinaryTreeIteration { public static List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); 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(); result.add(current.val); // 转向右子树继续遍历 current = current.right; } return result; } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } } ``` 这段代码实现了利用栈进行迭代的中序遍历逻辑[^2]。 --- #### 示例输入与输出 假设有一个如下所示的二叉树： ``` 1 / \ 2 3 / \ 4 5 ``` 对应的中序遍历结果应为 `4 2 5 1 3`。 可以通过以下测试代码验证两种方法的结果一致性： ```java 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("Recursive Inorder Traversal:"); inOrder(root); // 使用迭代方法获取中序遍历列表 System.out.println("\nIterative Inorder Traversal:"); List<Integer> iterativeResult = inorderTraversal(root); for (int value : iterativeResult) { System.out.print(value + " "); } } ``` 以上代码分别演示了递归和迭代两种方法的应用场景及其输出效果。 ---

### 二叉树中序遍历的代码实现 以下是基于 Java 的二叉树中序遍历非递归算法的代码实现。此方法利用栈来模拟递归调用过程，按照 **左子树 -> 根节点 -> 右子树** 的顺序访问节点。 #### 定义二叉树节点类 首先定义 `TreeNode` 类作为二叉树的节点结构： ```java class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode() {} public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } ``` [^2] #### 非递归中序遍历实现 下面是完整的非递归中序遍历函数实现： ```java import java.util.Stack; public class BinaryTreeInorderTraversal { public static void inorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode current = root; while (current != null || !stack.isEmpty()) { // 将当前节点及其所有左子节点压入栈中 while (current != null) { stack.push(current); current = current.left; } // 如果当前节点为空，则弹出栈顶元素并访问它 if (!stack.isEmpty()) { current = stack.pop(); System.out.print(current.val + " "); // 访问根节点 // 转向右子树 current = current.right; } } } public static void main(String[] args) { // 构建测试用的二叉树 TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4, null, null), new TreeNode(5, null, null)), new TreeNode(3, new TreeNode(6, null, null), new TreeNode(7, null, null))); // 执行中序遍历 System.out.println("中序遍历结果:"); inorderTraversal(root); // 输出应为: 4 2 5 1 6 3 7 } } ``` [^1] 上述代码通过栈实现了二叉树的中序遍历逻辑。具体流程如下： - 使用一个指针变量 `current` 来指向当前正在处理的节点。 - 当前节点不为空时，将其压入栈并将指针移动到其左子节点。 - 若当前节点为空且栈不为空，则从栈中弹出顶部节点进行访问，并将指针设置为其右子节点。 - 循环执行直到栈为空且指针也为空为止。 --- ### 测试说明 对于给定的二叉树结构（见引用[3]），运行程序后输出的结果将是： `4 2 5 1 6 3 7` 这与理论上的中序遍历结果一致[^3]。 ---