IGCSE Computer Science: Trees Revision Guide | IGCSE 计算机：树考点精讲

📚 IGCSE Computer Science: Trees Revision Guide | IGCSE 计算机：树考点精讲

In IGCSE Computer Science, the tree is a fundamental non-linear data structure that models hierarchical relationships. Understanding trees—especially binary trees and binary search trees—is essential for solving problems involving data organisation, searching, and expression evaluation. This revision guide will walk you through key concepts, terminology, representations, traversals, and real-world applications, all aligned with the syllabus requirements.

在 IGCSE 计算机科学中，树是一种基本的非线性数据结构，用于模拟层次关系。理解树（尤其是二叉树和二叉搜索树）对于解决涉及数据组织、搜索和表达式求值的问题至关重要。本复习指南将带你梳理核心概念、术语、表示方法、遍历算法及实际应用，紧扣大纲要求。

1. What is a Tree Data Structure? | 什么是树数据结构？

A tree is a collection of nodes connected by edges. It is a hierarchical structure with a single root node at the top, from which all other nodes descend. Unlike arrays or linked lists, a tree does not store data in a linear sequence; instead, it reflects parent-child relationships. A tree must not contain any cycles, making it a connected acyclic graph. Trees are used to represent file systems, organisational charts, and decision processes.

树是由节点通过边连接而成的集合。它是一种层次结构，顶部只有一个根节点，其他所有节点都从根节点派生。与数组或链表不同，树不以线性顺序存储数据，而是体现父子关系。树不能包含任何环，因此它是一幅连通的无环图。树被用来表示文件系统、组织架构图和决策过程。

2. Tree Terminology | 树的基本术语

To work with trees, you must be familiar with these terms: Root – the topmost node; Edge – the link between two nodes; Parent – a node that has one or more children; Child – a node directly connected to another node when moving away from the root; Siblings – nodes that share the same parent; Leaf (or external node) – a node with no children; 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 – a node together with all its descendants forms a subtree.

为了使用树，你必须熟悉以下术语：根(Root) – 最顶端的节点；边(Edge) – 两个节点之间的连接；父节点(Parent) – 拥有一个或多个子节点的节点；子节点(Child) – 从根往外看，与另一节点直接相连的节点；兄弟节点(Siblings) – 共享同一个父节点的节点；叶节点(Leaf)（或外部节点） – 没有子节点的节点；深度(Depth) – 从根到该节点的边数；高度(Height) – 从该节点到最远叶节点的最长路径上的边数；树的高度即根的高度；子树(Subtree) – 一个节点及其所有后代节点构成一棵子树。

English Term	中文术语	Example / 示例
Root	根	A (start node)
Edge	边	A → B
Leaf	叶节点	Node with no children
Depth	深度	Root depth = 0
Height	高度	Leaf height = 0

3. Binary Trees | 二叉树

A binary tree is a special type of tree in which each node has at most two children, referred to as the left child and the right child. Even if a node has only one child, the position (left or right) matters. A binary tree can be empty. Full, complete, and perfect binary trees describe specific structural properties: a full binary tree has every node with either 0 or 2 children; a complete binary tree is filled left to right at every level, except possibly the last; a perfect binary tree has all leaf nodes at the same depth and every internal node has two children.

二叉树是一种特殊的树，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。即使一个节点只有一个子节点，位置（左或右）也是重要的。二叉树可以为空。满二叉树、完全二叉树和完美二叉树描述了特定的结构性质：满二叉树的每个节点要么有 0 个要么有 2 个子节点；完全二叉树除了可能的最后一层外，每一层都从左到右填满；完美二叉树的所有叶节点都在同一深度，且每个内部节点都有两个子节点。

In the IGCSE syllabus, you need to recognise and draw binary trees, identify their properties, and understand how they differ from general trees. Applications include expression trees (e.g. (3 + 5) × 2), Huffman coding trees for compression, and binary search trees for efficient searching.

在 IGCSE 大纲中，你需要识别并画出二叉树，掌握其性质，并理解它们与普通树的区别。应用包括表达式树（如 (3 + 5) × 2）、用于压缩的哈夫曼编码树，以及用于高效搜索的二叉搜索树。

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

