IGCSE Edexcel Computer Science: Trees Key Points | IGCSE Edexcel 计算机：树考点精讲

📚 IGCSE Edexcel Computer Science: Trees Key Points | IGCSE Edexcel 计算机：树考点精讲

Trees are a fundamental data structure in computer science, and a firm grasp of tree concepts is essential for IGCSE Edexcel exam success. This article breaks down every must-know point – from basic terminology to binary tree traversals and binary search trees – so you can tackle any tree-related question with confidence. Whether you are visualising hierarchical data or tracing a recursive algorithm, mastering trees will sharpen your logical thinking and boost your problem-solving skills.

树是计算机科学中一种基础的数据结构，扎实掌握树的相关概念对 IGCSE Edexcel 考试至关重要。本文将拆解每个必考要点——从基本术语到二叉树的遍历以及二叉搜索树——让你能够自信应对任何与树相关的题目。无论你是在可视化层次数据还是跟踪递归算法，掌握树结构都会提升你的逻辑思维和解题能力。

1. Introduction to Trees | 树简介

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. The topmost node is called the root, and each node can have zero or more child nodes. Trees mirror real-world structures such as family trees, file systems, and organisational charts, making them an intuitive model for data that branches out in multiple directions.

树是一种非线性的层次数据结构，由通过边连接的节点组成。最顶端的节点称为根节点，每个节点可以有零个或多个子节点。树结构反映了现实世界中的组织方式，例如家谱、文件系统和组织架构图，因此非常适合用来建模具有分支关系的数据。

In Edexcel IGCSE Computer Science, you are expected to understand the properties of trees, differentiate between general trees and binary trees, perform traversals, and explain the operations of binary search trees. Questions often combine theory with pseudocode or algorithmic thinking, so always be ready to apply concepts to small worked examples.

在 Edexcel IGCSE 计算机科学中，你需要理解树的性质，区分一般树和二叉树，执行遍历操作，并解释二叉搜索树的操作。题目通常将理论与伪代码或算法思维相结合，因此务必准备好将概念应用到具体的小例子中。

2. Key Terminology | 关键术语

You must be comfortable with the precise vocabulary used to describe trees. The root is the only node with no parent. A leaf (or external node) is a node with no children. A parent node has one or more child nodes, and siblings share the same parent. An edge is the connection between a parent and a child. A path is a sequence of nodes connected by edges, and the depth of a node is the length of the path from the root to that node. The height of a tree is the maximum depth among all nodes.

你必须熟悉用于描述树的精确词汇。根节点是唯一没有父节点的节点。叶节点（或外部节点）是没有子节点的节点。父节点有一个或多个子节点，兄弟节点共享同一个父节点。边是父节点与子节点之间的连接。路径是由边连接的一系列节点，节点的深度是从根节点到该节点的路径长度。树的高度是所有节点中最大的深度。

Other important terms include subtree, which is any node together with all its descendants, and degree of a node, which is the number of children it has. A tree with a maximum degree of 2 is a binary tree. An empty tree has no nodes and is an important base case in recursive algorithms.

其他重要术语包括子树，即任一节点连同其所有后代节点；以及节点的度，指该节点拥有的子节点数。最大度为 2 的树称为二叉树。空树没有节点，是递归算法中的重要基例。

Remembering these terms is not just for definitions – exam questions often ask you to label nodes or identify relationships, and a single misused term can lead to lost marks.

记住这些术语不仅是为了应付定义题——考试中常要求你标注节点或识别关系，一个用错的术语就可能导致失分。

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. This structure forms the basis of many efficient search and sort algorithms. In an exam, you will mostly encounter binary trees, so it is vital to internalise their properties and traversal patterns.

二叉树是一种每个节点最多有两个子节点（称为左子节点和右子节点）的树。这种结构构成了许多高效搜索和排序算法的基础。考试中你遇到的大多是二叉树，因此必须牢记其性质和遍历模式。

A full binary tree is one where every node has either 0 or 2 children. A complete binary tree is one where all levels are completely filled except possibly the last, and in the last level nodes are as far left as possible. Although these specific variations are rarely tested in depth, understanding them helps when discussing binary heaps or efficient storage.

满二叉树是指每个节点要么有 0 个子节点，要么有 2 个子节点的二叉树。完全二叉树是指除最后一层外所有层均完全填满，且最后一层的节点尽可能靠左的二叉树。虽然这些具体变体很少深入考查，但理解它们有助于讨论二叉堆或高效存储。

