Trees in IGCSE AQA Computer Science | IGCSE AQA 计算机：树考点精讲

📚 Trees in IGCSE AQA Computer Science | IGCSE AQA 计算机：树考点精讲

A tree is a widely used abstract data structure that simulates a hierarchical structure, with a root value and subtrees of children represented as a set of linked nodes. In IGCSE Computer Science, understanding trees is essential for grasping concepts such as searching algorithms, expression evaluation, and efficient data organisation. This revision guide covers everything you need to know about trees for the AQA specification, including terminology, binary trees, tree traversal, and common applications.

树是一种广泛使用的抽象数据结构，模拟层次结构，具有一个根值和一系列由链接节点构成的子树。在 IGCSE 计算机科学中，理解树的概念对于掌握搜索算法、表达式求值和高效数据组织至关重要。本备考指南涵盖了 AQA 考试大纲中关于树的所有考点，包括术语、二叉树、树的遍历以及常见应用。

1. What is a Tree? | 什么是树？

A tree is a non-linear data structure consisting of nodes connected by edges. It is a collection of nodes where one node is designated as the root, and the remaining nodes are partitioned into disjoint subtrees, each of which is itself a tree. Unlike arrays or linked lists where data is arranged sequentially, a tree organises data hierarchically, allowing for efficient insertion, deletion, and searching operations.

树是一种非线性数据结构，由通过边连接的节点组成。它是一个节点的集合，其中一个节点被指定为根，其余节点被划分为互不相交的子树，每个子树本身也是一棵树。与数据按顺序排列的数组或链表不同，树以层次结构组织数据，能够高效地进行插入、删除和搜索操作。

A tree is made up of nodes, and each node contains a data element and may link to one or more child nodes. The topmost node is called the root. Nodes with no children are called leaves or leaf nodes. Edges represent the relationships between nodes. A subtree is a portion of the entire tree that consists of a node and all its descendants.

树由节点组成，每个节点包含一个数据元素，并可能链接到一个或多个子节点。最顶端的节点称为根。没有子节点的节点称为叶节点。边表示节点之间的关系。子树是整个树的一部分，由一个节点及其所有后代组成。

2. Basic Tree Terminology | 基本树术语

It is crucial to master the vocabulary used in tree data structures to answer exam questions correctly. A root is the only node with no parent. A parent is a node that has one or more children, and a child is a node that has a parent. Nodes that share the same parent are called siblings. A leaf (or external node) has no children. An internal node is any node that has at least one child. 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. A subtree consists of a node and all its descendants.

掌握树数据结构中的术语对于正确回答考试题目至关重要。根是唯一没有父节点的节点。父节点是有一个或多个子节点的节点，而子节点是有父节点的节点。共享同一父节点的节点称为兄弟节点。叶节点（或外部节点）没有子节点。内部节点是至少有一个子节点的任何节点。节点的深度是从根到该节点的边的数量。树的高度是所有节点中深度的最大值。子树由一个节点及其所有后代组成。

In exam questions, you may be asked to state the height of a tree, identify leaf nodes, or count the number of siblings. Always count edges carefully when measuring depth and height; some definitions use the number of nodes on the path, but the AQA specification commonly uses edges.

在考试题中，你可能会被要求说出树的高度、识别叶节点或计数兄弟节点的数量。在测量深度和高度时要仔细计数边；有些定义使用路径上的节点数，但 AQA 大纲通常使用边数。

3. Binary Trees | 二叉树

A binary tree is a special type of tree where each node has at most two children, referred to as the left child and the right child. This restriction makes binary trees particularly suitable for search algorithms and expression representations. A binary tree can be empty, and each child of a node is itself the root of a binary subtree. Binary trees are used in many applications including binary search trees, expression trees, and Huffman coding trees.

二叉树是一种特殊的树，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。这一限制使得二叉树特别适合于搜索算法和表达式表示。二叉树可以为空，每个节点的子节点本身也是一个二叉子树的根。二叉树在许多应用中都有使用，包括二叉搜索树、表达式树和哈夫曼编码树。

A full binary tree is one where every node has either 0 or 2 children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. These properties can be tested in multiple-choice or short-answer questions.

满二叉树是每个节点都有 0 个或 2 个子节点的树。完全二叉树是除了可能最后一层外，每一层都被完全填满，并且所有节点都尽可能靠左的二叉树。这些性质可能会在选择题或简答题中进行考查。

