📚 Trees Revision for A-Level CCEA Computer Science | A-Level CCEA 计算机：树 考点精讲
Trees are one of the most versatile non‑linear data structures in the CCEA A‑Level specification. They model hierarchical relationships efficiently and underpin many searching, sorting, and parsing algorithms. This guide unpacks all core tree concepts you need to master, from terminology and binary trees to BST operations and traversal techniques.
树是 CCEA A‑Level 考试大纲中用途最广泛的非线性数据结构之一。它能高效地模拟层次关系，并支撑着许多搜索、排序和解析算法。本指南将为你梳理所有必须掌握的核心树概念，从术语、二叉树到二叉搜索树操作与遍历技巧。
1. Introduction to Tree Data Structures | 树数据结构简介
A tree is a collection of nodes connected by edges, where each node holds a data item and references to its child nodes. Unlike arrays or lists, a tree does not store data in a linear sequence; instead it organises items in a branching hierarchy with a single root at the top. The root has no parent, every other node has exactly one parent, and leaf nodes have no children. Trees provide a natural way to represent parent‑child relationships, making them ideal for file systems, organisational charts, and expression parsing.
树是由边连接的一组节点，每个节点包含一个数据项和指向其子节点的引用。与数组或列表不同，树不是按线性顺序存储数据，而是以分支层次结构组织数据，最顶层有一个根节点。根节点没有父节点，其他每个节点都有一个父节点，叶节点没有子节点。树提供了表达父子关系的自然方式，非常适合表示文件系统、组织结构图和表达式解析。
2. Tree Terminology | 树的基本术语
Mastering the precise vocabulary is essential for both written answers and algorithm design. Root – the topmost node with no incoming edges. Edge – a connection between two nodes. Parent – a node that has one or more subtrees beneath it. Child – a node directly connected below another node. Sibling – nodes that share the same parent. Leaf (or external node) – a node with no children. Internal node – a node that has at least one child. Subtree – a node together with all its descendants. Depth of a node – the number of edges from the root to that node (root has depth 0). Height of a node – the number of edges on the longest downward path to a leaf; the height of the tree is the height of the root. Degree of a node – the number of children it possesses; the degree of a tree is the maximum degree over all its nodes. For a binary tree, degree is at most 2.
掌握准确的术语对书面答题和算法设计至关重要。根节点（Root）——最顶层没有入边的节点。边（Edge）——两个节点之间的连接。父节点（Parent）——其下拥有一个或多个子树的节点。子节点（Child）——直接连接在另一个节点下方的节点。兄弟节点（Sibling）——具有相同父节点的节点。叶节点（Leaf）（又称外部节点）——没有子节点的节点。内部节点（Internal node）——至少拥有一个子节点的节点。子树（Subtree）——一个节点与其所有后代组成的结构。节点的深度（Depth）——从根到该节点的边数（根的深度为 0）。节点的高度（Height）——从该节点到某个叶节点的最长下行路径上的边数；树的高度即根的高度。节点的度（Degree）——该节点拥有的子节点数；树的度是所有节点中最大的度。对于二叉树，度最大为 2。
3. Binary Trees | 二叉树
A binary tree is a tree in which every node has at most two children, conventionally referred to as the left child and the right child. A binary tree can be empty. The shape can be strictly binary (every node has 0 or 2 children) or complete (all levels are completely filled except possibly the last, which is filled from left to right). In a full binary tree, every level is fully populated; a full binary tree of height h contains exactly 2ʰ⁺¹ – 1 nodes. CCEA questions may ask you to state the maximum number of nodes at level k (2ᵏ) or to distinguish between a binary tree and a binary search tree.
二叉树是指每个节点最多有两个子节点的树，子节点通常称为左孩子和右孩子。二叉树可以为空。其形态可以是严格二叉树（每个节点有 0 个或 2 个子节点），也可以是完全二叉树（除最后一层外所有层均填满，且最后一层从左到右填充）。满二叉树每一层都完全填满；高度为 h 的满二叉树恰好包含 2ʰ⁺¹ – 1 个节点。CCEA 可能要求你给出第 k 层的最大节点数（2ᵏ），或区分二叉树与二叉搜索树。
4. Binary Search Trees (BSTs) | 二叉搜索树
A binary search tree is a binary tree with an ordering property: for every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater than the node’s value. Duplicates are normally prohibited or placed to one side consistently. This invariant allows extremely efficient search, insertion, and deletion operations—O(log n) on average for a balanced tree, degrading to O(n) if the tree becomes linear. CCEA candidates must be able to construct a BST from a given sequence of numbers, draw the resulting structure, and trace BST algorithms.
二叉搜索树是一种具有排序性质的二叉树：对任意节点，其左子树中所有值均小于该节点的值，右子树中所有值均大于该节点的值。通常不允许重复值，或始终将相同值放在同一侧。这一不变性质使得高效的搜索、插入和删除操作成为可能——平衡树的平均时间复杂度为 O(log n)，若树退化为线性结构则降至 O(n)。CCEA 考生须能从给定数字序列构造 BST，画出结果结构，并追踪 BST 算法。
5. Tree Traversals | 树的遍历
Traversal is the process of visiting every node in a tree exactly once. Three depth‑first methods are tested: pre‑order (visit node, then left subtree, then right subtree), in‑order (left subtree, node, right subtree) and post‑order (left subtree, right subtree, node). In a BST, in‑order traversal visits nodes in ascending order. You may be asked to list the order of nodes for a given tree or to reconstruct a tree from two traversal sequences. Practice drawing the recursive call stack to avoid mistakes.
遍历是指恰好访问树中每个节点一次的过程。考试涉及三种深度优先遍历方法：前序遍历（pre‑order）：访问节点，再遍历左子树，最后遍历右子树；中序遍历（in‑order）：遍历左子树，访问节点，遍历右子树；后序遍历（post‑order）：遍历左子树，遍历右子树，访问节点。在二叉搜索树中，中序遍历将按升序访问节点。考题可能要求列出给定树的节点访问顺序，或根据两个遍历序列重建树结构。建议练习画出递归调用栈以避免失误。
| Traversal | 遍历 | Order | 顺序 | Example for root A, left B, right C | 示例（根 A，左 B，右 C） |
|---|---|---|
| Pre‑order | 前序 | Node, Left, Right | 根，左，右 | A, B, C |
| In‑order | 中序 | Left, Node, Right | 左，根，右 | B, A, C |
| Post‑order | 后序 | Left, Right, Node | 左，右，根 | B, C, A |
6. BST Search Algorithm | 二叉搜索树查找算法
Searching for a key in a BST follows the ordering property. Begin at the root. If the tree is empty, the search fails. Compare the target value with the current node: if equal, the search succeeds; if smaller, move to the left child; if larger, move to the right child. Repeat until the value is found or a null branch is reached. The algorithm can be expressed recursively or iteratively. In pseudocode:
在二叉搜索树中查找一个键遵循排序性质。从根开始。若树为空，查找失败。比较目标值与当前节点：若相等则查找成功；若目标值较小则移至左孩子；若较大则移至右孩子。重复此过程直到找到值或遇到空分支。算法可用递归或迭代方式表达。伪代码如下：
function search(node, target)
if node is null then return false
if target = node.value then return true
else if target < node.value then return search(node.left, target)
else return search(node.right, target)
7. BST Insertion and Deletion | 二叉搜索树的插入与删除
Insertion mimics the search: walk down the tree following the BST property until a null child is found, then attach the new node there. If duplicates are allowed, a consistent policy (e.g., always place duplicates in the right subtree) must be adopted. Deletion has three cases. (1) The node is a leaf – simply remove it. (2) The node has one child – remove the node and link its parent directly to its child. (3) The node has two children – replace the node with its in‑order successor (the smallest node in its right subtree), then delete that successor using case (1) or (2). The in‑order successor guarantees that the BST property is maintained. These algorithms are often examined by asking you to show the tree after a sequence of add and remove operations.
插入操作模仿查找过程：按照 BST 性质向下移动，直到找到一个空子节点位置，再将新节点挂载在那里。若允许重复值，必须采用一致的策略（例如始终将重复值放入右子树）。删除有三种情况。(1) 节点为叶节点——直接删除。(2) 节点只有一个孩子——删除该节点并将父节点直接连接到其孩子。(3) 节点有两个孩子——用其中序后继节点（即右子树中的最小节点）替换该节点，然后按情况(1)或(2)删除该后继节点。中序后继保证了 BST 性质得以维护。考题经常要求你展示经过一系列添加和删除操作后树的结构变化。
8. Array and Linked Representations of Trees | 树的数组与链表表示
Two common implementations are tested. The linked representation uses node records containing a data field and two pointers (left and right). This is memory‑efficient for sparse or unbalanced trees and allows dynamic resizing. The array representation works well for complete binary trees. The root is stored at index 0 (or 1, depending on convention). For a node at index i: left child is at 2i+1 (or 2i), right child at 2i+2 (or 2i+1), and parent at floor((i‑1)/2). This scheme wastes space if the tree is skewed, but supports efficient random access. You must be able to convert between the two representations and discuss their trade‑offs in terms of memory and performance.
考试涉及两种常见实现方式。链式表示使用包含数据字段和两个指针（左、右）的节点记录。这对于稀疏或非平衡树来说内存效率更高，且允许动态调整大小。数组表示适用于完全二叉树。根存储在下标 0（或 1，依惯例而定）。对于下标为 i 的节点：左孩子在 2i+1（或 2i），右孩子在 2i+2（或 2i+1），父节点在 floor((i‑1)/2)。若树倾斜，这种方案会浪费空间，但支持高效的随机访问。你必须能在两种表示之间转换，并讨论它们在内存和性能方面的权衡。
9. Applications of Trees | 树的应用
Trees are everywhere in computing. Expression trees represent arithmetic expressions, where leaves are operands and internal nodes are operators; post‑order traversal yields the reverse Polish notation. Binary heaps (a complete binary tree used for priority queues) enable O(log n) insertion and removal of the extreme element. File systems model directories and files as a tree. Trie structures support fast string prefix searches. Binary search trees form the basis of many database indexing methods. Understanding these real‑world links will strengthen your design‑oriented answers and help you recognise when a tree is the appropriate abstract data type.
树在计算领域无处不在。表达式树用于表示算术表达式，其中叶节点为操作数，内部节点为运算符；后序遍历可得到逆波兰表示法。二叉堆（一种用于优先队列的完全二叉树）能够以 O(log n) 时间插入和删除极值元素。文件系统将目录和文件建模为树。字典树（Trie）支持快速的字符串前缀搜索。二叉搜索树是许多数据库索引方法的基础。理解这些现实联系将增强你在设计类题目中的作答能力，并帮助你识别何时应将树选作合适的抽象数据类型。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导