Binary trees are typically implemented using nodes that contain data and pointers (or references) to left and right children. In pseudocode, a node might be defined as a record with fields: data, leftChild, rightChild.

二叉树通常通过包含数据以及指向左、右子节点的指针（或引用）的节点来实现。在伪代码中，节点可定义为一个具有 data、leftChild 和 rightChild 字段的记录。

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

Traversing a tree means visiting each node systematically. For binary trees, there are three depth-first traversal methods: pre-order, in-order, and post-order. The order of visiting the root relative to the left and right subtrees defines each method. Edexcel expects you to trace these traversals on given trees and to recognise the output sequence.

遍历树意味着系统地访问每个节点。对于二叉树，有三种深度优先遍历方法：前序遍历、中序遍历和后序遍历。访问根节点相对于左子树和右子树的顺序定义了每种方法。Edexcel 要求你能够对给定树进行遍历跟踪，并识别输出序列。

All three traversals are recursive by nature: visit the current node (or not), then recursively traverse the left subtree, then recursively traverse the right subtree. The difference lies in when the current node is processed. A simple way to remember is using the abbreviations V, L, R (Visit node, visit Left subtree, visit Right subtree). Pre-order is VLR; in-order is LVR; post-order is LRV.

这三种遍历本质上都是递归的：访问当前节点（或不访问），然后递归遍历左子树，再递归遍历右子树。区别在于何时处理当前节点。一个简单的记忆方法是使用缩写 V、L、R（访问节点、访问左子树、访问右子树）。前序遍历为 VLR；中序遍历为 LVR；后序遍历为 LRV。

Exam questions frequently provide a diagram of a binary tree and ask you to list the nodes in a specified traversal order. You must be able to do this quickly and accurately. Alternatively, you may be given an output sequence and asked to determine which traversal was used.

考试题目经常给出一个二叉树的图，要求你按指定遍历顺序列出节点。你必须能够快速、准确地完成。或者，也可能给出一个输出序列，让你判断使用了哪种遍历方式。

5. Pre-order Traversal | 前序遍历

In pre-order traversal, the root is visited first, then the left subtree is traversed in pre-order, and finally the right subtree is traversed in pre-order. This means you write down the current node’s value as soon as you encounter it, before exploring its children.

在前序遍历中，首先访问根节点，然后以前序方式遍历左子树，最后以前序方式遍历右子树。这意味着你一旦遇到当前节点，就立即写下它的值，然后再探索其子节点。

Pre-order is useful for creating a copy of a tree or generating a prefix (Polish) notation for an expression tree. When you manually trace pre-order, you can think of walking around the tree and visiting the node the first time you pass it on the left side.

前序遍历对于复制树或为表达式树生成前缀（波兰）表示法非常有用。当手动跟踪前序遍历时，你可以想象在树周围行走，并在第一次从左侧经过该节点时访问它。

For a small tree, let’s say Traversal order: write root, then traverse left subtree fully, then right subtree. Practice with a simple tree: root A, left child B, right child C. Pre-order gives A, B, C. If B had a left child D, you would get A, B, D, C.

对于一棵小树，遍历顺序是先写根节点，然后完全遍历左子树，再遍历右子树。用一棵简单的树练习：根节点 A，左子节点 B，右子节点 C。前序遍历结果为 A、B、C。如果 B 有左子节点 D，那么结果就是 A、B、D、C。

6. In-order Traversal | 中序遍历

In-order traversal visits the left subtree first, then the root node, then the right subtree. This produces a sequence that, for a binary search tree, yields the nodes in ascending order. It is the most common traversal for outputting sorted data from a BST.

中序遍历首先访问左子树，然后访问根节点，再访问右子树。对于二叉搜索树，这样产生的序列是按升序排列的节点。这是从 BST 输出有序数据的最常用遍历方式。

The algorithm is: recursively traverse left subtree, process current node, recursively traverse right subtree. In pseudocode, it is often expressed as:

算法如下：递归遍历左子树，处理当前节点，递归遍历右子树。在伪代码中常表示为：

PROCEDURE InOrder (node)
IF node IS NOT NULL THEN
CALL InOrder (node.left)
OUTPUT node.data
CALL InOrder (node.right)
ENDIF
END PROCEDURE

Using the same simple tree A (B, C), in-order gives B, A, C. If B has left child D and right child E, the in-order traversal becomes D, B, E, A, C. Always remember: left, then current, then right.

