概述
二叉树的中序遍历（In-order Traversal）是树遍历算法中的基础且重要的一种，遵循左子树 → 根节点 → 右子树的访问顺序。对于二叉搜索树（BST），中序遍历能够得到一个有序的节点序列，这一特性使其在许多算法和应用中发挥重要作用。
核心特点
- 访问顺序：左 → 根 → 右
- BST特性：对BST进行中序遍历得到升序序列
- 应用广泛：BST验证、排序、查找第K小元素等
- 实现多样：递归、迭代、Morris遍历三种主要方式
基础概念
2.1 中序遍历定义
中序遍历是深度优先搜索（DFS）的一种，按照以下规则访问二叉树节点：
- 递归遍历左子树
- 访问根节点
- 递归遍历右子树
2.2 遍历示例
考虑以下二叉树：
4
/ \
2 6
/ \ / \
1 3 5 7
中序遍历结果：1 → 2 → 3 → 4 → 5 → 6 → 7
2.3 树节点定义
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
递归实现
3.1 标准递归实现
递归是实现中序遍历最直观的方法：
/**
* 标准递归中序遍历
* 时间复杂度：O(n)
* 空间复杂度：O(h)，h为树的高度
*/
public class InorderTraversalRecursive {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
// 遍历左子树
inorderHelper(node.left, result);
// 访问根节点
result.add(node.val);
// 遍历右子树
inorderHelper(node.right, result);
}
}
3.2 函数式递归实现
使用函数式编程风格的递归实现：
/**
* 函数式递归中序遍历
* 更加简洁的实现方式
*/
public List<Integer> inorderTraversalFunctional(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> result = new ArrayList<>();
// 合并左子树、根节点、右子树的结果
result.addAll(inorderTraversalFunctional(root.left));
result.add(root.val);
result.addAll(inorderTraversalFunctional(root.right));
return result;
}
3.3 尾递归优化
虽然Java不支持尾递归优化，但我们可以模拟这种思想：
/**
* 尾递归风格的中序遍历
* 使用累加器模式
*/
public List<Integer> inorderTraversalTailRecursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTailHelper(root, result);
return result;
}
private void inorderTailHelper(TreeNode node, List<Integer> accumulator) {
if (node == null) {
return;
}
// 处理左子树
inorderTailHelper(node.left, accumulator);
// 处理当前节点
accumulator.add(node.val);
// 处理右子树（尾递归位置）
inorderTailHelper(node.right, accumulator);
}
3.4 递归深度控制
对于深度较大的树，需要控制递归深度避免栈溢出：
/**
* 带深度控制的递归中序遍历
* 防止栈溢出
*/
public class InorderWithDepthControl {
private static final int MAX_DEPTH = 1000;
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
try {
inorderWithDepth(root, result, 0);
} catch (StackOverflowException e) {
// 递归深度过大，转为迭代实现
return inorderIterative(root);
}
return result;
}
private void inorderWithDepth(TreeNode node, List<Integer> result, int depth)
throws StackOverflowException {
if (node == null) {
return;
}
if (depth > MAX_DEPTH) {
throw new StackOverflowException("递归深度超过限制");
}
inorderWithDepth(node.left, result, depth + 1);
result.add(node.val);
inorderWithDepth(node.right, result, depth + 1);
}
// 自定义异常
private static class StackOverflowException extends Exception {
public StackOverflowException(String message) {
super(message);
}
}
}
迭代实现
4.1 标准迭代实现
使用显式栈模拟递归过程：
/**
* 标准迭代中序遍历
* 使用栈模拟递归调用
*/
public List<Integer> inorderTraversalIterative(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;
}
4.2 优化的迭代实现
使用ArrayDeque替代Stack提升性能：
/**
* 优化的迭代中序遍历
* 使用ArrayDeque提升性能
*/
public List<Integer> inorderTraversalOptimized(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// 将左路径上的所有节点入栈
if (current != null) {
stack.push(current);
current = current.left;
} else {
// 处理栈顶节点
current = stack.pop();
result.add(current.val);
current = current.right;
}
}
return result;
}
4.3 预分配栈空间的实现
/**
* 预分配栈空间的迭代实现
* 减少栈扩容开销
*/
public List<Integer> inorderTraversalPreAllocated(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// 预估树的深度，预分配栈空间
int estimatedDepth = estimateTreeDepth(root);
Deque<TreeNode> stack = new ArrayDeque<>(estimatedDepth);
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;
}
/**
* 估算树的深度
* 用于预分配栈空间
*/
private int estimateTreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = estimateTreeDepth(root.left);
int rightDepth = estimateTreeDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
Morris遍历
5.1 Morris遍历原理
Morris遍历是一种巧妙的遍历方法，通过利用叶子节点的空指针来保存遍历信息，实现O(1)空间复杂度的遍历。
核心思想：
- 利用叶子节点的右指针指向后继节点
- 遍历完成后恢复树的原始结构
- 不需要额外的栈或递归空间
5.2 Morris中序遍历实现
/**
* Morris中序遍历
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
public List<Integer> inorderTraversalMorris(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// 没有左子树，直接访问当前节点
result.add(current.val);
current = current.right;
} else {
// 找到当前节点的前驱节点
TreeNode predecessor = findPredecessor(current);
if (predecessor.right == null) {
// 建立线索
predecessor.right = current;
current = current.left;
} else {
// 线索已存在，说明左子树已遍历完成
predecessor.right = null; // 恢复树结构
result.add(current.val);
current = current.right;
}
}
}
return result;
}
/**
* 找到当前节点的前驱节点
* 前驱节点是左子树中的最右节点
*/
private TreeNode findPredecessor(TreeNode node) {
TreeNode predecessor = node.left;
// 找到左子树的最右节点
while (predecessor.right != null && predecessor.right != node) {
predecessor = predecessor.right;
}
return predecessor;
}
5.3 Morris遍历详细步骤解析
/**
* Morris遍历的详细实现
* 包含详细的步骤注释
*/
public List<Integer> inorderTraversalMorrisDetailed(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// 情况1：当前节点没有左子树
// 直接访问当前节点，然后移动到右子树
System.out.println("访问节点: " + current.val);
result.add(current.val);
current = current.right;
} else {
// 情况2：当前节点有左子树
// 需要找到前驱节点并建立/断开线索
TreeNode predecessor = current.left;
// 找到前驱节点（左子树的最右节点）
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 子情况2.1：还未建立线索
// 建立从前驱节点到当前节点的线索
System.out.println("建立线索: " + predecessor.val + " -> " + current.val);
predecessor.right = current;
current = current.left;
} else {
// 子情况2.2：线索已存在
// 说明左子树已遍历完成，断开线索并访问当前节点
System.out.println("断开线索: " + predecessor.val + " -X-> " + current.val);
predecessor.right = null;
System.out.println("访问节点: " + current.val);
result.add(current.val);
current = current.right;
}
}
}
return result;
}
5.4 Morris遍历的优缺点
优点：
- 空间复杂度O(1)
- 不需要递归或栈
- 适合内存受限的环境
缺点：
- 代码复杂度较高
- 需要临时修改树结构
- 常数因子较大
变种问题
6.1 逆中序遍历
逆中序遍历按照右 → 根 → 左的顺序访问节点：
/**
* 逆中序遍历（右-根-左）
* 对于BST，得到降序序列
*/
public List<Integer> reverseInorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
reverseInorderHelper(root, result);
return result;
}
private void reverseInorderHelper(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
// 先遍历右子树
reverseInorderHelper(node.right, result);
// 访问根节点
result.add(node.val);
// 后遍历左子树
reverseInorderHelper(node.left, result);
}
6.2 范围中序遍历
只遍历指定范围内的节点：
/**
* 范围中序遍历
* 只访问值在[low, high]范围内的节点
*/
public List<Integer> rangeInorderTraversal(TreeNode root, int low, int high) {
List<Integer> result = new ArrayList<>();
rangeInorderHelper(root, low, high, result);
return result;
}
private void rangeInorderHelper(TreeNode node, int low, int high, List<Integer> result) {
if (node == null) {
return;
}
// 如果当前节点值大于low，才需要遍历左子树
if (node.val > low) {
rangeInorderHelper(node.left, low, high, result);
}
// 如果当前节点在范围内，添加到结果
if (node.val >= low && node.val <= high) {
result.add(node.val);
}
// 如果当前节点值小于high，才需要遍历右子树
if (node.val < high) {
rangeInorderHelper(node.right, low, high, result);
}
}
6.3 第K小元素
利用中序遍历找到BST中第K小的元素：
/**
* 找到BST中第K小的元素
* 利用中序遍历的有序性
*/
public int kthSmallest(TreeNode root, int k) {
Counter counter = new Counter();
return kthSmallestHelper(root, k, counter);
}
private int kthSmallestHelper(TreeNode node, int k, Counter counter) {
if (node == null) {
return -1;
}
// 遍历左子树
int leftResult = kthSmallestHelper(node.left, k, counter);
if (leftResult != -1) {
return leftResult;
}
// 访问当前节点
counter.count++;
if (counter.count == k) {
return node.val;
}
// 遍历右子树
return kthSmallestHelper(node.right, k, counter);
}
// 辅助类，用于计数
private static class Counter {
int count = 0;
}
6.4 中序遍历路径记录
记录从根到每个节点的路径：
/**
* 中序遍历并记录路径
* 记录从根节点到每个访问节点的路径
*/
public List<List<Integer>> inorderWithPath(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
inorderPathHelper(root, currentPath, result);
return result;
}
private void inorderPathHelper(TreeNode node, List<Integer> currentPath,
List<List<Integer>> result) {
if (node == null) {
return;
}
// 将当前节点加入路径
currentPath.add(node.val);
// 遍历左子树
inorderPathHelper(node.left, currentPath, result);
// 访问当前节点时，记录路径
result.add(new ArrayList<>(currentPath));
// 遍历右子树
inorderPathHelper(node.right, currentPath, result);
// 回溯，移除当前节点
currentPath.remove(currentPath.size() - 1);
}
复杂度分析与优化
7.1 时间复杂度分析
| 实现方式 | 时间复杂度 | 说明 |
|---|---|---|
| 递归实现 | O(n) | 每个节点访问一次 |
| 迭代实现 | O(n) | 每个节点入栈出栈一次 |
| Morris遍历 | O(n) | 每个节点最多访问3次 |
7.2 空间复杂度分析
| 实现方式 | 空间复杂度 | 说明 |
|---|---|---|
| 递归实现 | O(h) | 递归栈深度，h为树高 |
| 迭代实现 | O(h) | 显式栈空间 |
| Morris遍历 | O(1) | 只使用常数额外空间 |
7.3 性能优化策略
7.3.1 递归优化
/**
* 优化的递归实现
* 减少函数调用开销
*/
public class OptimizedRecursiveInorder {
private List<Integer> result;
public List<Integer> inorderTraversal(TreeNode root) {
// 预估结果集大小，减少扩容
int estimatedSize = estimateNodeCount(root);
result = new ArrayList<>(estimatedSize);
inorderHelper(root);
return result;
}
private void inorderHelper(TreeNode node) {
if (node == null) {
return;
}
inorderHelper(node.left);
result.add(node.val);
inorderHelper(node.right);
}
private int estimateNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + estimateNodeCount(root.left) + estimateNodeCount(root.right);
}
}
7.3.2 迭代优化
/**
* 高性能迭代实现
* 使用数组模拟栈，避免对象创建
*/
public List<Integer> inorderTraversalHighPerf(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> result = new ArrayList<>();
// 使用数组模拟栈，提升性能
TreeNode[] stack = new TreeNode[1000]; // 假设树深度不超过1000
int top = -1;
TreeNode current = root;
while (current != null || top >= 0) {
while (current != null) {
stack[++top] = current;
current = current.left;
}
current = stack[top--];
result.add(current.val);
current = current.right;
}
return result;
}
7.3.3 内存池优化
/**
* 使用内存池的优化实现
* 重用对象，减少GC压力
*/
public class MemoryPoolInorder {
private final Queue<List<Integer>> listPool = new ArrayDeque<>();
private final Queue<Stack<TreeNode>> stackPool = new ArrayDeque<>();
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = borrowList();
Stack<TreeNode> stack = borrowStack();
try {
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 new ArrayList<>(result);
} finally {
returnList(result);
returnStack(stack);
}
}
private List<Integer> borrowList() {
List<Integer> list = listPool.poll();
if (list == null) {
list = new ArrayList<>();
} else {
list.clear();
}
return list;
}
private void returnList(List<Integer> list) {
if (list.size() < 1000) { // 避免内存池过大
listPool.offer(list);
}
}
private Stack<TreeNode> borrowStack() {
Stack<TreeNode> stack = stackPool.poll();
if (stack == null) {
stack = new Stack<>();
} else {
stack.clear();
}
return stack;
}
private void returnStack(Stack<TreeNode> stack) {
if (stack.capacity() < 1000) {
stackPool.offer(stack);
}
}
}
相关LeetCode题目
8.1 LeetCode 94: 二叉树的中序遍历
题目描述：给定一个二叉树的根节点root，返回它的中序遍历。
/**
* LeetCode 94: 二叉树的中序遍历
* 三种解法的完整实现
*/
public class Solution94 {
// 解法1：递归
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node != null) {
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
}
// 解法2：迭代
public List<Integer> inorderTraversal2(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;
}
// 解法3：Morris遍历
public List<Integer> inorderTraversal3(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
result.add(current.val);
current = current.right;
} else {
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
result.add(current.val);
current = current.right;
}
}
}
return result;
}
}
8.2 LeetCode 98: 验证二叉搜索树
题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。
/**
* LeetCode 98: 验证二叉搜索树
* 利用中序遍历的有序性
*/
public class Solution98 {
// 方法1：中序遍历 + 有序性检查
public boolean isValidBST1(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 void inorderTraversal(TreeNode node, List<Integer> result) {
if (node != null) {
inorderTraversal(node.left, result);
result.add(node.val);
inorderTraversal(node.right, result);
}
}
// 方法2：中序遍历 + 即时检查（优化空间）
private Integer prev = null;
public boolean isValidBST2(TreeNode root) {
prev = null;
return inorderCheck(root);
}
private boolean inorderCheck(TreeNode node) {
if (node == null) {
return true;
}
// 检查左子树
if (!inorderCheck(node.left)) {
return false;
}
// 检查当前节点
if (prev != null && node.val <= prev) {
return false;
}
prev = node.val;
// 检查右子树
return inorderCheck(node.right);
}
// 方法3：范围检查（更高效）
public boolean isValidBST3(TreeNode root) {
return validate(root, null, null);
}
private boolean validate(TreeNode node, Integer min, Integer max) {
if (node == null) {
return true;
}
if ((min != null && node.val <= min) ||
(max != null && node.val >= max)) {
return false;
}
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
}
8.3 LeetCode 230: 二叉搜索树中第K小的元素
/**
* LeetCode 230: 二叉搜索树中第K小的元素
* 利用中序遍历找第K小元素
*/
public class Solution230 {
// 方法1：中序遍历 + 计数
private int count = 0;
private int result = 0;
public int kthSmallest1(TreeNode root, int k) {
count = 0;
inorderCount(root, k);
return result;
}
private void inorderCount(TreeNode node, int k) {
if (node == null) {
return;
}
inorderCount(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inorderCount(node.right, k);
}
// 方法2：迭代实现
public int kthSmallest2(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
int count = 0;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
count++;
if (count == k) {
return current.val;
}
current = current.right;
}
return -1; // 不应该到达这里
}
// 方法3：Morris遍历实现
public int kthSmallest3(TreeNode root, int k) {
TreeNode current = root;
int count = 0;
while (current != null) {
if (current.left == null) {
count++;
if (count == k) {
return current.val;
}
current = current.right;
} else {
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
count++;
if (count == k) {
return current.val;
}
current = current.right;
}
}
}
return -1;
}
}
8.4 LeetCode 285: 二叉搜索树中的中序后继
/**
* LeetCode 285: 二叉搜索树中的中序后继
* 找到给定节点在中序遍历中的下一个节点
*/
public class Solution285 {
// 方法1：中序遍历找后继
public TreeNode inorderSuccessor1(TreeNode root, TreeNode p) {
List<TreeNode> inorder = new ArrayList<>();
inorderTraversal(root, inorder);
for (int i = 0; i < inorder.size() - 1; i++) {
if (inorder.get(i) == p) {
return inorder.get(i + 1);
}
}
return null;
}
private void inorderTraversal(TreeNode node, List<TreeNode> result) {
if (node != null) {
inorderTraversal(node.left, result);
result.add(node);
inorderTraversal(node.right, result);
}
}
// 方法2：利用BST性质（更高效）
public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
TreeNode successor = null;
TreeNode current = root;
while (current != null) {
if (current.val > p.val) {
successor = current;
current = current.left;
} else {
current = current.right;
}
}
return successor;
}
// 方法3：递归实现
public TreeNode inorderSuccessor3(TreeNode root, TreeNode p) {
if (root == null) {
return null;
}
if (root.val <= p.val) {
return inorderSuccessor3(root.right, p);
} else {
TreeNode left = inorderSuccessor3(root.left, p);
return left != null ? left : root;
}
}
}
面试问题解析
9.1 常见面试问题
Q1: 递归和迭代实现中序遍历的优缺点是什么？
答案：
递归实现：
- 优点：代码简洁直观，易于理解和实现
- 缺点：可能导致栈溢出，空间复杂度取决于树的深度
迭代实现：
- 优点：避免栈溢出，可以处理更深的树
- 缺点：代码相对复杂，需要手动管理栈
Q2: Morris遍历的原理是什么？有什么优缺点？
答案：
Morris遍历利用叶子节点的空指针来保存遍历信息，通过建立和断开线索来实现O(1)空间复杂度的遍历。
优点：
- 空间复杂度O(1)
- 不需要递归或栈
缺点：
- 代码复杂度高
- 需要临时修改树结构
- 常数因子较大
Q3: 如何利用中序遍历验证二叉搜索树？
答案：
对BST进行中序遍历会得到一个严格递增的序列。可以通过以下方式验证：
- 完整遍历后检查序列是否有序
- 遍历过程中即时检查当前节点是否大于前一个节点
- 使用范围检查（更高效）
Q4: 如何在中序遍历中找到第K小的元素？
答案：
利用中序遍历的有序性，在遍历过程中计数，当计数达到K时返回当前节点值。可以使用递归、迭代或Morris遍历实现。
9.2 进阶面试问题
Q5: 如何在不修改树结构的情况下实现O(1)空间的中序遍历？
答案：
严格来说，在不修改树结构的情况下无法实现真正的O(1)空间中序遍历。Morris遍历虽然是O(1)空间，但会临时修改树结构。
可能的替代方案：
- 使用线程化二叉树（预处理时建立线索）
- 使用父指针（如果节点包含父指针）
Q6: 如何处理超大规模的二叉树遍历？
答案：
- 分层处理：将树分层存储，逐层遍历
- 流式处理：使用迭代器模式，按需生成结果
- 并行处理：将子树分配给不同线程处理
- 外存处理：对于无法完全加载到内存的树，使用外存算法
/**
* 流式中序遍历迭代器
* 适用于大规模数据处理
*/
public class InorderIterator implements Iterator<Integer> {
private Stack<TreeNode> stack;
private TreeNode current;
public InorderIterator(TreeNode root) {
stack = new Stack<>();
current = root;
pushLeft(current);
}
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
TreeNode node = stack.pop();
pushLeft(node.right);
return node.val;
}
private void pushLeft(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
}
实际应用场景
10.1 数据库索引遍历
数据库的B+树索引使用类似中序遍历的方式进行范围查询：
/**
* 模拟数据库索引的范围查询
* 使用中序遍历实现
*/
public class DatabaseIndexRange {
public List<Integer> rangeQuery(TreeNode root, int start, int end) {
List<Integer> result = new ArrayList<>();
rangeQueryHelper(root, start, end, result);
return result;
}
private void rangeQueryHelper(TreeNode node, int start, int end,
List<Integer> result) {
if (node == null) {
return;
}
// 剪枝：如果当前节点值大于start，才遍历左子树
if (node.val > start) {
rangeQueryHelper(node.left, start, end, result);
}
// 如果当前节点在范围内，添加到结果
if (node.val >= start && node.val <= end) {
result.add(node.val);
}
// 剪枝：如果当前节点值小于end，才遍历右子树
if (node.val < end) {
rangeQueryHelper(node.right, start, end, result);
}
}
}
10.2 编译器语法树遍历
编译器在处理表达式时使用中序遍历生成中缀表达式：
/**
* 表达式树的中序遍历
* 生成中缀表达式
*/
public class ExpressionTree {
static class ExprNode {
String value;
ExprNode left;
ExprNode right;
boolean isOperator;
ExprNode(String value, boolean isOperator) {
this.value = value;
this.isOperator = isOperator;
}
}
public String toInfixExpression(ExprNode root) {
StringBuilder sb = new StringBuilder();
inorderExpression(root, sb);
return sb.toString();
}
private void inorderExpression(ExprNode node, StringBuilder sb) {
if (node == null) {
return;
}
// 如果是操作符且有子节点，需要加括号
boolean needParentheses = node.isOperator &&
(node.left != null || node.right != null);
if (needParentheses) {
sb.append("(");
}
// 遍历左子树
inorderExpression(node.left, sb);
// 访问当前节点
sb.append(node.value);
// 遍历右子树
inorderExpression(node.right, sb);
if (needParentheses) {
sb.append(")");
}
}
}
10.3 文件系统目录遍历
文件系统的目录结构可以看作树，中序遍历可用于特定的排序需求：
/**
* 文件系统目录的中序遍历
* 按照特定规则排序文件和目录
*/
public class FileSystemTraversal {
static class FileNode {
String name;
boolean isDirectory;
FileNode left;
FileNode right;
long size;
long lastModified;
FileNode(String name, boolean isDirectory) {
this.name = name;
this.isDirectory = isDirectory;
}
}
// 按文件大小中序遍历
public List<String> traverseBySize(FileNode root) {
List<String> result = new ArrayList<>();
inorderBySize(root, result);
return result;
}
private void inorderBySize(FileNode node, List<String> result) {
if (node == null) {
return;
}
inorderBySize(node.left, result);
result.add(node.name + " (" + node.size + " bytes)");
inorderBySize(node.right, result);
}
// 按修改时间中序遍历
public List<String> traverseByTime(FileNode root) {
List<String> result = new ArrayList<>();
inorderByTime(root, result);
return result;
}
private void inorderByTime(FileNode node, List<String> result) {
if (node == null) {
return;
}
inorderByTime(node.left, result);
result.add(node.name + " (" + new Date(node.lastModified) + ")");
inorderByTime(node.right, result);
}
}
性能测试与基准
11.1 性能测试框架
/**
* 中序遍历性能测试
* 比较不同实现方式的性能
*/
public class InorderPerformanceTest {
@Test
public void benchmarkInorderTraversals() {
// 创建不同规模的测试树
TreeNode smallTree = createBalancedTree(10); // 2^10 - 1 = 1023个节点
TreeNode mediumTree = createBalancedTree(15); // 2^15 - 1 = 32767个节点
TreeNode largeTree = createBalancedTree(20); // 2^20 - 1 = 1048575个节点
System.out.println("=== 中序遍历性能测试 ===");
// 测试小规模树
System.out.println("\n小规模树 (1023个节点):");
benchmarkTree(smallTree, "小规模");
// 测试中等规模树
System.out.println("\n中等规模树 (32767个节点):");
benchmarkTree(mediumTree, "中等规模");
// 测试大规模树
System.out.println("\n大规模树 (1048575个节点):");
benchmarkTree(largeTree, "大规模");
}
private void benchmarkTree(TreeNode root, String scale) {
int iterations = 100;
// 预热JVM
for (int i = 0; i < 10; i++) {
inorderRecursive(root);
inorderIterative(root);
inorderMorris(root);
}
// 测试递归实现
long startTime = System.nanoTime();
for (int i = 0; i < iterations; i++) {
inorderRecursive(root);
}
long recursiveTime = System.nanoTime() - startTime;
// 测试迭代实现
startTime = System.nanoTime();
for (int i = 0; i < iterations; i++) {
inorderIterative(root);
}
long iterativeTime = System.nanoTime() - startTime;
// 测试Morris遍历
startTime = System.nanoTime();
for (int i = 0; i < iterations; i++) {
inorderMorris(root);
}
long morrisTime = System.nanoTime() - startTime;
// 输出结果
System.out.printf("递归实现: %.2f ms\n", recursiveTime / 1_000_000.0);
System.out.printf("迭代实现: %.2f ms\n", iterativeTime / 1_000_000.0);
System.out.printf("Morris遍历: %.2f ms\n", morrisTime / 1_000_000.0);
// 性能比较
double iterativeSpeedup = (double) recursiveTime / iterativeTime;
double morrisSpeedup = (double) recursiveTime / morrisTime;
System.out.printf("迭代相对递归提升: %.2fx\n", iterativeSpeedup);
System.out.printf("Morris相对递归提升: %.2fx\n", morrisSpeedup);
}
// 创建平衡二叉树用于测试
private TreeNode createBalancedTree(int depth) {
if (depth <= 0) {
return null;
}
TreeNode root = new TreeNode(1);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int nodeValue = 2;
for (int level = 1; level < depth; level++) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
node.left = new TreeNode(nodeValue++);
node.right = new TreeNode(nodeValue++);
queue.offer(node.left);
queue.offer(node.right);
}
}
return root;
}
// 各种实现方法（简化版）
private List<Integer> inorderRecursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node != null) {
inorderHelper(node.left, result);
result.add(node.val);
inorderHelper(node.right, result);
}
}
private List<Integer> inorderIterative(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;
}
private List<Integer> inorderMorris(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
result.add(current.val);
current = current.right;
} else {
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
result.add(current.val);
current = current.right;
}
}
}
return result;
}
}
11.2 内存使用测试
/**
* 内存使用测试
* 比较不同实现的内存消耗
*/
public class MemoryUsageTest {
@Test
public void testMemoryUsage() {
TreeNode testTree = createSkewedTree(1000); // 创建偏斜树
System.out.println("=== 内存使用测试 ===");
// 测试递归实现的内存使用
testRecursiveMemory(testTree);
// 测试迭代实现的内存使用
testIterativeMemory(testTree);
// 测试Morris遍历的内存使用
testMorrisMemory(testTree);
}
private void testRecursiveMemory(TreeNode root) {
Runtime runtime = Runtime.getRuntime();
// 强制垃圾回收
System.gc();
long beforeMemory = runtime.totalMemory() - runtime.freeMemory();
// 执行递归遍历
List<Integer> result = inorderRecursive(root);
long afterMemory = runtime.totalMemory() - runtime.freeMemory();
long memoryUsed = afterMemory - beforeMemory;
System.out.printf("递归实现内存使用: %d KB\n", memoryUsed / 1024);
}
private void testIterativeMemory(TreeNode root) {
Runtime runtime = Runtime.getRuntime();
System.gc();
long beforeMemory = runtime.totalMemory() - runtime.freeMemory();
List<Integer> result = inorderIterative(root);
long afterMemory = runtime.totalMemory() - runtime.freeMemory();
long memoryUsed = afterMemory - beforeMemory;
System.out.printf("迭代实现内存使用: %d KB\n", memoryUsed / 1024);
}
private void testMorrisMemory(TreeNode root) {
Runtime runtime = Runtime.getRuntime();
System.gc();
long beforeMemory = runtime.totalMemory() - runtime.freeMemory();
List<Integer> result = inorderMorris(root);
long afterMemory = runtime.totalMemory() - runtime.freeMemory();
long memoryUsed = afterMemory - beforeMemory;
System.out.printf("Morris遍历内存使用: %d KB\n", memoryUsed / 1024);
}
// 创建偏斜树（最坏情况）
private TreeNode createSkewedTree(int n) {
if (n <= 0) {
return null;
}
TreeNode root = new TreeNode(1);
TreeNode current = root;
for (int i = 2; i <= n; i++) {
current.right = new TreeNode(i);
current = current.right;
}
return root;
}
}
11.3 性能测试结果分析
基于实际测试，不同实现方式的性能特点：
| 实现方式 | 时间性能 | 空间使用 | 适用场景 |
|---|---|---|---|
| 递归实现 | 中等 | 高（O(h)） | 平衡树，代码简洁性优先 |
| 迭代实现 | 最好 | 中等（O(h)） | 深度较大的树，性能优先 |
| Morris遍历 | 较差 | 最好（O(1)） | 内存受限环境 |
性能优化建议：
- 对于平衡树，递归实现简洁且性能可接受
- 对于深度较大的树，使用迭代实现避免栈溢出
- 在内存极度受限的环境下，考虑Morris遍历
- 对于频繁遍历的场景，可以考虑缓存结果
最佳实践总结
12.1 高级中序遍历技巧与优化
基于现代算法库的最佳实践，我们可以进一步优化中序遍历的实现：
// 基于 data-structure-typed 库的高性能实现
import { BST, BSTNode } from 'data-structure-typed';
class AdvancedInorderTraversal {
private result: number[] = [];
private nodePool: BSTNode<number>[] = []; // 对象池优化
// 高性能迭代实现（避免递归开销）
inorderIterativeOptimized<T>(root: BSTNode<T> | null): T[] {
if (!root) return [];
const result: T[] = [];
const stack: BSTNode<T>[] = [];
let current = root;
// 预分配栈空间，避免动态扩容
stack.length = this.estimateMaxDepth(root);
let stackTop = -1;
while (stackTop >= 0 || current) {
// 到达最左节点
while (current) {
stack[++stackTop] = current;
current = current.left;
}
// 处理当前节点
current = stack[stackTop--];
result.push(current.key);
// 转向右子树
current = current.right;
}
return result;
}
// 内存优化的Morris遍历
morrisInorderOptimized<T>(root: BSTNode<T> | null): T[] {
if (!root) return [];
const result: T[] = [];
let current = root;
while (current) {
if (!current.left) {
result.push(current.key);
current = current.right;
} else {
// 找到前驱节点
let predecessor = current.left;
while (predecessor.right && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (!predecessor.right) {
// 建立线索
predecessor.right = current;
current = current.left;
} else {
// 恢复树结构
predecessor.right = null;
result.push(current.key);
current = current.right;
}
}
}
return result;
}
// 估算树的最大深度（用于栈预分配）
private estimateMaxDepth<T>(root: BSTNode<T>): number {
if (!root) return 0;
return Math.max(
this.estimateMaxDepth(root.left),
this.estimateMaxDepth(root.right)
) + 1;
}
// 并发安全的中序遍历
async inorderConcurrentSafe<T>(root: BSTNode<T> | null): Promise<T[]> {
return new Promise((resolve) => {
// 使用 Worker 或 setTimeout 避免阻塞主线程
setTimeout(() => {
const result = this.inorderIterativeOptimized(root);
resolve(result);
}, 0);
});
}
}
12.2 性能基准测试与对比
// 性能测试框架
class InorderPerformanceBenchmark {
private bst: BST<number>;
constructor() {
this.bst = new BST<number>();
// 构建测试数据
this.bst.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);
}
// 基准测试
runBenchmarks(): void {
const iterations = 10000;
const traversal = new AdvancedInorderTraversal();
console.log('=== 中序遍历性能基准测试 ===');
// 测试递归实现
const recursiveStart = performance.now();
for (let i = 0; i < iterations; i++) {
this.recursiveInorder(this.bst.root);
}
const recursiveTime = performance.now() - recursiveStart;
// 测试迭代实现
const iterativeStart = performance.now();
for (let i = 0; i < iterations; i++) {
traversal.inorderIterativeOptimized(this.bst.root);
}
const iterativeTime = performance.now() - iterativeStart;
// 测试Morris遍历
const morrisStart = performance.now();
for (let i = 0; i < iterations; i++) {
traversal.morrisInorderOptimized(this.bst.root);
}
const morrisTime = performance.now() - morrisStart;
// 输出结果
console.log(`递归实现: ${recursiveTime.toFixed(2)}ms`);
console.log(`迭代实现: ${iterativeTime.toFixed(2)}ms`);
console.log(`Morris遍历: ${morrisTime.toFixed(2)}ms`);
// 内存使用情况
this.measureMemoryUsage();
}
private recursiveInorder<T>(root: BSTNode<T> | null): T[] {
if (!root) return [];
return [
...this.recursiveInorder(root.left),
root.key,
...this.recursiveInorder(root.right)
];
}
private measureMemoryUsage(): void {
if (typeof performance !== 'undefined' && performance.memory) {
const memory = performance.memory;
console.log('=== 内存使用情况 ===');
console.log(`已使用堆内存: ${(memory.usedJSHeapSize / 1024 / 1024).toFixed(2)} MB`);
console.log(`总堆内存: ${(memory.totalJSHeapSize / 1024 / 1024).toFixed(2)} MB`);
console.log(`堆内存限制: ${(memory.jsHeapSizeLimit / 1024 / 1024).toFixed(2)} MB`);
}
}
}
12.3 实际应用场景扩展
// 实际应用：文件系统遍历
class FileSystemInorderTraversal {
// 模拟文件系统节点
interface FileNode {
name: string;
isDirectory: boolean;
children?: FileNode[];
size?: number;
}
// 按字典序遍历文件系统
traverseFileSystem(root: FileNode): string[] {
const result: string[] = [];
const inorder = (node: FileNode | null) => {
if (!node) return;
// 对子节点排序（模拟BST的有序性）
const sortedChildren = node.children?.sort((a, b) =>
a.name.localeCompare(b.name)
) || [];
const midIndex = Math.floor(sortedChildren.length / 2);
// 遍历左半部分
for (let i = 0; i < midIndex; i++) {
inorder(sortedChildren[i]);
}
// 处理当前节点
result.push(node.name);
// 遍历右半部分
for (let i = midIndex; i < sortedChildren.length; i++) {
inorder(sortedChildren[i]);
}
};
inorder(root);
return result;
}
}
// 实际应用：数据库索引遍历
class DatabaseIndexTraversal {
// 模拟B+树索引的中序遍历
traverseIndex(indexRoot: any): any[] {
// 实现数据库索引的有序遍历
// 这在数据库查询优化中非常重要
return [];
}
}
12.4 代码质量与测试策略
// 完整的测试套件
class ComprehensiveInorderTests {
private traversal: AdvancedInorderTraversal;
constructor() {
this.traversal = new AdvancedInorderTraversal();
}
// 边界条件测试
testEdgeCases(): void {
console.log('=== 边界条件测试 ===');
// 空树
console.assert(
JSON.stringify(this.traversal.inorderIterativeOptimized(null)) === '[]',
'空树测试失败'
);
// 单节点
const singleNode = new BSTNode(42);
console.assert(
JSON.stringify(this.traversal.inorderIterativeOptimized(singleNode)) === '[42]',
'单节点测试失败'
);
console.log('边界条件测试通过 ✓');
}
// 正确性验证
testCorrectness(): void {
console.log('=== 正确性验证 ===');
const bst = new BST<number>();
bst.addMany([4, 2, 6, 1, 3, 5, 7]);
const expected = [1, 2, 3, 4, 5, 6, 7];
const actual = this.traversal.inorderIterativeOptimized(bst.root);
console.assert(
JSON.stringify(actual) === JSON.stringify(expected),
`正确性测试失败: 期望 ${expected}, 实际 ${actual}`
);
console.log('正确性验证通过 ✓');
}
// 性能回归测试
testPerformanceRegression(): void {
console.log('=== 性能回归测试 ===');
const bst = new BST<number>();
const largeDataSet = Array.from({length: 1000}, (_, i) => i);
bst.addMany(largeDataSet);
const start = performance.now();
this.traversal.inorderIterativeOptimized(bst.root);
const duration = performance.now() - start;
// 性能阈值检查
const maxAllowedTime = 10; // 10ms
console.assert(
duration < maxAllowedTime,
`性能回归: 耗时 ${duration}ms 超过阈值 ${maxAllowedTime}ms`
);
console.log(`性能测试通过 ✓ (耗时: ${duration.toFixed(2)}ms)`);
}
}
12.5 扩展思考与学习建议
- 分布式遍历：在分布式系统中如何实现树的遍历
- 大规模数据处理：处理无法完全加载到内存的大型树结构
- 实时遍历：在动态变化的树结构上进行实时遍历
- 可视化工具：开发树遍历过程的可视化工具
- 算法变种：研究其他树遍历算法的优化技巧
// 学习路径建议
const learningPath = {
beginner: [
'掌握基本的递归实现',
'理解中序遍历的应用场景',
'练习相关LeetCode题目'
],
intermediate: [
'学习迭代实现和Morris遍历',
'理解时间空间复杂度权衡',
'掌握性能优化技巧'
],
advanced: [
'研究并发和分布式遍历',
'开发自定义遍历算法',
'贡献开源算法库'
]
};
总结
二叉树的中序遍历是树结构操作的基础，通过本文的深入学习，你不仅掌握了基本的实现方法，还了解了现代算法库中的最佳实践。关键收获包括：
- 多种实现方式：递归、迭代、Morris遍历各有优势
- 性能优化技巧：内存预分配、对象池、并发处理
- 实际应用场景：文件系统、数据库索引、搜索算法
- 代码质量保证：完整的测试策略和性能监控
- 扩展学习方向：分布式处理、大规模数据、实时系统
继续深入学习和实践，你将能够在复杂的系统设计中灵活运用这些知识！
文章标签
冬眠
博主专注于技术、阅读与思考。在这里记录学习、思考与生活。
系列：二叉树
第 3 篇，共 5 篇