欢迎来到树状结构的世界！

你好！今天我们要深入探讨计算机科学中，最重要且优雅的数据组织方式之一：树 (Trees)。虽然你之前已经接触过数组 (arrays) 和栈 (stacks) 这类线性结构，但树是层次化 (hierarchical) 的。这意味着它们非常适合呈现事物之间的从属关系，例如电脑里的文件夹或族谱。

如果刚开始觉得这些概念有点抽象，别担心！我们会一步步拆解，并透过大量生动的比喻，帮助你拓展知识的枝叶！


1. 到底什么是树？

在 AQA 课程大纲中，树有非常具体的数学定义。它是一个连通、无向且无环的图 (connected, undirected graph with no cycles)。

让我们把这些专业术语转化成简单的说法：

  • 连通 (Connected)： 你可以通过线条从树的任何一部分到达另一部分，没有任何“漂浮”在外的节点。
  • 无向 (Undirected)： 线条（边）没有箭头，不指定单一方向。
  • 无环 (No Cycles)： 这点最重要！意即图中没有回路。你不能从一点出发，沿着路径走，在不回头的情况下又回到起点。

你知道吗？ 在数学上，树其实不需要有“起点”或根节点。但在计算机科学中，我们几乎总是处理有根树 (Rooted Trees)。

有根树的关键术语

当我们选定一个节点作为“起点”时，称之为根节点 (Root)。一旦有了根节点，其他所有节点都会成为它的后代 (descendant)。这就建立了父子关系 (parent-child relationship)：

  • 节点 (Node)： 单一的数据元素（也就是那些“圆圈”）。
  • 边 (Edge)： 连接两个节点的线。
  • 根节点 (Root)： 唯一没有父节点的节点，是位居顶端的“大佬”。
  • 父节点 (Parent)： 拥有指向下方节点的边的节点。
  • 子节点 (Child)： 由上方节点连接而来的节点。
  • 叶节点 (Leaf)： 没有任何子节点的节点。它们是树的“末端”。

重点总结： 树就是一种连通且无环的图。在计算机科学中，我们通常指定一个节点为“根节点”来构建层次结构。


2. 二叉树 (Binary Tree)

二叉树 (Binary Tree) 是一种特殊的有根树，在考试中会经常出现。规则很简单：每个节点最多只能有两个子节点。

把它想象成一个家庭，每个人最多只能生两个小孩。我们通常称之为“左子节点 (Left Child)”和“右子节点 (Right Child)”。

二叉搜索树 (Binary Search Tree, BST)

二叉树最常见的应用是二叉搜索树 (BST)。这是一种为了让数据搜索变得极快而特别设计的结构，每个节点都遵循严格的规则：

  • 比父节点小的值放在左边。
  • 比父节点大的值放在右边。

记忆小撇步： “左小右大”。如果数字比较小，就往左转！

快速回顾：二叉搜索树的效率

由于你在向下移动每一层时，基本上都将剩余的节点数量减半，因此搜索平衡二叉树的效率非常高。在大 O 符号 (Big O Notation) 中，搜索二叉树的时间复杂度为 \(O(\log n)\)。


3. 树的遍历 (Tree Traversals)

有时我们需要访问树中的每一个节点（例如将它们打印出来或进行复制）。这称为遍历 (traversing)。因为树不是直线的，我们有三种主要方法，这取决于何时访问根节点。

1. 前序遍历 (Pre-Order Traversal)

顺序： 根节点 \(\rightarrow\) 左子树 \(\rightarrow\) 右子树
运作方式： 先访问根节点，接着遍历整个左子树，最后遍历整个右子树。
典型用途： 用于复制树结构。如果你想重制这棵树，首先必须知道根节点在哪里！

2. 中序遍历 (In-Order Traversal)

顺序： 左子树 \(\rightarrow\) 根节点 \(\rightarrow\) 右子树
运作方式： 先遍历左子树，访问根节点，最后遍历右子树。
典型用途： 如果对二叉搜索树进行中序遍历，输出的内容会是升序排列（例如 1, 2, 3...）。

3. 后序遍历 (Post-Order Traversal)

顺序： 左子树 \(\rightarrow\) 右子树 \(\rightarrow\) 根节点
运作方式： 先访问所有子节点，最后才访问根节点。
典型用途： 用于删除树（在删除子节点之前，你无法删除父节点！）或将算式转换为逆波兰表示法 (Reverse Polish Notation, RPN)。

如果觉得这部分很难，别担心！ 考试时有一个简单的“轮廓技巧”。想像在树的外围画一条紧密的线（轮廓），从根节点的左侧开始。如果你在每个节点的左侧标记一个点，按顺序连接起来就是前序遍历 (Pre-Order)；标记在下方是中序遍历 (In-Order)；标记在右侧则是后序遍历 (Post-Order)。

重点总结： 遍历只是穿过树的不同“路径”。前序用于复制，中序用于排序，后序则用于 RPN 或清空树。


4. 关键概念总结

在继续往下学习之前，请确保你已经掌握这些“必备知识点”：

  • 树的定义： 连通、无向且无环的图。
  • 有根树： 拥有一个核心（根节点）的树。
  • 二叉树： 每个节点最多只有 2 个子节点的树。
  • 搜索复杂度： 搜索二叉树通常为 \(O(\log n)\)。
  • 遍历顺序： 记住这些顺序！
    • 前序 (Pre-Order)：根、左、右
    • 中序 (In-Order)：左、根、右
    • 后序 (Post-Order)：左、右、根

避免常见错误： 不要假设每一棵树都是二叉树！一般的树在每个节点上可以有任意数量的子节点，只有“二叉”树才限制为两个。

做得好！你刚刚已经掌握了数据结构中“树”的基础。继续练习画出这些遍历路径，你很快就会成为高手！