欢迎来到树状遍历（Tree Traversals）！
在本章中，我们将探索计算机是如何在「树」这种数据结构中进行「行走」的。试想一下家谱或是计算机中的文件系统，这些都是树！为了对它们进行任何实用的操作——比如搜索文件或打印清单——计算机需要一种系统化的方法来走访每一个节点（node），且确保不会迷路。
如果刚开始觉得有点抽象，别担心。一旦你掌握了这些「隐藏路径」的技巧，你很快就能对这些算法了如指掌，甚至连做梦都会走！
先备知识检查：什么是树？
在开始走路前，我们得先知道自己身在何处。在计算机科学中，树（Tree）是由节点（nodes）与连接它们的边（edges）所组成的集合。
• 根节点（Root）：最顶端的节点（也就是「老大」）。
• 节点（Nodes）：包含数据的圆圈。
• 子节点（Children）：从父节点延伸出来的节点。
• 二叉树（Binary Tree）：这是一种特殊的树，每个节点最多只能有两个子节点（通常称为左子节点和右子节点）。
三种遍历方法
「遍历（Traversal）」这个词听起来很专业，其实就是指走访树中每一个节点的意思。针对 AQA 课程大纲，你需要掌握三种具体的遍历方式。这些方法的名称正正告诉了你，在树的任何一个子区域中，该在何时走访根节点（Root）。
1. 前序遍历（Pre-Order Traversal）
在前序遍历中，你会再子节点之前（BEFORE）走访根节点。
顺序是：根节点 → 左子节点 → 右子节点。
记忆小撇步：「Pre」即「之前」。根节点总是排在分支之前。
步骤解析：
1. 走访根节点。
2. 遍历左子树。
3. 遍历右子树。
实际应用：复制树状结构
如果你想复制一棵树，就得用前序遍历。你必须先建立父节点，然后才能将子节点连接上去！
2. 中序遍历（In-Order Traversal）
在中序遍历中，根节点是在左子节点和右子节点之间（IN BETWEEN）被走访的。
顺序是：左子节点 → 根节点 → 右子节点。
记忆小撇步：「In-order」会产生「In-creasing」（递增）的顺序，这对于二叉搜索树（BST）非常实用！
步骤解析：
1. 遍历左子树。
2. 走访根节点。
3. 遍历右子树。
实际应用：排序
如果你有一棵二叉搜索树（BST），执行中序遍历会输出递增顺序的数据（例如：1, 2, 3... 或 A, B, C...）。
3. 后序遍历（Post-Order Traversal）
在后序遍历中，你是在子节点之后（AFTER）才走访根节点。
顺序是：左子节点 → 右子节点 → 根节点。
记忆小撇步：「Post」即「之后」。根节点是你最后才走访的节点。
步骤解析：
1. 遍历左子树。
2. 遍历右子树。
3. 走访根节点。
实际应用：删除树与数学运算
• 清空树：你必须先删除子节点，才能删除父节点（否则子节点会变成内存中的「孤儿」！）。
• 逆波兰表示法（RPN）：后序遍历可用于将标准数学算式转换成计算机能轻易通过堆栈（stack）计算的格式。
「轮廓法」技巧：如何追踪任何树
如果在考试中看到树，别慌！使用轮廓法（Outline Method）几秒钟就能找到答案。想象你画出一条连续的线，紧贴着树的外围，从根节点的左侧开始，绕着树的形状走一圈。
取得序列的方法：
• 前序（Pre-order）：当你经过节点的左侧时，记下该节点的值。
• 中序（In-order）：当你经过节点的底部时，记下该节点的值。
• 后序（Post-order）：当你经过节点的右侧时，记下该节点的值。
快速复习：左边 = 前序，底部 = 中序，右边 = 后序。
用途总结（课程大纲要求）
你知道吗？不同的遍历方式不仅仅是为了好玩，它们在软件工程中有非常明确的工作任务。以下是你考试时需要记住的重点：
前序（Pre-Order）：用于复制树状结构。
中序（In-Order）：用于以递增顺序输出 BST 的内容。
后序（Post-Order）：用于中缀转后缀（RPN）转换，产生后缀表达式，以及清空/删除树。
避免常见错误
• 搞混左边与右边：在所有三种遍历中，左边永远在右边之前。唯一会改变位置的是根节点。
• 起点错误：无论算法指示先去哪里，务必永远从根节点（最顶端）开始你的追踪。
• 忽略叶节点（Leaf Nodes）：必须走访每一个节点，即使是那些位于最底部且没有子节点的节点也要走访！
重点整理方块
前序（Pre-Order）：根-左-右（复制）
中序（In-Order）：左-根-右（排序/BST）
后序（Post-Order）：左-右-根（RPN/删除）
Big-O 复杂度：这三种遍历的时间复杂度皆为 \(O(n)\)，因为你必须精确地走访每一个节点一次。