📚 GCSE AQA Computer Science: Trees | GCSE AQA 计算机：树 考点精讲
Trees are one of the most important non‑linear data structures in computer science. From file systems and database indexes to game AI and expression parsing, tree structures enable efficient organisation, searching, and manipulation of hierarchical data. The GCSE AQA Computer Science specification expects you to understand the fundamental terminology, the properties of binary trees, how binary search trees work, and the three standard depth‑first traversals (pre‑order, in‑order, post‑order). This revision guide breaks down every key concept with crystal‑clear explanations and exam‑ready examples.
树是计算机科学中最重要的非线性数据结构之一。从文件系统、数据库索引到游戏人工智能和表达式解析，树结构能够高效地组织、查找和处理层次化数据。GCSE AQA 计算机科学大纲要求你掌握基本术语、二叉树的性质、二叉搜索树的工作方式以及三种标准的深度优先遍历（前序、中序、后序）。本复习指南将用清晰的讲解和适合考试的例子逐一分解每个核心概念。
1. What is a Tree? | 什么是树？
A tree is a connected, undirected graph with no cycles, where every pair of nodes is connected by exactly one simple path. In computer science, we draw trees with the root at the top and branches growing downwards. Each node contains data and may have links (pointers) to child nodes. A tree has exactly one root node, and all other nodes are descendants of the root. If a node has no children it is called a leaf. The edges represent the parent‑child relationship. Think of a family tree or a folder structure on your computer — they are both everyday examples of trees.
树是一种连通、无环的无向图，任何两个节点之间恰好由一条简单路径相连。在计算机科学中，我们通常将根画在顶部，树枝向下生长。每个节点包含数据，并可以拥有指向子节点的链接（指针）。一棵树只有一个根节点，所有其他节点都是根的后代。没有子节点的节点称为叶节点。边表示父节点与子节点之间的关系。你可以想象一个家族谱系图或电脑中的文件夹结构——它们都是日常生活中树的例子。
2. Essential Tree Terminology | 基本术语
Root – the topmost node of the tree.
Parent – a node that has one or more child nodes.
Child – a node directly connected to another node when moving away from the root.
Sibling – nodes that share the same parent.
Leaf – a node with no children.
Edge – the link between two nodes.
Path – a sequence of edges from one node to another.
Depth of a node – the number of edges from the root to that node.
Height of a node – the number of edges on the longest path from that node down to a leaf. The height of the tree is the height of the root.
Subtree – any node together with all its descendants forms a subtree. Every node can be regarded as the root of its own subtree.
根 – 树的顶端节点。
父节点 – 拥有一个或多个子节点的节点。
子节点 – 从根向下移动时，与另一个节点直接相连的节点。
兄弟节点 – 拥有相同父节点的节点。
叶节点 – 没有子节点的节点。
边 – 两个节点之间的连接。
路径 – 从一个节点到另一个节点经过的边的序列。
节点的深度 – 从根到该节点的边的数量。
节点的高度 – 从该节点向下到最远叶节点的最长路径的边的数量。树的高度等于根的高度。
子树 – 任意节点及其所有后代节点构成一棵子树。每个节点都可以被看作以其为根的子树。
3. Binary Trees | 二叉树
A binary tree is a tree in which every node has at most two children, commonly referred to as the left child and the right child. Even if a node has only one child, it is still classed as a binary tree. A full binary tree is one where every node has exactly 0 or 2 children. A complete binary tree is one in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. The maximum number of nodes at level k (where the root is level 0) is 2ᵏ. For a binary tree of height h, the maximum total number of nodes is 2ʰ⁺¹ – 1.
二叉树是一种每个节点最多有两个子节点的树，这两个子节点通常被称为左子节点和右子节点。即使一个节点只有一个子节点，该树仍被归类为二叉树。满二叉树是指每个节点恰好有 0 个或 2 个子节点的树。完全二叉树是指除最后一层外，每一层都被完全填满，且最后一层的所有节点均尽可能靠左排列的树。第 k 层（根为第 0 层）的最大节点数是 2ᵏ。对于高度为 h 的二叉树，最大总节点数为 2ʰ⁺¹ – 1。
4. Binary Search Trees (BST) | 二叉搜索树
A binary search tree is a special type of binary tree that follows a strict ordering rule: for any node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger than the node's value. This property holds for every node in the tree. No duplicate values are usually allowed. The main advantage of a BST is that it supports fast searching, insertion, and deletion. When searching for a value, you compare the target with the current node. If it is smaller you go left; if larger, you go right. This process continues until you find the value or reach a leaf (null).
二叉搜索树是一类特殊的二叉树，它遵循严格的排序规则：对于任意节点，其左子树中的所有值均小于该节点的值，其右子树中的所有值均大于该节点的值。树中的每一个节点都满足此性质。通常不允许出现重复值。二叉搜索树的主要优点是能够快速完成查找、插入和删除操作。查找某个值时，将目标值与当前节点进行比较，若目标值较小则向左走，较大则向右走，如此反复，直到找到该值或到达叶节点（空）为止。
5. Searching in a BST – Complexity | BST 查找的时间复杂度
If a binary search tree is well balanced, the number of comparisons required to find a value is proportional to the height of the tree: O(log n). In a perfectly balanced tree with n nodes, the height is approximately log₂(n). However, if values are inserted in sorted order (e.g. 1, 2, 3, 4, 5), the tree degenerates into a linear linked list, and the height becomes n – 1. In that worst‑case scenario, searching, insertion and deletion all require O(n) time. This is why balance is critical for maintaining efficiency.
若二叉搜索树处于良好平衡状态，查找某个值所需要的比较次数与树的高度成正比：O(log n)。在一棵有 n 个节点的完美平衡树中，其高度大约为 log₂(n)。然而，如果插入的值是有序的（例如 1, 2, 3, 4, 5），则该树会退化为一条线性的链表，此时高度变为 n – 1。在这种最坏情况下，查找、插入和删除所需的时间均为 O(n)。这便是保持平衡对于维持效率至关重要的原因。
6. Inserting into a Binary Search Tree | 向二叉搜索树中插入节点
To insert a new value, you perform a search to find the correct empty position. Starting at the root, compare the new value with the current node. If it is smaller, move to the left child; if larger, move to the right child. If the chosen child is null, place the new node there. Duplicates are normally rejected. Notice that the shape of the tree depends on the order of insertion; the same set of values can produce many different BSTs. AQA exam questions may ask you to draw the resulting BST after a series of insertions, so practise step by step. Example: insert 8, 3, 10, 1, 6 into an empty BST.
要插入一个新值，需通过查找找到正确的空位置。从根节点开始，将新值与当前节点比较。若新值较小，则移向左子节点；若较大，则移向右子节点。若所选择的子节点为空，就在此处放置新节点。通常会拒绝重复值。注意，树的形状取决于插入的顺序；同一组数据可能产生多种不同的二叉搜索树。AQA 试题可能会要求你在完成一系列插入操作后画出最终的 BST，因此务必逐步练习。例如：将 8、3、10、1、6 依次插入一棵空的 BST。
7. Deletion from a Binary Search Tree (Summary) | 从二叉搜索树中删除节点（概述）
Deleting a node from a BST is more complex than insertion, and you are not required to implement it in full detail for GCSE, but you should understand the three cases. Case 1: node is a leaf — simply remove it. Case 2: node has one child — replace the node with its child. Case 3: node has two children — find the node's in‑order successor (the smallest value in its right subtree), copy that value to the node, and then delete the successor (which will fall into Case 1 or Case 2). Being able to describe these cases in words will strengthen your written answers.
从 BST 中删除节点比插入更为复杂，GCSE 不要求完整实现，但你应理解三种情况。情况 1：节点为叶节点——直接移除即可。情况 2：节点只有一个子节点——用该子节点替换该节点。情况 3：节点有两个子节点——找到该节点的中序后继节点（即其右子树中的最小值），将该值复制到该节点中，然后删除该后继节点（后者将属于情况 1 或情况 2）。能够用文字描述这三种情况，有助于提升你书面回答的质量。
8. Tree Traversals – Pre‑order, In‑order, Post‑order | 树的遍历——前序、中序、后序
Traversing a tree means visiting every node exactly once. There are three classic depth‑first methods, all defined recursively:
Pre‑order: visit the root, then traverse the left subtree, then traverse the right subtree.
In‑order: traverse left subtree, visit root, traverse right subtree.
Post‑order: traverse left subtree, traverse right subtree, visit root.
In a BST, in‑order traversal visits nodes in ascending order, which is a vital property used in sorting and searching. You must be able to write down the sequence of nodes produced by a given traversal on a given tree. For example, the in‑order of the BST [8,3,10,1,6] is 1,3,6,8,10.
遍历一棵树意味着恰好访问每一个节点一次。三种经典的深度优先方法均通过递归定义：
前序遍历：访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历：遍历左子树，访问根节点，再遍历右子树。
后序遍历：遍历左子树，遍历右子树，最后访问根节点。
在 BST 中，中序遍历会按升序访问节点，这是用于排序和查找的重要性质。你必须能够写出给定树在某种遍历下得到的节点序列。例如，BST 序列 [8,3,10,1,6] 的中序遍历结果为 1,3,6,8,10。
9. Applications of Trees | 树的应用
sions can be parsed into expression trees, enabling compilers to evaluate them correctly; leaves hold operands (numbers) and internal nodes hold operators (+, -, ×, ÷). Decision trees are widely used in machine learning and AI to model decisions. Network routing algorithms may use spanning trees. Even natural language processing often relies on syntax trees. Understanding the abstract structure of trees helps you appreciate these real‑world uses and prepares you for higher‑level computing concepts.
树在计算领域无处不在。文件系统采用树状结构，目录相当于内部节点，文件相当于叶节点。算术表达式可被解析为表达式树，从而使编译器能够正确求值；叶节点存放操作数（数字），内部节点存放运算符（+、-、×、÷）。决策树广泛应用于机器学习和人工智能中，用于决策建模。网络路由算法可能使用生成树。甚至自然语言处理也常常依赖于语法树。理解树的抽象结构能帮助你认识这些现实应用，并为更高级的计算概念做好准备。
10. Exam Tips and Common Pitfalls | 考试技巧与常见错误
In the exam, you may be asked to draw a tree after a sequence of insertions, complete a traversal, or identify the root, leaves, and height. Always read the question carefully: is the tree a BST or just an ordinary binary tree? If it's a BST, apply the left‑less‑right‑greater rule consistently. When writing traversal outputs, use a clear comma‑separated list. A common mistake is confusing pre‑order and post‑order; remember that the name tells you when the root is processed: pre means before the children, post means after. Practising with small trees of 5–7 nodes will build your confidence and speed.
考试中，你可能会被要求在一系列插入操作后画出树、完成遍历，或者识别根节点、叶节点和高度。务必仔细审题：这棵树是 BST 还是普通的二叉树？如果是 BST，要始终遵循“左小右大”的规则。在写出遍历结果时，应使用清晰的逗号分隔列表。一个常见的错误是混淆前序和后序；记住，名称已经告诉了你处理根节点的时机：pre 表示在子节点之前，post 表示在子节点之后。用 5 到 7 个节点的小树多加练习，可以增强信心并提高速度。
11. From Trees to Advanced Concepts | 从树到高级概念
Although GCSE keeps the focus on binary trees and BSTs, it is useful to know that self‑balancing trees such as AVL trees and red‑black trees guarantee O(log n) operations even in the worst case, and are used in database engines and language libraries. B‑trees and B+ trees power modern file systems and database indexing. These advanced structures all build on the fundamental principles you learn now: hierarchical organisation, efficient search paths, and recursive definitions. Getting the foundations rock‑solid at GCSE level will make A‑level and beyond far more approachable.
尽管 GCSE 将重点放在二叉树和 BST 上，但了解以下内容会有所帮助：AVL 树和红黑树等自平衡树即使在最坏情况下也能保证 O(log n) 的操作时间，并被应用于数据库引擎和语言库中。B 树和 B+ 树支撑着现代文件系统和数据库索引。这些高级结构都建立在你目前所学习的基本原理之上：层次化组织、高效的查找路径和递归定义。在 GCSE 阶段打下扎实的基础，将使 A‑level 及更高层次的学习变得轻而易举。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图