使用同一棵简单树 A (B, C)，中序遍历结果为 B、A、C。如果 B 有左子节点 D 和右子节点 E，则中序遍历变为 D、B、E、A、C。始终记住：先左，再当前，再右。

7. Post-order Traversal | 后序遍历

Post-order traversal visits the left subtree, then the right subtree, and finally the root node. This means children are processed before their parent. It is especially useful for deleting a tree or evaluating expression trees, where you need to compute operands before applying an operator.

后序遍历先访问左子树，再访问右子树，最后访问根节点。这意味着子节点会在其父节点之前被处理。这对于删除树或计算表达式树特别有用，因为在应用运算符之前需要先计算操作数。

The recursive pattern is: traverse left, traverse right, visit root. For tree A (B, C), post-order gives B, C, A. If B had left child D and right child E, post-order yields D, E, B, C, A. Notice that the root always appears last.

递归模式为：遍历左子树，遍历右子树，访问根。对于树 A (B, C)，后序遍历结果为 B、C、A。如果 B 有左子节点 D 和右子节点 E，后序遍历结果为 D、E、B、C、A。注意根节点总是最后出现。

In the Edexcel exam, you might be asked to give the output of a post-order traversal or to reconstruct a tree from given traversal outputs. Knowing that post-order lists the root last is a key clue for reconstruction.

在 Edexcel 考试中，你可能会被要求给出后序遍历的输出，或者根据给定的遍历输出重建树。知道后序遍历中根节点排在最后是重建的关键线索。

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

A binary search tree is a binary tree with a special ordering property: for any node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This property allows fast search, insertion, and deletion – on average O(log n) time if the tree is balanced.

二叉搜索树是一种具有特殊排序性质的二叉树：对于任意节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。这一性质使得搜索、插入和删除操作变得很快——如果树是平衡的，平均时间复杂度为 O(log n)。

Duplicate values are typically not allowed, or are handled by a consistent rule (e.g., place equal values to the left or right). The Edexcel specification expects you to understand how to insert, search, and traverse BSTs, and to recognise that an in-order traversal will output the data in sorted order.

通常不允许重复值，或者通过一致的规则处理（例如将相等的值放在左侧或右侧）。Edexcel 考纲要求你理解如何插入、搜索和遍历 BST，并认识到中序遍历会按排序顺序输出数据。

BSTs are widely used in applications such as databases, dictionaries, and routing tables. Their main limitation is that without balancing, a degenerate tree (essentially a linked list) can form, degrading performance to O(n). While balancing is beyond IGCSE, you should know that a skewed tree is inefficient.

BST 广泛应用于数据库、字典和路由表等场景。它们的主要局限在于，如果不进行平衡，可能会形成退化树（实际上就是一个链表），导致性能下降至 O(n)。虽然平衡机制超出 IGCSE 范围，但你应该知道倾斜树的效率很低。

9. Inserting into a BST | 插入二叉搜索树

To insert a new value into a BST, you compare it with the root. If the value is less than the root, you move to the left child; if greater, move to the right child. Repeat this process recursively until you reach an empty spot (a null child), and then place the new node there.

向 BST 插入新值时，需要将其与根节点比较。如果值小于根节点，则移到左子节点；如果大于根节点，则移到右子节点。递归重复此过程，直到到达一个空位（空子节点），然后在此处放置新节点。

This recursive algorithm ensures the BST property is maintained. Pseudocode for insertion:

这个递归算法确保维持 BST 的性质。插入的伪代码：

FUNCTION Insert (node, newValue)
IF node IS NULL THEN
RETURN CREATE_NODE(newValue)
ENDIF
IF newValue < node.data THEN
node.left ← Insert (node.left, newValue)
ELSE IF newValue > node.data THEN
node.right ← Insert (node.right, newValue)
ENDIF
RETURN node
END FUNCTION

You could be asked to trace an insertion step by step, showing the state of the tree after each new number is added. Practise inserting sequences like [8,3,10,1,6,14] and draw the resulting BST.

你可能会被要求逐步跟踪插入过程，展示每次添加新数字后树的状态。练习插入序列如 [8,3,10,1,6,14] 并画出最终的 BST。

10. Searching a BST | 搜索二叉搜索树

Searching a BST exploits the ordering property. Starting at the root, compare the target value with the current node. If they match, the search is successful. If the target is smaller, go left; if larger, go right. If you reach a null pointer, the value is not in the tree.