A binary search tree (BST) is a binary tree that follows an ordering invariant: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger (or equal, depending on the convention). This property makes searching extremely efficient, with an average time complexity of O(log n) if the tree is balanced. Insertion and deletion also follow this rule. To search for a value, start at the root: if the target equals the root, you have found it; if smaller, move to the left child; if larger, move to the right child. Repeat until found or a leaf is reached.

二叉搜索树 (BST) 是一种遵循排序不变量的二叉树：对于任意节点，其左子树中的所有值都更小，右子树中的所有值都更大（或相等，取决于约定）。这一性质使得搜索非常高效，在树平衡的情况下平均时间复杂度为 O(log n)。插入和删除操作也遵循这一规则。搜索一个值时，从根开始：如果目标值等于根，则找到；如果更小，则移至左子节点；如果更大，则移至右子节点。重复操作直至找到或到达叶节点。

Example BST built from inserting 8, 3, 10, 1, 6, 14, 4, 7 in order:

按顺序插入 8, 3, 10, 1, 6, 14, 4, 7 后构建的 BST 示例：

8 (root) → left: 3, right: 10; 3 → left: 1, right: 6; 6 → left: 4, right: 7; 10 → right: 14. In-order traversal of this BST yields sorted data: 1, 3, 4, 6, 7, 8, 10, 14.

5. Representing Trees: Array Implementation | 树的表示：数组实现

A binary tree can be stored in an array by using index calculations. Typically, the root is placed at index 0 (or 1). For a node at index i (assuming 0-based indexing), its left child is at 2i + 1, its right child at 2i + 2, and its parent at ⌊(i-1)/2⌋. This method works well for complete or perfect binary trees because there are no gaps. For sparse or unbalanced trees, however, it wastes memory with many empty slots. The array representation is commonly used in the heap data structure (a special complete binary tree).

二叉树可以通过下标计算存入数组。通常根节点放在索引 0（或 1）处。对于索引为 i 的节点（假设从 0 开始），其左子节点位于 2i + 1，右子节点位于 2i + 2，父节点位于 ⌊(i-1)/2⌋。这种方法非常适合完全二叉树或完美二叉树，因为没有空隙。然而，对于稀疏或不平衡的树，它会浪费很多空位内存。数组表示常用于堆数据结构（一种特殊的完全二叉树）。

IGCSE exam questions may ask you to fill in an array from a given binary tree diagram, or to draw the tree from an array representation. Always check whether indexing starts at 0 or 1.

IGCSE 考题可能会要求你根据给定的二叉树图填充数组，或根据数组表示画出树。请务必确认索引是从 0 还是 1 开始。

6. Representing Trees: Linked List Implementation | 树的表示：链表实现

In the linked representation, each node is an object that contains a data field and two pointers (references): left and right. The root pointer points to the top node. A leaf node has both pointers set to null (or None). This dynamic structure allocates memory only for existing nodes, making it memory-efficient for arbitrary binary trees. However, it requires extra space for the pointers. Most real-world tree implementations in programming use this node-based approach.

在链表表示中，每个节点都是一个对象，包含一个数据域和两个指针（引用）：左指针和右指针。根指针指向顶端节点。叶节点的两个指针都设为 null（或 None）。这种动态结构仅为存在的节点分配内存，因此对任意二叉树而言更节省空间。但它需要额外的指针空间。编程中大多数实际的树实现都采用这种基于节点的方式。

Below is a simple pseudocode for a binary tree node structure:

以下是一个二叉树节点结构的简单伪代码：

TYPE Node
DECLARE data : INTEGER
DECLARE left : POINTER TO Node
DECLARE right : POINTER TO Node
ENDTYPE

7. Tree Traversals: Pre-order | 树的遍历：前序

Traversal means visiting every node in a tree exactly once. In pre-order traversal, you visit the current node first, then recursively traverse the left subtree, then the right subtree. The order is: Root → Left → Right. Pre-order is used to create a copy of the tree, or to output a prefix expression (Polish notation) from an expression tree.

遍历意味着恰好访问树中的每个节点一次。在前序遍历中，你先访问当前节点，然后递归遍历左子树，再遍历右子树。顺序为：根 → 左 → 右。前序用于复制一棵树，或从表达式树输出前缀表达式（波兰表示法）。

For the BST used earlier (8, 3, 10, 1, 6, 14, 4, 7), the pre-order traversal would be: 8, 3, 1, 6, 4, 7, 10, 14. Pseudocode:

