📚 Tree Revision Guide | 树考点精讲
Trees are one of the most fundamental non‑linear data structures in computer science, appearing everywhere from file systems to network routing algorithms. Understanding how trees are represented and manipulated is essential for both IB and AQA Computer Science examinations. This revision guide breaks down key concepts such as binary trees, search trees, traversals, and heaps, using clear examples and precise terminology.
树是计算机科学中最基础的非线性数据结构之一，从文件系统到网络路由算法几乎无处不在。理解树的表示与操作对于 IB 和 AQA 计算机科学考试至关重要。本考点精讲通过清晰的示例和准确的术语，逐一拆解二叉树、搜索树、遍历以及堆等核心概念。
1. What is a Tree? | 树是什么？
A tree is a hierarchical data structure consisting of nodes connected by edges. Each tree has exactly one root node, and every other node is connected by a directed path from the root. Trees contain no cycles, meaning there is exactly one unique path between any two nodes.
树是一种由节点和边组成的层次化数据结构。每棵树仅有一个根节点，其余节点都通过从根出发的有向路径相连。树中不含环路，即任意两个节点之间有且仅有一条路径。
In IB and AQA syllabi, trees model hierarchical relationships such as folder structures, organisational charts, and expression syntax. The recursive nature of trees makes them well‑suited for algorithms that break problems into smaller sub‑problems.
在 IB 与 AQA 考纲中，树常用于模拟层次关系，如文件夹结构、组织架构图和表达式语法。树的递归特性使其特别适合将问题分解为更小子问题的算法。
2. Basic Terminology | 基本术语
Node: An element that holds data and links to child nodes. The root is the topmost node without a parent. Leaves are nodes with no children. The depth of a node is the number of edges from the root to that node. The height of a tree is the maximum depth of any leaf.
节点：存储数据并链接到子节点的元素。根节点是没有父节点的最顶层节点。叶节点是没有子节点的节点。节点的深度是从根到该节点的边数。树的高度是所有叶节点的最大深度。
- Parent and child: A node directly connected to another node closer to the root is the parent; the connected node is the child. / 父节点与子节点：直接连接到距根更近节点的节点称为父节点，被连接的节点为子节点。
- Sibling: Nodes sharing the same parent. / 兄弟节点：共享同一父节点的节点。
- Subtree: A node and all its descendants form a subtree. / 子树：一个节点及其所有后代构成一棵子树。
- Degree: The number of children a node has. In a binary tree, degree ≤ 2. / 度：节点拥有的子节点数量。二叉树中度 ≤ 2。
3. Binary Trees | 二叉树
A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child. It is the foundation for binary search trees, expression trees, and heaps. A full binary tree has every node with either 0 or 2 children; a complete binary tree is filled at all levels except possibly the last, which is filled from left to right.
二叉树是每个节点最多有两个子节点的树，这两个子节点分别称为左孩子和右孩子。它是二叉搜索树、表达式树和堆的基础。满二叉树每个节点的子节点数为 0 或 2；完全二叉树除最后一层外所有层均填满，并且最后一层的节点从左向右填充。
Representation of a binary tree can be done using nodes with left and right pointers, or using an array (especially for complete binary trees). For an array representation, the root is at index 1 (or 0), left child of node at i is at 2i, right child at 2i+1.
二叉树的表示可以用包含左右指针的节点来实现，也可以使用数组（尤其适用于完全二叉树）。在数组表示中，根节点位于索引 1（或 0），节点 i 的左孩子在 2i 处，右孩子在 2i+1 处。
4. Binary Search Trees (BST) | 二叉搜索树
A binary search tree is a binary tree with the ordering property: for any given node, all values in its left subtree are smaller (or equal), and all values in its right subtree are greater. This property enables efficient searching, insertion, and deletion operations—average time complexity O(log n) for balanced trees.
二叉搜索树是对节点值具有排序性质的二叉树：对于任意节点，其左子树中的所有值都较小（或相等），右子树中的所有值都较大。这一性质使得查找、插入和删除操作高效——平衡树的平均时间复杂度为 O(log n)。
When a BST becomes unbalanced (degenerates into a linked list), operations can degrade to O(n). Self‑balancing BSTs such as AVL trees and Red‑Black trees maintain O(log n) performance, but AQA and IB often test the unbalanced BST behaviour using manual insertion sequences.
当二叉搜索树变得不平衡（退化为链表）时，操作可能降到 O(n)。自平衡二叉搜索树（如 AVL 树和红黑树）能够保持 O(log n) 性能，但 AQA 和 IB 通常通过手动插入序列来考查不平衡 BST 的行为。
5. Tree Traversals | 树的遍历
Tree traversal refers to the process of visiting every node in a systematic order. There are four main traversal methods tested in IB and AQA: pre‑order, in‑order, post‑order, and level‑order (breadth‑first). Understanding the output sequence for a given tree is a classic exam question.
树的遍历是指以某种系统化的顺序访问树中的每一个节点。IB 和 AQA 主要考察四种遍历方法：前序、中序、后序和层序（广度优先）。能够给出给定树的遍历输出序列是经典的考题。
Pre-order: root → left → right | 前序：根 → 左 → 右
In-order: left → root → right | 中序：左 → 根 → 右
Post-order: left → right → root | 后序：左 → 右 → 根
Level-order: visit nodes top‑down, left to right | 层序：从上到下、从左到右访问节点
| Traversal | Order | Typical Use |
|---|---|---|
| Pre‑order | Root, Left, Right | Copying a tree; prefix expression |
| In‑order | Left, Root, Right | Retrieving sorted data from BST |
| Post‑order | Left, Right, Root | Deleting nodes; postfix expression |
| Level‑order | Breadth‑first | Serialisation; shortest‑path on unweighted trees |
The table above summarises traversal orders and typical applications. In‑order traversal of a binary search tree produces the nodes in ascending order, a property frequently examined. / 上表总结了遍历顺序及典型应用。对二叉搜索树进行中序遍历可以按升序输出节点，这是一个常考的性质。
6. BST Operations: Search, Insert, Delete | 二叉搜索树操作：查找、插入、删除
Search: Start at the root. If the target equals the current node’s value, return found. If the target is smaller, go left; if larger, go right. Repeat until found or a null child is reached.
查找：从根开始。若目标值等于当前节点的值，则返回找到。若目标值较小，向左子树递归；若较大，向右子树递归。重复直到找到或到达空孩子为止。
Insertion: Follow the search path; when a null child is found, insert the new node there, preserving the BST property.
插入：遵循查找路径，当发现一个空孩子时，在该位置插入新节点，同时保持 BST 性质。
Deletion has three cases: (1) Leaf node — simply remove it. (2) Node with one child — replace the node with its child. (3) Node with two children — find the in‑order successor (smallest in right subtree), copy its value to the node, then delete the successor. This maintains BST ordering.
删除有三种情况：(1) 叶子节点——直接删除。(2) 只有一个子节点——用其子节点替换该节点。(3) 有两个子节点——找到中序后继（右子树中的最小节点），将其值复制到待删节点，然后删除那个后继节点。这样可以维持 BST 排序性质。
Time complexity of BST operations: O(log n) average, O(n) worst case | BST 操作时间复杂度：平均 O(log n)，最坏 O(n)
7. Heaps | 堆
A heap is a specialised complete binary tree that satisfies the heap property. In a max‑heap, the value of each node is greater than or equal to the values of its children; in a min‑heap, each node is less than or equal to its children. Heaps are typically implemented using arrays for efficient access.
堆是一种满足堆性质的特化完全二叉树。在最大堆中，每个节点的值都大于或等于其孩子的值；在最小堆中，每个节点的值都小于或等于其孩子的值。堆通常用数组实现以支持高效访问。
The root of a max‑heap holds the maximum element; the root of a min‑heap holds the minimum. Heap operations include insertion (percolate up), deletion of the root (percolate down), and heapify (building a heap from an unordered array). These operations run in O(log n) time.
最大堆的根存放着最大元素；最小堆的根存放着最小元素。堆操作包括插入（向上渗透）、删除根节点（向下渗透）以及建堆（从一个无序数组构建堆）。这些操作的时间复杂度为 O(log n)。
Heaps are essential for implementing priority queues and the heap sort algorithm. AQA and IB syllabi expect students to manually perform up‑heap and down‑heap on small arrays, and to represent a heap as an array.
堆是实现优先队列和堆排序算法的关键。AQA 与 IB 考纲要求学生能够手动对小规模数组进行向上渗透和向下渗透，并能够以数组形式表示堆。
8. Expression Trees and Other Applications | 表达式树及其他应用
An expression tree is a binary tree used to represent arithmetic or logical expressions. Leaves contain operands (numbers or variables), and internal nodes contain operators. Traversing the tree in different orders yields prefix, infix, and postfix notations.
表达式树是一种用于表示算术或逻辑表达式的二叉树。叶节点存放操作数（数字或变量），内部节点存放运算符。以不同顺序遍历该树可得到前缀、中缀和后缀表示法。
Other tree applications include: decision trees in machine learning, file system directories, DOM (Document Object Model) for web pages, and syntax trees in compilers. In networks, spanning trees ensure loop‑free paths.
树的其他应用包括：机器学习中的决策树、文件系统目录、网页的 DOM（文档对象模型）以及编译器中的语法树。在网络领域，生成树确保了无环路径。
9. Exam‑style Questions and Tips | 考点例题与技巧
Typical IB and AQA questions on trees require you to: draw a BST after insertions and deletions; state the output of a given traversal; identify whether a tree is a valid BST or heap; perform heap insertions; and explain the advantages of balanced trees. Marks are often awarded for showing intermediary steps.
典型的 IB 与 AQA 树型考题包括：根据插入与删除操作画出 BST；给出特定遍历的输出；判断一棵树是否为合法的 BST 或堆；执行堆插入；解释平衡树的优势。阅卷时会根据中间步骤给分。
- Draw clearly: Use consistent shapes; label left/right children. / 绘图清晰：使用统一形状，标注左/右孩子。
- Traversal mnemonic: Remember “pre” means visiting the node before children, “post” after children. / 遍历助记：记住“前序”表示在孩子之前访问节点，“后序”在孩子之后。
- BST deletion with two children: Always replace with the in‑order successor (next largest) to preserve structure; the exam often asks for the resulting tree after one such deletion. / 删除双子节点：总是用中序后继（下一个较大值）替代以维持结构；考试常要求画出这样的删除结果。
- Heap array representation: Children of index i are at 2i+1 and 2i+2 (if using 0‑based array). Practise percolation steps for insert and delete. / 堆的数组表示：节点索引 i 的孩子在 2i+1 和 2i+2（若采用基于0的数组）。练习插入和删除的渗透步骤。
10. Summary | 小结
Trees provide an elegant way to organise hierarchical data. Mastery of binary trees, BSTs, tree traversals, and heaps is indispensable for scoring well in IB and AQA Computer Science. Remember the recursive structure: almost every tree algorithm can be expressed in terms of operations on the root, left subtree, and right subtree. Consistent practice with drawing trees step by step will build the speed and accuracy needed in the exam.
树为组织层次化数据提供了一种优雅的方式。掌握二叉树、二叉搜索树、树的遍历和堆对于在 IB 与 AQA 计算机科学中取得高分至关重要。记住递归结构：几乎所有树算法都可以通过根、左子树和右子树的操作来描述。坚持逐步画树的练习，能够建立起考试所需的速度与准确性。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导