搜索 BST 利用其排序性质。从根节点开始，将目标值与当前节点比较。如果匹配，搜索成功。如果目标值更小，则向左走；如果更大，则向右走。如果到达空指针，则说明该值不在树中。

The search algorithm is highly efficient because it discards half the remaining tree at each step. The pseudocode for a recursive search is:

搜索算法非常高效，因为每一步都会丢弃剩余树的一半。递归搜索的伪代码如下：

FUNCTION Search (node, target)
IF node IS NULL THEN
RETURN False
ELSE IF node.data = target THEN
RETURN True
ELSE IF target < node.data THEN
RETURN Search (node.left, target)
ELSE
RETURN Search (node.right, target)
ENDIF
END FUNCTION

Exam questions often ask you to trace a search for a particular value, listing the nodes visited in order. This tests your understanding of the BST property. Always remember: the path you take is determined by the comparisons at each node.

考试题目常要求你跟踪对某个特定值的搜索过程，按顺序列出访问的节点。这考查你对 BST 性质的理解。永远记住：你走过的路径由每个节点的比较结果决定。

11. Applications of Trees | 树的应用

Trees appear throughout computing. File systems are hierarchical trees where directories are parent nodes and files are leaves. Expression trees represent arithmetic expressions, with operators as internal nodes and operands as leaves; evaluating an expression tree via post-order traversal produces the correct computation sequence.

树在计算领域随处可见。文件系统是层次树，目录是父节点，文件是叶节点。表达式树表示算术表达式，运算符作为内部节点，操作数作为叶节点；通过后序遍历计算表达式树可以得到正确的运算顺序。

Another key application is the binary heap (a complete binary tree) used for priority queues. While not a BST, a heap satisfies a different ordering: in a max-heap, a parent is greater than its children. Heaps underpin efficient sorting algorithms like heapsort.

另一个关键应用是二叉堆（一种完全二叉树），用于实现优先队列。堆虽然不是 BST，但满足另一种排序：在最大堆中，父节点大于其子节点。堆支撑了堆排序等高效排序算法。

Trees also form the backbone of network routing algorithms, decision trees in artificial intelligence, and syntax trees in compilers. Recognizing these real-world connections helps solidify abstract concepts and can be useful for extended answer questions.

树也是网络路由算法、人工智能中的决策树和编译器中的语法树的支柱。认识这些现实世界的联系有助于巩固抽象概念，对回答扩展题也很有用。

12. Past Paper Tips | 真题技巧

Edexcel IGCSE tree questions tend to follow predictable patterns. Common tasks include: (a) labelling root, leaves, and siblings on a diagram; (b) completing a binary tree given some nodes; (c) writing down the order of nodes for a specified traversal; (d) building a BST from a list of numbers and then traversing it; (e) tracing search or insertion pseudocode.

Edexcel IGCSE 的树问题往往有规律可循。常见任务包括：(a) 在图上标注根节点、叶节点和兄弟节点；(b) 根据给定节点补全二叉树；(c) 写出指定遍历的节点顺序；(d) 根据一组数字构建 BST 然后遍历它；(e) 跟踪搜索或插入伪代码。

Always read the question carefully – if it says ‘in-order’ but you produce ‘pre-order’, even a perfect traversal is worthless. Double-check your sequences by comparing with the tree diagram. When drawing a tree from insertion order, insert the numbers exactly as they appear in the list, one by one.

务必仔细审题——如果题目要求“中序”而你给出了“前序”，即使遍历完全正确也无用。通过与树图比较来复查你的序列。当根据插入顺序画树时，严格按列表中出现的数字逐一插入。

If you are asked to write or complete pseudocode for a tree algorithm, pay attention to recursion base cases (node is NULL) and the order of left/right calls. Marks are awarded for correct logic, even if syntax is not perfect. Use indentation clearly.

如果要求你编写或补全树算法的伪代码，注意递归基例（节点为 NULL）以及左右调用的顺序。即使语法不完全正确，逻辑正确也能得分。使用清晰的缩进。

Finally, practise with a variety of shapes – balanced trees, left-skewed, right-skewed – so you are not thrown off by an unusual structure in the exam.

最后，练习各种形状的树——平衡树、左倾树、右倾树——这样在考试中遇到不寻常的结构就不会慌乱。

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

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

IGCSE Edexcel Computer Science: Trees Key Points | IGCSE Edexcel 计算机：树 考点精讲