对于前面用过的 BST (8, 3, 10, 1, 6, 14, 4, 7)，前序遍历的结果为：8, 3, 1, 6, 4, 7, 10, 14。伪代码：

PROCEDURE PreOrder(node)
IF node ≠ null THEN
OUTPUT node.data
PreOrder(node.left)
PreOrder(node.right)
ENDIF
ENDPROCEDURE

8. Tree Traversals: In-order | 树的遍历：中序

In-order traversal visits the left subtree first, then the current node, then the right subtree: Left → Root → Right. For a binary search tree, in-order traversal yields the data in ascending (sorted) order. This is one of the most important properties of BSTs and is often tested. In-order is also used to produce infix notation (with parentheses if required) from an expression tree.

中序遍历先访问左子树，然后访问当前节点，再访问右子树：左 → 根 → 右。对二叉搜索树而言，中序遍历会按升序（排序）输出数据。这是 BST 最重要的性质之一，常被考查。中序也用于从表达式树生成中缀表示法（必要时加括号）。

For the same tree, in-order gives: 1, 3, 4, 6, 7, 8, 10, 14. Note the sorted output. Pseudocode is similar, with the output step placed between the two recursive calls.

对于同一棵树，中序的结果为：1, 3, 4, 6, 7, 8, 10, 14。请注意输出的有序性。伪代码类似，只是输出步骤放在两个递归调用之间。

PROCEDURE InOrder(node)
IF node ≠ null THEN
InOrder(node.left)
OUTPUT node.data
InOrder(node.right)
ENDIF
ENDPROCEDURE

9. Tree Traversals: Post-order | 树的遍历：后序

Post-order traversal visits the left subtree, then the right subtree, and finally the current node: Left → Right → Root. This traversal is useful when deleting an entire tree (you must delete children before the parent) or when evaluating an expression tree to produce postfix notation (Reverse Polish Notation). For our example BST, post-order gives: 1, 4, 7, 6, 3, 14, 10, 8.

后序遍历先访问左子树，然后右子树，最后访问当前节点：左 → 右 → 根。当需要删除整棵树（必须先删除子节点再删除父节点）或计算表达式树以生成后缀表示法（逆波兰表示法）时，这种遍历非常有用。对于我们的 BST 示例，后序结果为：1, 4, 7, 6, 3, 14, 10, 8。

The pseudocode places the output after both recursive traversals:

伪代码将输出放在两个递归遍历之后：

PROCEDURE PostOrder(node)
IF node ≠ null THEN
PostOrder(node.left)
PostOrder(node.right)
OUTPUT node.data
ENDIF
ENDPROCEDURE

You should practise writing traversal orders for small trees by hand. Exam questions may ask you to list the nodes visited in a given order, or to reconstruct a tree from two traversal sequences (typically in-order together with pre-order or post-order).

你应动手练习写出小树的遍历顺序。考试可能会要求你列出按给定顺序访问的节点，或根据两个遍历序列重建一棵树（通常是中序配合前序或后序）。

10. Real-world Applications of Trees | 树的实际应用

Trees appear in many areas of computing. File systems: directories and subdirectories form a tree structure. Organisational charts: employee hierarchies. Expression parsing: compilers build abstract syntax trees. Routing algorithms: network routing tables use tree-like structures. Decision trees: machine learning models for classification. Binary search trees: used in databases and dictionaries for fast key look-up. Heaps: priority queues for scheduling processes. Trie: a tree for efficient string searching and auto-complete.

树出现在计算机的许多领域。文件系统：目录和子目录形成树状结构。组织架构图：员工层级。表达式解析：编译器构建抽象语法树。路由算法：网络路由表使用类树结构。决策树：用于分类的机器学习模型。二叉搜索树：用于数据库和字典中的快速键值查找。堆：用于进程调度的优先级队列。字典树 (Trie)：用于高效字符串搜索和自动完成。

Understanding the core concepts of trees prepares you not only for IGCSE exams but also for more advanced topics in A-Level and beyond, such as graph theory, self-balancing trees, and data compression algorithms.

理解树的核心概念不仅为你的 IGCSE 考试做准备，也为 A-Level 及以后更高级的主题（如图论、自平衡树、数据压缩算法）打下基础。

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

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

IGCSE Computer Science: Trees Revision Guide | IGCSE 计算机：树 考点精讲