欢迎来到树状结构的世界！
在本章中，我们将探索树状算法 (Tree Algorithms)。虽然听到“树”可能会让你想起公园里的绿色植物，但在计算机科学中，它们是组织数据最强大的工具之一。无论是在电脑中搜索文件，还是在电子字典中查找单词，背后往往都有树状算法在运作！阅读完这份笔记后，你将能理解这些结构的运作原理，并像专业人士一样轻松地“遍历”它们。
1. 什么是树 (Tree)？
在深入研究算法之前，我们先快速复习一下什么是树。树 (Tree) 是一种看起来像倒过来的真实树木的数据结构。它从一个单一点开始，然后向外分支出去。
必须记住的关键术语：
节点 (Node)： 树中的单个元素（通常包含数据，如数字或名称）。
根节点 (Root)： 树的最顶端节点。每棵树都恰好有一个根节点。
边 (Edge)： 连接节点之间的线或链接。
父节点 (Parent)： 拥有指向其下方节点链接的节点。
子节点 (Child)： 拥有来自上方节点链接的节点。
叶节点 (Leaf)： 没有任何子节点的节点（树枝的“尽头”）。
快速回顾： 除了根节点外，每个节点都恰好有一个父节点，但一个父节点可以拥有多个子节点！
2. 二叉搜索树 (Binary Search Tree, BST)
二叉树 (Binary Tree) 是一种特殊的树，其中每个节点最多只能有两个子节点（通常称为左子节点和右子节点）。
二叉搜索树 (BST) 增加了一条非常重要的规则，帮助我们快速找到数据：
1. 比父节点小的数据放在左边。
2. 比父节点大的数据放在右边。
为什么这很有用？
由于这个“左小右大”的规则，搜索数值的速度会变得非常快。我们不必像查看列表那样逐一检查每个项目，而是每次向下移动一层时，都能排除掉一半的树。平衡二叉搜索树的搜索时间效率通常为 \( O(\log n) \)。
重点总结： BST 是为速度而设计的。它将漫长的搜索过程转化为一系列简单的“左还是右？”的决策。
3. 树的遍历算法 (Tree Traversal Algorithms)
遍历 (Traversal) 是指以特定顺序访问树中每个节点的专业术语。在 Oxford AQA 9645 的课程大纲中，你需要掌握三种“深度优先 (Depth-First)”的方法。别担心名称听起来很像，我们有个小窍门能帮你记住它们！
方法一：前序遍历 (Pre-order Traversal)
在前序遍历中，我们在访问子节点之前先访问根节点。
顺序：根节点 \(\rightarrow\) 左节点 \(\rightarrow\) 右节点
用途： 复制一棵树，或显示目录结构。
方法二：中序遍历 (In-order Traversal)
在中序遍历中，我们在左子节点和右子节点之间访问根节点。
顺序：左节点 \(\rightarrow\) 根节点 \(\rightarrow\) 右节点
神奇的事实： 如果你对二叉搜索树执行中序遍历，你将会以完美的数值或字母顺序访问所有节点！
方法三：后序遍历 (Post-order Traversal)
在后序遍历中，我们在访问完所有子节点之后才访问根节点。
顺序：左节点 \(\rightarrow\) 右节点 \(\rightarrow\) 根节点
用途： 删除树（你必须先删除子节点才能删除父节点）或计算数学表达式树。
记忆技巧 - “根节点规则”：
- Pre 代表“之前” \(\rightarrow\) 根节点在最前 (First)。
- In 代表“中间” \(\rightarrow\) 根节点在中间 (Middle)。
- Post 代表“之后” \(\rightarrow\) 根节点在最后 (Last)。
4. 遍历的“点点技巧”(The Dot Trick)
如果在考试中需要追踪遍历过程，请使用这个“秘密方法”。它绝对管用！
第一步： 在树的每个节点上画一个小点。
- 若为前序遍历，把点画在节点的左侧。
- 若为中序遍历，把点画在节点的底部。
- 若为后序遍历，把点画在节点的右侧。
第二步： 想象一支笔从根节点的左侧开始，画出一条持续不断的线，沿着树的外缘“环绕”（就像一个人绕着树边走一样）。
第三步： 每当你的线经过一个点，就写下该节点的值。写下来的顺序就是你的答案！
快速回顾： 这种物理上的“描边”方法是最安全的方式，能确保你不会遗漏节点或搞混顺序。
5. 在 BST 中加入新节点
要将新数据加入二叉搜索树，我们遵循与搜索相同的逻辑。我们从根节点开始，将新值与当前节点进行比较。
逐步流程：
1. 树是空的吗？如果是，新值将成为根节点。
2. 如果不是，将新值与当前节点比较。
3. 比当前节点小吗？移动到左子节点。
4. 比当前节点大吗？移动到右子节点。
5. 重复此过程，直到到达一个空的点（“边”）。
6. 将你的新节点放在那里。
常见错误： 学生有时会试图在加入节点时“重新排列”树。千万别这么做！新节点永远是作为分支末端的一个新的“叶节点”被加入的。
总结：考试关键重点
结构： 树由节点和边组成。顶端是根节点；末端是叶节点。
BST 规则： 左子节点 \( < \) 父节点；右子节点 \( > \) 父节点。
遍历：
- 前序 (Pre-order)： 根、左、右（用于复制）
- 中序 (In-order)： 左、根、右（用于排序）
- 后序 (Post-order)： 左、右、根（用于删除）
效率： 在平衡的情况下，搜索 BST 的效率远高于线性搜索，其复杂度为 \( O(\log n) \)。
如果一开始觉得遍历有点混乱，别担心！试着画一个有 3 个节点（数字 10、5 和 15）的小树，练习一下“点点技巧”。只要练习两次，这就会变成你的直觉！