📚 Trees in A-Level WJEC Computer Science | A-Level WJEC 计算机：树 考点精讲
Trees are one of the most versatile and commonly examined abstract data types (ADTs) in the WJEC A-Level Computer Science specification. A tree organises data in a hierarchical structure, with a single root node at the top, branching out to child nodes and eventually terminating at leaf nodes. Understanding trees is fundamental for grasping more advanced concepts such as binary search trees, expression parsing, and efficient searching and sorting algorithms. This article unpacks every tree-related point required by the WJEC specification, from basic terminology to graph traversal and practical applications, with bilingual explanations to support both English and Chinese revision.
树是WJEC A-Level计算机科学大纲中最灵活且最常考的抽象数据类型之一。树将数据组织为层次结构，顶部是单个根节点，向下分支到子节点，最终终止于叶节点。理解树是掌握更高级概念（例如二叉搜索树、表达式解析、高效查找与排序算法）的基础。本文从基本术语到图的遍历和实际应用，逐条解析WJEC规范要求的每个树相关考点，提供英中双语解释，方便中英文复习。
1. What is a Tree? | 什么是树？
A tree is a connected, undirected graph with no cycles. In computer science, it is usually treated as a rooted directed structure where each node (except the root) has exactly one parent. This gives a natural top-down hierarchy. Trees can model file systems, organisation charts, document object models (DOM), and decision processes.
树是一个无环的连通无向图。在计算机科学中，通常将其视为有根的有向结构，每个节点（根节点除外）恰好有一个父节点，形成自然的自顶向下层次。树可以建模文件系统、组织结构图、文档对象模型（DOM）和决策过程。
A tree consists of nodes connected by edges. The root is the topmost node; children are nodes directly connected below another node; a parent is the node directly above. Nodes with the same parent are siblings. A leaf (external node) is a node with no children; all other nodes are internal nodes. 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 node. The size of a tree is the number of nodes it contains.
树由节点和边组成。根是最顶层的节点；直接位于某节点下方的节点称为子节点；直接位于上方的节点称为父节点。具有相同父节点的节点是兄弟节点。叶节点（外部节点）是没有子节点的节点；其他节点均为内部节点。节点的深度是从根到该节点的边数；树的高度是任意节点的最大深度。树的大小是它所包含的节点总数。
2. Binary Trees | 二叉树
A binary tree is a tree in which each node can have at most two children, conventionally referred to as the left child and the right child. This simple restriction enables powerful algorithms for traversal, searching, and expression representation. A binary tree can be empty (null root), or consist of a root and two disjoint binary trees (the left subtree and the right subtree).
二叉树是每个节点最多有两个子节点的树，这两个子节点通常称为左子节点和右子节点。这一简单限制使得遍历、查找和表达式表示等强大算法成为可能。二叉树可以为空（空根），或由一个根和两棵不相交的二叉树（左子树和右子树）组成。
In the WJEC specification, you must be able to distinguish between a full binary tree (every node has either 0 or 2 children), a complete binary tree (all levels are fully filled except possibly the last, which is filled from left to right), and a perfect binary tree (all internal nodes have two children and all leaves are at the same level). These distinctions affect efficiency and storage representation.
在WJEC规范中，您必须能够区分满二叉树（每个节点要么有0个要么有2个子节点）、完全二叉树（除最后一层外所有层均填满，且最后一层从左到右填充）和完美二叉树（所有内部节点都有两个子节点，且所有叶节点在同一层）。这些区别影响效率和存储表示。
A binary tree can be implemented using nodes with data, a left pointer/reference, and a right pointer/reference. In a procedural language, a node is a record (struct) with three fields; in an object-oriented language, it is a class with data and two child references.
二叉树可以使用包含数据、左指针/引用和右指针/引用的节点来实现。在过程化语言中，节点是一个具有三个字段的记录（结构体）；在面向对象语言中，它是一个带有数据和两个子引用的类。
3. Binary Search Trees (BST) | 二叉搜索树（BST）
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 (or equal to) the node's value. This ordering allows for efficient O(log n) search, insertion, and deletion on average, provided the tree stays relatively balanced.
二叉搜索树是具有排序性质的二叉树：对于每个节点，其左子树中的所有值都小于该节点的值，而其右子树中的所有值都大于（或等于）该节点的值。只要树保持相对平衡，这种排序就可以实现平均O(log n)的高效查找、插入和删除。
Searching in a BST starts at the root. If the target equals the root, it is found. If smaller, search the left subtree; if larger, search the right subtree. This recursive divide-and-conquer strategy mirrors binary search on an array but with a dynamic linked structure.
在BST中查找从根开始。如果目标值等于根值，则找到。如果更小，则在左子树中查找；如果更大，则在右子树中查找。这种递归分治策略类似于数组上的二分查找，但采用了动态链式结构。
Insertion follows a similar path: compare the new value with the current node, go left if smaller, go right if larger, until an empty spot (a null left or right) is found, then attach the new node. Deletion is trickier and has three cases: removing a leaf (simply delete), removing a node with one child (replace it with its child), and removing a node with two children (find the in-order successor, the smallest node in the right subtree, copy its value, and delete that successor).
插入遵循类似路径：将新值与当前节点比较，如果较小则向左走，如果较大则向右走，直到找到一个空位（空左或空右）为止，然后挂接新节点。删除操作比较复杂，分为三种情况：删除叶节点（直接删除），删除只有一个子节点的节点（用其子节点替换它），以及删除有两个子节点的节点（找到中序后继节点，即右子树中最小的节点，复制其值，并删除该后继节点）。
4. Tree Traversals | 树的遍历
Traversal means visiting every node in a tree exactly once in a systematic order. For binary trees, WJEC requires knowledge of three depth-first traversals: pre-order (root, left subtree, right subtree), in-order (left subtree, root, right subtree), and post-order (left subtree, right subtree, root). Each can be implemented recursively or iteratively with a stack.
遍历是指按照系统顺序恰好访问树中的每个节点一次。对于二叉树，WJEC要求掌握三种深度优先遍历：前序（根、左子树、右子树）、中序（左子树、根、右子树）和后序（左子树、右子树、根）。每种遍历都可以用递归或使用栈的迭代方式实现。
In-order traversal of a BST yields node values in ascending order, which is extremely useful for sorting or outputting ordered data. Pre-order traversal can produce a prefix notation (Polish notation) of an expression tree, useful for parsing and evaluation. Post-order traversal yields postfix notation (Reverse Polish Notation), which can be directly executed by a stack-based evaluator.
对BST进行中序遍历可以按升序得到节点值，这对于排序或输出有序数据极其有用。前序遍历可以产生表达式树的前缀表示法（波兰表示法），适用于解析和求值。后序遍历产生后缀表示法（逆波兰表示法），可直接由基于栈的求值器执行。
WJEC also expects understanding of breadth-first traversal (level order). Here nodes are visited level by level from left to right, typically using a queue. Level order traversal is useful for building a complete binary tree or for algorithms where depth is less relevant.
WJEC也期望理解广度优先遍历（层序遍历）。它是逐层从左到右访问节点，通常使用队列实现。层序遍历对于构建完全二叉树或与深度关系不大的算法很有用。
5. Representing Expressions with Binary Trees | 用二叉树表示表达式
). This representation makes evaluation, conversion between notations, and code generation straightforward. The expression (A + B) × (C − D) becomes a tree with root '×', left child '+', right child '−', and so on.
算术表达式可以表示为二叉树，其中内部节点存放运算符，叶节点存放操作数（数字或变量）。这种表示法使得求值、表示法之间的转换和代码生成变得简单直接。表达式 (A + B) × (C − D) 形成一棵树，根为'×'，左子节点为'+'，右子节点为'−'，依此类推。
output prefix or postfix forms. For example, pre-order traversal of the tree gives × + A B − C D (prefix), and post-order gives A B + C D − × (postfix).
WJEC考生应能够从完全括号化的中缀表示法构建表达式树，然后通过遍历输出前缀或后缀形式。例如，对该树进行前序遍历得到 × + A B − C D（前缀），后序遍历得到 A B + C D − ×（后缀）。
Evaluating an expression tree is done recursively: if the node is an operand, return its value; if it is an operator, recursively evaluate the left and right subtrees, then apply the operator. This is the basis of compiler and interpreter design.
求值表达式树采用递归方式：如果节点是操作数，则返回其值；如果是运算符，则递归求值左子树和右子树，然后应用运算符。这是编译器和解释器设计的基础。
6. Implementing Trees: Pointers vs Arrays | 树的实现：指针与数组
In WJEC's programming context, trees can be implemented using either dynamic data structures (nodes with pointers) or static implementations (arrays). A pointer-based node typically stores data, a left child pointer, and a right child pointer. This is memory-flexible but relies on dynamic memory allocation and garbage collection.
在WJEC的编程语境中，树可以使用动态数据结构（带指针的节点）或静态实现（数组）来实现。基于指针的节点通常存储数据、左子指针和右子指针。这种方式内存使用灵活，但依赖动态内存分配和垃圾回收。
An array-based binary tree stores nodes in an array, with index relationships: for a node at index i, its left child is at 2i+1, right child at 2i+2 (0-indexed), and its parent at floor((i−1)/2). This representation is memory efficient for complete or nearly complete trees, e.g., a heap, but wastes space for sparse trees. WJEC questions often ask to draw the array representation given a binary tree.
基于数组的二叉树将节点存储在数组中，利用索引关系：对于索引为 i 的节点，其左子节点位于 2i+1，右子节点位于 2i+2（0起始索引），父节点位于 floor((i−1)/2)。这种表示法对于完全或近似完全树（例如堆）内存效率高，但对于稀疏树会浪费空间。WJEC考题常要求根据给定的二叉树绘制其数组表示。
When using arrays, the root is at index 0. A missing child is often represented by a sentinel value or simply left blank. Understanding both implementations is critical for WJEC unit 2 (programming concepts) and unit 3 (algorithms).
使用数组时，根位于索引0。缺失的子节点通常用哨兵值表示或直接留空。理解这两种实现方式对于WJEC Unit 2（编程概念）和 Unit 3（算法）至关重要。
7. Tree Applications: Heaps and Priority Queues | 树的应用：堆与优先队列
is introduced alongside trees. WJEC may examine heap operations: insertion (add at the next free position, then sift up) and deletion of the root (replace with last element, then sift down). Heaps underpin priority queues.
虽然堆从技术上讲是满足堆性质的完全二叉树（最小堆：父节点 ≤ 子节点；最大堆：父节点 ≥ 子节点），但通常与树一起介绍。WJEC可能考查堆的操作：插入（在下一个空闲位置添加，然后向上调整）和删除根节点（用最后一个元素替换，然后向下调整）。堆是优先队列的基础。
The WJEC specification also references tree-based searching and sorting. Binary search trees support dynamic data sets with efficient search. Heaps enable heap sort, an O(n log n) in-place sorting algorithm. Understanding these applications helps in selecting appropriate data structures for given problems.
WJEC规范还提及了基于树的查找和排序。二叉搜索树支持动态数据集的高效查找。堆实现了堆排序，一种O(n log n)的原位排序算法。理解这些应用有助于为给定问题选择合适的数据结构。
8. Tree-Based File Structures | 基于树的文件结构
In data storage, trees are essential for organising indexes. A B-tree (and its variant B+ tree) allows efficient access to large files by keeping the tree height low and storing multiple keys per node. Although WJEC does not demand deep B-tree mechanics, questions may ask about the idea of hierarchical indexing and how trees reduce disk accesses compared to linear files.
在数据存储中，树是组织索引所必需的。B树（及其变体B+树）通过保持低树高并在每个节点存储多个键，实现对大型文件的高效访问。尽管WJEC不要求深入了解B树机制，但题目可能询问层次索引的概念，以及树如何相比线性文件减少磁盘访问次数。
XML and HTML DOM trees are also real-world examples. Parsing a web page produces a tree structure; JavaScript traverses this tree to manipulate elements. This contextualises trees beyond abstract theory and aligns with the broader computing curriculum.
XML和HTML DOM树也是现实世界的例子。解析网页会生成树结构；JavaScript遍历该树以操作元素。这将树置于超越抽象理论的背景下，与更广泛的计算课程内容一致。
9. Recursion and Tree Algorithms | 递归与树算法
Tree algorithms rely heavily on recursion. Recursive definitions mirror the self-similar structure of subtrees. Traversals, search, insertion, deletion, and expression evaluation are all naturally expressed recursively. WJEC expects candidates to trace recursive tree functions and write simple recursive algorithms to count nodes, compute height, or check if a tree is balanced.
树算法严重依赖递归。递归定义反映了子树的自我相似结构。遍历、查找、插入、删除和表达式求值都可以自然地用递归表达。WJEC期望考生能够追踪递归树函数，并编写简单的递归算法，例如计算节点数、计算高度或检查树是否平衡。
For example, to compute the number of nodes: if tree is empty return 0, else return 1 + count(left) + count(right). Height: if empty return −1 (or 0 depending on definition), else return 1 + max(height(left), height(right)). These algorithms appear frequently in written and practical exams.
例如，计算节点数：如果树为空则返回0，否则返回 1 + count(left) + count(right)。高度：如果为空返回 −1（或0，取决于定义），否则返回 1 + max(height(left), height(right))。这些算法在笔试和实践考试中频繁出现。
10. Searching Algorithms Using Trees | 使用树的搜索算法
Beyond binary search trees, trees define search spaces in game playing and problem solving. A state space tree represents all possible moves; minimax algorithms use game trees. While not explicitly in the WJEC tree topic, understanding that trees underpin these algorithms broadens computational thinking. Depth-first and breadth-first tree traversals form the basis of uninformed graph search, which may appear in Algorithm questions.
除了二叉搜索树，树还定义了博弈和问题求解中的搜索空间。状态空间树表示所有可能的走法；极小极大算法使用博弈树。尽管这些不直接属于WJEC树专题，但理解树是这些算法的基础可以拓宽计算思维。深度优先和广度优先树遍历构成了无信息图搜索的基础，这可能出现在算法题中。
For the written paper, always clarify the traversal order, the structure of the tree after operations, and the time complexity where appropriate. Use clear, step-by-step diagrams and pseudocode. Practice drawing trees after sequence of insertions and deletions.
在笔试中，始终要明确遍历顺序、操作后树的结构，并在适当的地方分析时间复杂度。使用清晰的逐步示意图和伪代码。练习绘制一系列插入和删除操作后的树。
11. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧
C specification often uses edge-count height (root depth 0, leaf depth = number of edges). Confirm with past mark schemes. Also, when constructing a BST, always keep the ordering property: left < node < right (or left ≤ node ≤ right). Insertion order drastically affects the shape and balance of the tree.
许多学生混淆深度和高度，或者忘记只有一个根节点的树高度为0（或1，取决于约定）且深度为0。WJEC规范通常使用边计数高度（根深度为0，叶深度=边数）。请根据历年评分方案确认。此外，在构建BST时，始终保持排序性质：左 < 节点 < 右（或左 ≤ 节点 ≤ 右）。插入顺序极大地影响树的形状和平衡程度。
In traversal questions, do not just list the output; show the order of visiting with a labelled sequence. If a question asks to draw a binary tree from given traversals (e.g., pre-order and in-order), remember that pre-order gives the root first, and in-order splits left and right subtrees. Reconstruct recursively. These "reverse engineering" questions are exam favourites.
在遍历题中，不要只列出输出；要用标记序列显示访问顺序。如果题目要求根据给定的遍历（例如前序和中序）绘制二叉树，请记住前序遍历首先给出根，中序遍历将左右子树分开。递归重建。这类“逆向工程”题是考试的热门。
Finally, when implementing tree operations in Python or another language for coursework, ensure memory is managed properly and infinite loops are avoided. Use iterative deepening or explicit stack/queue to avoid stack overflow with deep trees. Always test edge cases: empty tree, single node, left-skewed, right-skewed.
最后，在课程作业中用Python或其他语言实现树操作时，确保正确管理内存并避免无限循环。使用迭代加深或显式栈/队列来避免深树时的栈溢出。始终测试边界情况：空树、单个节点、左斜树、右斜树。
12. Summary: Key Points for WJEC Revision | 总结：WJEC复习要点
Trees form a core part of the A-Level Computer Science curriculum. Master the terminology (root, leaf, parent, child, sibling, depth, height), the three depth-first traversals plus breadth-first, and the operations on binary search trees. Understand both pointer-based and array-based implementations, and the use of trees in expression evaluation and indexing. Relate trees to recursion and justify their efficiency advantages over linear structures.
树是A-Level计算机科学课程的核心部分。掌握术语（根、叶、父、子、兄弟、深度、高度）、三种深度优先遍历加广度优先遍历，以及二叉搜索树的操作。理解基于指针和基于数组的实现，以及树在表达式求值和索引中的应用。将树与递归联系起来，并说明其相对于线性结构的效率优势。
Regularly practise constructing, traversing, and manipulating trees on paper. Draw clear diagrams and label each step. Use bilingual terminology to solidify understanding in both languages, as questions may involve English terms even in bilingual contexts. Always check the official WJEC spec and past papers for the exact phrasing expected.
经常在纸上练习树的构建、遍历和操作。绘制清晰的图表并标注每一步。使用双语术语以巩固两种语言的理解，因为即使在双语环境中，题目也可能包含英文术语。始终查阅WJEC官方规范和历年试卷，以了解期望的准确措辞。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图