4. Representing Trees in Memory | 在内存中表示树

Trees are typically implemented using nodes and pointers. Each node in a binary tree can be stored as a record or object with three fields: one for the data, one for a pointer to the left child, and one for a pointer to the right child. A null pointer (often shown as a slash or a special value) indicates the absence of a child. In diagrams, nodes are drawn as circles, and pointers are arrows linking parents to children.

树通常使用节点和指针来实现。二叉树中的每个节点可以存储为一个具有三个字段的记录或对象：一个用于数据，一个用于指向左子节点的指针，一个用于指向右子节点的指针。空指针（通常表示为斜线或特殊值）表示没有子节点。在图中，节点画成圆圈，指针是从父节点指向子节点的箭头。

Alternatively, a tree could be stored using a 2D array or a one-dimensional array where the index relationship between parent and children is defined by a formula (commonly used in heaps). For example, in a zero-indexed array, the children of node at index i are at 2i+1 and 2i+2. However, the pointer-based representation is more common in IGCSE discussions of binary trees.

或者，树可以使用二维数组或一维数组存储，其中父子之间的索引关系由公式定义（通常用于堆中）。例如，在零索引数组中，索引 i 处的节点的子节点位于 2i+1 和 2i+2。然而，在 IGCSE 对二叉树的讨论中，基于指针的表示法更为常见。

5. Binary Search Trees (BST) | 二叉搜索树

A binary search tree (BST) is a binary tree with the following 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. This property must hold recursively for every node. BSTs allow for very efficient searching, insertion, and deletion, with average time complexity O(log n) when the tree is balanced.

二叉搜索树是一种具有以下排序性质的二叉树：对于每个节点，其左子树中的所有值都小于该节点的值，而其右子树中的所有值都大于该节点的值。这一性质必须对每个节点递归成立。二叉搜索树能够实现非常高效的搜索、插入和删除操作，当树平衡时，平均时间复杂度为 O(log n)。

To search for a value in a BST, you start at the root. If the target equals the current node’s value, the search is successful. If the target is less, move to the left child; if greater, move to the right child. Repeat until the value is found or a null pointer is reached. Insertion follows a similar path to place the new node as a leaf.

在二叉搜索树中搜索一个值，从根开始。如果目标等于当前节点的值，则搜索成功。如果目标较小，则移动到左子节点；如果较大，则移动到右子节点。重复此过程直到找到该值或遇到空指针。插入遵循类似的路径，将新节点放置为叶节点。

6. Tree Traversal Methods | 树的遍历方法

Tree traversal refers to the process of visiting (examining or updating) each node in a tree exactly once in a specific order. For binary trees, three classical depth-first traversals are pre-order, in-order, and post-order. These are defined recursively and are essential for algorithms that process tree data structures, such as printing an expression tree or copying a tree.

树的遍历是指按照特定顺序恰好访问（检查或更新）树中每个节点一次的过程。对于二叉树，三种经典的深度优先遍历是前序遍历、中序遍历和后序遍历。这些遍历是递归定义的，对于处理树数据结构的算法（如打印表达式树或复制一棵树）至关重要。

In pre-order traversal, the node is visited first, then the left subtree, then the right subtree (VLR). In in-order traversal, the left subtree is visited, then the node, then the right subtree (LVR). In post-order traversal, the left subtree is visited, then the right subtree, then the node (LRV). Memorising these abbreviations helps to quickly write out traversal sequences for any binary tree.

在前序遍历中，先访问节点，然后是左子树，最后是右子树（VLR）。在中序遍历中，先访问左子树，然后是节点，最后是右子树（LVR）。在后序遍历中，先访问左子树，然后是右子树，最后是节点（LRV）。记住这些缩写有助于快速写出任何二叉树的遍历序列。

Example: for a small BST with root 10, left child 5, right child 15, and 5 having left child 2. Pre-order: 10, 5, 2, 15. In-order: 2, 5, 10, 15. Post-order: 2, 5, 15, 10. Note how in-order traversal of a BST yields the values in ascending order.

示例：一个小的二叉搜索树，根为 10，左子节点为 5，右子节点为 15，5 有左子节点 2。前序：10, 5, 2, 15。中序：2, 5, 10, 15。后序：2, 5, 15, 10。请注意，对二叉搜索树进行中序遍历会产生升序排列的值。

7. Algorithms for Traversal (Using Recursion) | 遍历算法（使用递归）

