数据结构--中序遍历

中序遍历（Inorder Traversal）是二叉树三种基本深度优先遍历方式之一（另外两种是前序、后序）。它的核心规则非常简单：

先遍历左子树 → 再访问根节点 → 最后遍历右子树
（简称：左 - 根 - 右）

---

🌳 通俗理解

想象你站在二叉树的根节点，要按顺序“拜访”所有节点：

1. 先一头扎进左子树，用同样的规则（左→根→右）遍历它；
2. 等左子树全部拜访完，才回到当前根节点并记录它；
3. 最后去拜访右子树，同样用（左→根→右）的规则。

这个过程天然具有递归性质——每个子树都是一个更小的二叉树，处理逻辑完全相同。

---

📌 关键特性

• 对二叉搜索树（BST）有特殊意义：
  中序遍历 BST 的结果一定是升序序列（因为 BST 性质：左子树 < 根 < 右子树）。
• 时间复杂度：O(n)（每个节点访问一次）
  空间复杂度：O(h)（h 为树高，递归栈或显式栈的深度）。

---

🌰 举例说明

A / \ B C / \ \ D E F

中序遍历步骤：

1. 从根A开始，先遍历左子树（以B为根）
   • 遍历B的左子树（D）→ 访问D
   • 访问B
   • 遍历B的右子树（E）→ 访问E
2. 访问根A
3. 遍历右子树（以C为根）
   • 访问C（C无左子树）
   • 遍历C的右子树（F）→ 访问F

结果：[D, B, E, A, C, F]

---

💡 为什么叫“中序”？

• “中”指根节点在遍历顺序的中间位置（左子树之后，右子树之前）。
• 对比其他遍历：
  • 前序：根 → 左 → 右（根在前）
  • 后序：左 → 右 → 根（根在后）

---

🛠 实现方式

方法 1：递归（最直观）

def inorderTraversal(root): if not root: return [] return (inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right))

方法 2：迭代（用栈模拟递归）

def inorderTraversal(root): result, stack, current = [], [], root while current or stack: # 一路向左，将路径节点入栈 while current: stack.append(current) current = current.left # 弹出栈顶（最左节点），访问它 current = stack.pop() result.append(current.val) # 转向右子树 current = current.right return result

---

✅ 总结

表格

遍历类型	顺序	应用场景
中序	左 →根→ 右	BST 升序输出、表达式树求值
前序	根→ 左 → 右	复制树、序列化
后序	左 → 右 →根	删除树、计算目录大小

中序遍历的本质是深度优先探索左分支，回溯时处理根，再探索右分支，这种“分治”思想是树算法的基础。