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

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

In computer science, a tree is a hierarchical data structure that consists of nodes connected by edges. It is widely used in many areas such as operating systems, compilers, and databases. Understanding trees is essential for IGCSE WJEC Computer Science, particularly binary trees and their traversals.

在计算机科学中，树是一种由节点和边构成的层次数据结构。它广泛应用于操作系统、编译器和数据库等领域。理解树的概念是学习 IGCSE WJEC 计算机科学的核心内容之一，尤其是二叉树及其遍历算法。

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

A tree is a collection of entities called nodes, linked together to simulate a hierarchy. It is a non-linear data structure, unlike arrays or linked lists. A tree always has a single topmost node called the root. Every other node is connected to exactly one parent, but can have zero, one or more child nodes.

树是一组称为节点的实体的集合，它们连接在一起模拟层次结构。与数组或链表不同，树是一种非线性数据结构。树总是有一个位于最顶层的节点，称为根。其他每个节点都恰好连接到一个父节点，但可以有零个、一个或多个子节点。

2. Basic Tree Terminology | 树的基本术语

Key terms include: root (the starting node of the tree), edge (the connection between two nodes), parent and child (a node directly above is the parent; a node directly below is the child), leaf (a node with no children), sibling (nodes sharing the same parent), and subtree (a node together with all its descendants forms a subtree). 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.

关键术语包括：根（树的起始节点）、边（两个节点之间的连接）、父与子（直接在上方的节点是父节点，直接在下方的节点是子节点）、叶（没有子节点的节点）、兄弟（拥有相同父节点的节点）以及子树（一个节点连同其所有后代构成的树）。节点的深度是从根到该节点的边的数量；树的高度是所有节点深度的最大值。

3. Binary Trees | 二叉树

A binary tree is a special type of tree in which each node can have at most two children, referred to as the left child and the right child. Binary trees are the most widely used tree structure in computer science. They can be full (every node has 0 or 2 children), complete (all levels are fully filled except possibly the last, which is filled from left to right), or perfect (all internal nodes have two children and all leaves are at the same level).

二叉树是一种特殊的树，其中每个节点最多有两个子节点，分别称为左孩子和右孩子。二叉树是计算机科学中使用最广泛的树结构。它们可以是满二叉树（每个节点有 0 或 2 个孩子）、完全二叉树（除最后一层外所有层均被填满，最后一层从左到右填充）或完美二叉树（所有内部节点都有两个孩子且所有叶子在同一层）。

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

A binary search tree is an ordered binary tree where for each node, all values in its left subtree are smaller, and all values in its right subtree are larger. This ordering property makes searching very efficient. When searching for a value, you start at the root and decide whether to go left or right based on comparison, just like the binary search algorithm. Inserting a new node follows the same rule: traverse down the tree and attach the new node as a leaf in the correct position. If the tree remains balanced, search, insertion and deletion take O(log n) time on average.

二叉搜索树是一种有序二叉树，其中对于每个节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。这种有序性质使得搜索非常高效。在查找一个值时，从根开始，根据比较结果决定向左还是向右移动，这与二分查找算法的原理类似。插入新节点遵循相同的规则：向下遍历树，在正确的位置将新节点作为叶子挂载。如果树保持平衡，搜索、插入和删除的平均时间复杂度为 O(log n)。

5. Tree Traversal – Overview | 树遍历概述

Tree traversal means visiting all the nodes of a tree exactly once in a systematic way. For binary trees, there are three depth-first traversal methods: pre-order, in-order, and post-order. The names refer to when the root of a subtree is visited relative to its left and right children. These traversals are often implemented using recursion and are a core skill in the IGCSE WJEC examination.

树遍历是指按照系统化的方式恰好访问树中的每个节点一次。对于二叉树，存在三种深度优先遍历方法：前序遍历、中序遍历和后序遍历。这些名称反映了子树的根是何时相对于其左右孩子被访问的。这些遍历通常利用递归实现，是 IGCSE WJEC 考试中的核心技能。

6. Pre-order Traversal | 前序遍历

In pre-order traversal, we visit the current node first, then recursively traverse its left subtree, and finally its right subtree. The order is: root → left → right. Using a sample tree where A is the root, B is its left child and C its right child, and B has left child D and right child E, the pre-order traversal yields the sequence: A, B, D, E, C. Pre-order is useful for creating a copy of a tree or for prefix notation (Polish notation) of expressions.

在前序遍历中，我们首先访问当前节点，然后递归遍历其左子树，最后遍历其右子树。顺序为：根 → 左 → 右。以一棵示例树为例：A 是根，B 是左孩子，C 是右孩子；B 有左孩子 D 和右孩子 E。前序遍历产生的序列是：A, B, D, E, C。前序遍历对复制树或生成表达式的前缀表示（波兰表示法）很有用。

7. In-order Traversal | 中序遍历