Traversal algorithms are naturally implemented using recursion. The base case is an empty tree (null). For pre-order, the steps are: if tree is not empty, output the root’s data, traverse left subtree, traverse right subtree. For in-order: traverse left, output root, traverse right. For post-order: traverse left, traverse right, output root. These recursive procedures are simple and elegant, and they form the basis of many tree operations.

遍历算法很自然地使用递归来实现。基本情况是空树（null）。对于前序，步骤是：如果树不为空，输出根的数据，遍历左子树，遍历右子树。对于中序：遍历左子树，输出根，遍历右子树。对于后序：遍历左子树，遍历右子树，输出根。这些递归过程简单而优雅，构成了许多树操作的基础。

You may be asked to write pseudocode or trace an algorithm for a given tree. Always ensure that you correctly follow the recursive call order and that you handle the null case to avoid infinite recursion. In pseudocode, a procedure such as TraverseInOrder(Node) will call itself on the left child, then output the node’s data, then call itself on the right child.

你可能会被要求为给定的树编写伪代码或跟踪算法。务必确保正确遵循递归调用顺序，并处理空指针情况以避免无限递归。在伪代码中，像 TraverseInOrder(Node) 这样的程序会先对左子节点调用自身，然后输出节点数据，再对右子节点调用自身。

8. Expression Trees | 表达式树

An expression tree is a specific kind of binary tree used to represent mathematical or logical expressions. Each leaf node contains an operand (a number or a variable), and each internal node contains an operator. The tree captures operator precedence and associativity without the need for parentheses. Evaluating an expression tree or producing infix/postfix notation from it is a key skill.

表达式树是一种用于表示数学或逻辑表达式的特殊二叉树。每个叶节点包含一个操作数（数字或变量），每个内部节点包含一个运算符。这种树可以在不使用括号的情况下体现运算符的优先级和结合性。对表达式树求值或从中生成中缀/后缀表示法是一项关键技能。

For example, the expression (3 + 2) * 5 would be represented as a tree with ‘*’ at the root, ‘+’ as the left child, and operands as leaves. A post-order traversal of this tree yields the postfix notation “3 2 + 5 *”, which is useful for stack-based evaluation. In-order traversal produces the infix expression, but parentheses may be needed to restore the correct order unless the tree inherently captures it.

例如，表达式 (3 + 2) * 5 会表示成一棵树，根为 ‘*’，左子节点为 ‘+’，操作数为叶节点。对这棵树进行后序遍历会生成后缀表示法 “3 2 + 5 *”，这对于基于堆栈的求值非常有用。中序遍历会产生中缀表达式，但可能需要括号来恢复正确的顺序，除非树本身已经体现了顺序。

9. Using Trees for Huffman Coding | 利用树进行哈夫曼编码

Huffman coding is a compression technique that assigns variable-length codes to characters based on their frequencies. It builds a binary tree where each leaf represents a character and its frequency (or weight). The tree is constructed by repeatedly merging the two nodes with the smallest frequencies until only one root remains. The path from root to a leaf determines the code: left edge is usually 0, right edge is 1.

哈夫曼编码是一种根据字符频率分配可变长度编码的压缩技术。它构建一棵二叉树，其中每个叶节点代表一个字符及其频率（或权重）。通过反复合并频率最小的两个节点来构建这棵树，直到只剩下一个根节点。从根到叶节点的路径决定了编码：通常左边为 0，右边为 1。

Huffman trees allow you to derive the optimal prefix code (no code is a prefix of another) for a given set of frequencies. You may be required to construct a Huffman tree from a frequency table and then write the binary codes for each character. This topic often appears in the context of data compression and encoding schemes.

哈夫曼树使你能够为给定的一组频率推导出最优前缀编码（没有编码是另一个编码的前缀）。你可能会被要求根据频率表构建一棵哈夫曼树，然后写出每个字符的二进制编码。这个主题经常出现在数据压缩和编码方案的背景下。

10. Binary Tree Search vs. Linear Search | 二叉树搜索与线性搜索

One of the key benefits of a binary search tree is its search efficiency compared to linear search in an array. In a balanced BST, the search time is O(log n), meaning the number of comparisons grows logarithmically with the number of nodes. In contrast, linear search on an unsorted list takes O(n) time. However, if the BST becomes unbalanced (e.g., inserting sorted data sequentially), it degenerates into a linked list with O(n) search time.

