章节：树（Trees）
欢迎！在这个章节中，我们将一起探索树（Trees）。在计算机科学中，树并不是公园里那种长着叶子和树皮的植物，而是一种组织数据的方式，让我们能够极快地搜索、添加和删除信息。如果你曾经在电脑上使用“文件资源管理器”来查看文件夹，那你其实已经用过树状结构了！
如果一开始觉得这些概念有点抽象，别担心。我们会用简单的类比一步步拆解，确保你能够自信地掌握这些知识。
1. 什么是树？
从技术层面来说，树是一种非线性数据结构。与数组（Array）或列表（List，就像排成一列的人）不同，树会向不同的方向分支。
关键术语
要理解树，我们需要先学习描述它们的“家族”术语：
- 节点（Node）：树中的个别数据项目（就像家谱中的一个人）。
- 边（Edge）：连接两个节点的链接或线条。
- 根节点（Root）：树最顶端的节点。每一棵树都只有一个根节点。
- 父节点（Parent）：拥有连接到下方节点的边的节点。
- 子节点（Child）：从上方节点延伸出边所连接到的节点。
- 叶节点（Leaf）：没有子节点的节点（它位于分支的最末端）。
- 子树（Subtree）：树中的一个较小区段，其本身也是一棵树。
现实生活类比：想象一家公司的架构。执行长（CEO）是根节点。经理是员工的父节点，而员工则是子节点。处于最底层、不需要管理任何人的员工就是叶节点。
快速复习：
• 根节点是唯一没有父节点的节点。
• 叶节点是唯一没有子节点的节点。
• 边连接父节点与子节点。
2. 二叉树（Binary Trees）
二叉树是一种遵循简单规则的特殊树：每个节点最多只能有两个子节点。
想象一个人最多只有两个孩子。在二叉树中，我们通常将这两个孩子称为左子节点（Left Child）和右子节点（Right Child）。
你知道吗？二叉树的效率非常高。如果你拥有一棵包含 1,000 个项目且完全平衡的二叉树，你只需要大约 10 个步骤就能找到任何特定项目！
二叉搜索树（Binary Search Trees, BST）
二叉搜索树是一种二叉树，其中的数据以特定顺序排列，使搜索速度更快。其规则如下：
- 比父节点小的值放在左侧。
- 比父节点大的值放在右侧。
例子：如果根节点是 10，你想添加 5，它会放在左侧。如果你想添加 15，它会放在右侧。
关键重点：
BST 的黄金法则就是：左小右大（Left is Less, Right is More）。
3. 树的遍历（Tree Traversals）
遍历是一个专业术语，意指“访问树中的每一个节点一次”。根据我们访问节点的顺序不同，会得到不同的结果。你需要掌握三种主要类型：
1. 前序遍历（Pre-order Traversal）
在此方式中，我们依序访问根节点，然后是左子树，最后是右子树。
记忆法：Root（根）在Pre（前面），优先于其他所有项目。
2. 中序遍历（In-order Traversal）
我们依序访问左子树，然后是根节点，最后是右子树。
记忆法：Root（根）在In（中间）。
专业小贴士：如果你对一棵二叉搜索树执行中序遍历，输出的数字将会呈现完美的数值排序！
3. 后序遍历（Post-order Traversal）
我们依序访问左子树，然后是右子树，最后才是根节点。
记忆法：Root（根）在Post（后面），最后处理。
如何轻松完成（“外框”技巧）：
如果你有一棵树的图表，从根节点的左侧开始画一条连续的线，绕着树的外围绕一圈（就像用绳子把它包起来一样）。
• 前序遍历：当你经过节点的左侧时标记它。
• 中序遍历：当你经过节点的底部时标记它。
• 后序遍历：当你经过节点的右侧时标记它。
4. 在 BST 中添加与搜索
在二叉搜索树中搜索数值就像玩“猜大小”游戏一样。
逐步搜索：
- 从根节点开始。
- 你要找的值是否等于当前节点？如果是，那就找到了！
- 数值是否较小？前往左子节点并重复步骤 2。
- 数值是否较大？前往右子节点并重复步骤 2。
- 如果你到达了一个无法再往下移动的点（没有子节点），说明该数值不存在于树中。
常见错误：
学生常忘记在添加节点时，必须遵循搜索规则，直到找到一个空位（叶节点）。你不能随便放置！你必须在过程中将它与沿途的每个父节点进行比较。
快速复习方框：
搜索或添加：
1. 从根节点开始。
2. 进行比较。
3. 较小？往左走。
4. 较大？往右走。
5. 重复直到找到目标或到达空位。
总结检查清单
检查你的理解程度：
[ ] 我能定义根节点、父节点、子节点和叶节点吗？
[ ] 我知道二叉树的每个节点最多只能有 2 个子节点吗？
[ ] 我能记住搜索树的“左小右大”规则吗？
[ ] 我能执行中序、前序和后序遍历吗？
做得好！树是计算机科学的基础组成部分。一旦你掌握了“左 vs 右”的逻辑，你就已经攻克了最困难的部分。