image-20251027181908179

image-20251027181933593

二叉树中序遍历总结（含栈的深度理解

一、什么是二叉树中序遍历

中序遍历的核心规则是 “左 - 根 - 右”：先中序遍历左子树，再访问根节点，最后中序遍历右子树。

以简单二叉树（根A，左孩子B，右孩子C）为例，中序遍历结果为 B → A → C（即BAC）。

二、普通递归方法（基于修正后的二叉树结构）

修正后的二叉树结构：

      A
     / \
    B   C
   /   / \
  D   E   F
 / \   \
G   H   I

递归逻辑：通过 “函数调用栈” 隐式实现 “左 - 根 - 右” 的顺序。每调用一次遍历函数，就将当前节点压入系统栈，先处理左子树，再访问根，最后处理右子树。

步骤拆解：

  1. 遍历A的左子树B → 遍历B的左子树D → 遍历D的左子树G（无左子树，访问G）→ 访问D → 遍历D的右子树H（访问H）→ 访问B → 访问A → 遍历A的右子树C → 遍历C的左子树E（无左子树，访问E）→ 遍历E的右子树I（访问I）→ 访问C → 遍历C的右子树F（访问F）。
  2. 最终结果：GDHBAEICF。

三、非递归方法（显式栈模拟）

递归的本质是系统栈的调用，非递归方法通过自定义栈显式模拟这一过程，核心逻辑可总结为：“压栈左链 → 弹出访问 → 处理右子树”。

栈的角色理解

栈在这里承担了 “记录回溯路径” 的作用：

  • 压栈：将需要后续处理的节点（根、右子树）暂存到栈中，优先处理左子树。
  • 弹栈：当左子树处理完毕，弹出栈顶节点（即当前子树的根）访问，再处理其右子树。

基于修正后的二叉树，非递归遍历步骤（结合栈操作）：

步骤 栈内元素 访问节点 操作逻辑
1 [] - 初始化栈，指针p指向根A
2 [A] - p沿左链遍历，将A、B、D、G依次压栈，直到G无左孩子
3 [A,B,D] G 弹出G（无右孩子），访问G
4 [A,B] D 弹出D，访问D；p指向D的右孩子H
5 [A,B,H] - H无左孩子，压栈H
6 [A,B] H 弹出H（无右孩子），访问H
7 [A] B 弹出B，访问B；p指向B的右孩子（无）
8 [] A 弹出A，访问A；p指向A的右孩子C
9 [C] - p沿左链遍历，将C、E依次压栈，直到E的左孩子（无）
10 [C,E] - p指向E的右孩子I，压栈I
11 [C] I 弹出I（无右孩子），访问I
12 [] E 弹出E，访问E；p指向E的右孩子（无）
13 [] C 弹出C，访问C；p指向C的右孩子F
14 [F] - F无左孩子，压栈F
15 [] F 弹出F，访问F

最终遍历结果：GDHBAEICF。

个人对 “栈” 的理解

无论是递归的系统栈还是非递归的自定义栈，其核心作用都是 “保存节点的回溯路径”。

  • 递归中，系统栈自动记录 “未处理完的根节点”：当左子树处理完毕，栈顶的根节点会被弹出并访问，再处理右子树。
  • 非递归中，自定义栈显式模拟这一过程：通过 “压左链、弹根、处理右” 的循环，完全复刻了递归的逻辑，只是把 “隐式的系统栈” 变成了 “显式的自定义栈”。

这种 “栈结构” 的使用，本质是利用了栈 “先进后出” 的特性，确保 “左子树处理完后，能准确回溯到根节点，再处理右子树”，完美契合中序遍历 “左 - 根 - 右” 的顺序要求。

可以说，理解了栈在中序遍历中的角色，就理解了递归的本质 ——递归的简洁写法背后，是系统栈在隐式地完成 “压栈、弹栈、回溯” 的操作；它和你手动用栈模拟的逻辑完全等价，只是语法上更友好。，背后的执行逻辑完全可以通过显式栈来实现。