In in-order traversal, we recursively traverse the left subtree first, then visit the current node, and finally traverse the right subtree. The order is: left → root → right. Applying this to the same sample tree A(B(D,E),C), the in-order sequence is: D, B, E, A, C. In a binary search tree, in-order traversal will visit nodes in ascending order, which is why it is used to output sorted data from a BST.

在中序遍历中，我们首先递归遍历左子树，然后访问当前节点，最后遍历右子树。顺序为：左 → 根 → 右。对同样的示例树 A(B(D,E),C) 应用中序遍历，得到的序列为：D, B, E, A, C。在二叉搜索树中，中序遍历会按升序访问节点，这就是它被用于从 BST 输出有序数据的原因。

8. Post-order Traversal | 后序遍历

In post-order traversal, we recursively traverse the left subtree, then the right subtree, and finally visit the current node. The order is: left → right → root. For the same tree, the post-order sequence is: D, E, B, C, A. Post-order traversal is particularly useful for deleting a tree (visiting children before parent) or for evaluating postfix expressions in expression trees.

在后序遍历中，我们递归遍历左子树，接着遍历右子树，最后访问当前节点。顺序为：左 → 右 → 根。对于同一棵树，后序遍历的序列是：D, E, B, C, A。后序遍历特别适用于删除树（在删除父节点之前先处理子节点）或在表达式树中计算后缀表达式。

9. Representing Trees in Programming | 在编程中表示树

In a programming language such as Python, a binary tree can be represented by creating a Node class. Each node object typically has three attributes: data (the value stored), left (a pointer to the left child node) and right (a pointer to the right child node). For a BST, the insertion function would create a new node and recursively place it according to the BST property. In examinations, you may be asked to write pseudocode for tree operations, so you must be comfortable with this representation.

在 Python 等编程语言中，二叉树可以通过创建一个 Node 类来表示。每个节点对象通常有三个属性：data（存储的值）、left（指向左孩子节点的指针）和 right（指向右孩子节点的指针）。对于 BST，插入函数会创建一个新节点并根据 BST 性质递归地放置它。在考试中，你可能会被要求编写树操作的伪代码，因此必须熟悉这种表示方法。

class Node:
   def __init__(self, data):
     self.data = data
     self.left = None
     self.right = None

10. Expression Trees | 表达式树

An expression tree is a specific binary tree used to represent arithmetic expressions. In such a tree, leaf nodes contain operands (numbers or variables), while internal nodes contain operators. For example, the expression (3 + 4) × 2 can be represented as a tree with the root ‘×’, left child ‘+’ and right child ‘2’. The ‘+’ node has left child ‘3’ and right child ‘4’. By traversing the tree in post-order, we obtain the postfix form: 3 4 + 2 ×; in-order traversal (with parentheses added) gives the infix form; pre-order traversal gives the prefix form: × + 3 4 2.

表达式树是一种特定的二叉树，用于表示算术表达式。在表达式树中，叶子节点包含操作数（数字或变量），而内部节点包含运算符。例如，表达式 (3 + 4) × 2 可以表示为根节点为 ‘×’、左孩子为 ‘+’、右孩子为 ‘2’ 的树。’+’ 节点的左孩子是 ‘3’、右孩子是 ‘4’。通过后序遍历我们得到后缀形式：3 4 + 2 ×；中序遍历（加上括号）得到中缀形式；前序遍历得到前缀形式：× + 3 4 2。

11. Common Applications of Trees | 树的常见应用

Trees are used in many real-world computing scenarios. File systems on a computer (folders and files) are organised as a tree. HTML Document Object Model (DOM) is a tree. Binary search trees enable fast searching and sorting. Decision trees are used in artificial intelligence for classification tasks. Heap data structures (which are complete binary trees) are used to implement priority queues. Compilers use abstract syntax trees and expression trees to interpret and generate code.

树在许多现实世界的计算场景中得到应用。计算机上的文件系统（文件夹和文件）就是按照树结构组织的。HTML 文档对象模型（DOM）是一棵树。二叉搜索树能够实现快速搜索和排序。人工智能中使用决策树进行分类任务。堆数据结构（属于完全二叉树）用于实现优先队列。编译器利用抽象语法树和表达式树来解释和生成代码。

12. Exam Tips for Trees | 考试技巧

For the IGCSE WJEC exam, make sure you can define key terms (root, leaf, binary tree, BST etc.), draw and label a tree from a given description, and perform pre-order, in-order and post-order traversals correctly. Practice tracing BST insertion step by step. You may also be asked to explain why a BST can give faster search than a linear list. Write traversal algorithms recursively – it is the expected approach. Always label your traversal sequence clearly.

针对 IGCSE WJEC 考试，请确保你能定义关键术语（根、叶子、二叉树、BST 等），根据描述绘制并标注树结构，并正确执行前序、中序和后序遍历。练习逐步跟踪 BST 插入的过程。你可能还需要解释为什么 BST 搜索比线性列表快。用递归方式编写遍历算法——这是预期的做法。务必清晰地标注你的遍历序列。

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

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

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