二叉搜索树的一个主要优点是，与数组中的线性搜索相比，其搜索效率更高。在一个平衡的二叉搜索树中，搜索时间复杂度为 O(log n)，即比较次数随着节点数量的增加呈对数增长。相比之下，在未排序列表上进行线性搜索需要 O(n) 时间。然而，如果二叉搜索树变得不平衡（例如，按顺序插入已排序的数据），它就会退化为一个链表，搜索时间复杂度为 O(n)。

In exam questions, you might need to compare the number of steps required to find a value in a BST versus a standard array. For example, searching for 50 in a tree of 16 nodes where it is a leaf might take up to 4 comparisons in a balanced BST, but could take up to 16 in an array. Understanding the worst-case and average-case scenarios is important.

在考试题中，你可能需要比较在二叉搜索树和标准数组中查找一个值所需的步骤数。例如，在一个有 16 个节点的树中搜索 50（它是一个叶节点），在平衡二叉搜索树中最多需要 4 次比较，但在数组中可能需要 16 次。理解最坏情况和平均情况非常重要。

11. Checking and Drawing Trees | 树的检查与绘制

Drawing trees correctly from a given data set or traversal sequence is a common exam task. When constructing a BST, insert nodes one by one, always comparing with the root and moving left or right accordingly, attaching the new node as a leaf. When given two traversals (e.g., in-order and pre-order), you can reconstruct a unique binary tree. Start by identifying the root (first element in pre-order), then split the in-order sequence into left and right subtrees.

根据给定的数据集或遍历序列正确绘制树是常见的考试任务。在构建二叉搜索树时，逐个插入节点，始终与根进行比较，并相应地向左或向右移动，将新节点作为叶子添加。当给出两种遍历（例如，中序和前序）时，你可以重建一棵唯一的二叉树。首先确定根（前序中的第一个元素），然后将中序序列分割为左子树和右子树。

Always check that the tree you draw obeys the BST property (if applicable) or the given expression tree conventions. Label nodes clearly and indicate null pointers if required. In traversal questions, show your working by listing the nodes in the order they are visited.

务必检查你绘制的树是否符合二叉搜索树的性质（如果适用）或给定的表达式树约定。清楚地标记节点，如果需要，标出空指针。在遍历题目中，通过按访问顺序列出节点来展示你的工作过程。

12. Common Mistakes and Exam Tips | 常见错误与考试技巧

Many students confuse the three traversal methods, especially under time pressure. Use mnemonics: pre-order means ‘visit first’, in-order means ‘visit in the middle’, post-order means ‘visit last’. Another pitfall is misidentifying leaf nodes or counting depth incorrectly (edges vs. nodes). Always read the question carefully to see which definition is expected. When tracing recursive algorithms, simulate the stack manually with a clear diagram.

许多学生容易混淆三种遍历方法，尤其是在时间紧迫的情况下。可以使用助记法：前序意味着“先访问”，中序意味着“中间访问”，后序意味着“最后访问”。另一个常犯的错误是错误识别叶节点或深度计算错误（边与节点）。务必仔细阅读题目，确认期望的定义。在跟踪递归算法时，用一个清晰的图表手动模拟堆栈。

Practice writing pseudocode for tree traversal, searching, and inserting nodes. Be comfortable with null pointer checks. If a question asks you to describe an algorithm, use structured English or bullet points, and always mention the base case. In addition, remember that a tree is a connected, acyclic graph – so no cycles or disconnected parts exist. This can help you identify invalid structures.

练习编写树遍历、搜索和插入节点的伪代码。要熟悉空指针检查。如果题目要求描述一个算法，使用结构化英语或要点形式，并始终提及基本情形。此外，请记住树是一个连通的、无环的图——因此不存在循环或断开部分。这可以帮助你识别无效的结构。

Always review the keywords from the specification: binary tree, binary search tree, traversal, root, child, leaf, subtree, expression tree, Huffman tree. Using precise terminology earns marks in written answers. Finally, when comparing search algorithms, link your answer to efficiency and provide a brief example with numbers to demonstrate understanding.

始终复习大纲中的关键词：二叉树、二叉搜索树、遍历、根、子节点、叶节点、子树、表达式树、哈夫曼树。使用精确的术语可以在书面答案中获得分数。最后，在比较搜索算法时，将你的答案与效率联系起来，并提供一个简短的带数字的例子来展示理解。

Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Trees in IGCSE AQA Computer Science | IGCSE AQA 计算机：树 考点精讲