二叉树中序遍历 代码
时间: 2025-05-29 22:15:08 浏览: 13
### 二叉树中序遍历的代码实现
以下是基于 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]。
---
阅读全文
相关推荐


















