GCSE CIE Computer Science: Trees | GCSE CIE 计算机：树考点精讲

📚 GCSE CIE Computer Science: Trees | GCSE CIE 计算机：树考点精讲

A tree is a fundamental non-linear data structure used in computer science to represent hierarchical relationships. In the CIE GCSE Computer Science syllabus, you are expected to understand the concept of a tree, construct binary trees, and perform preorder, inorder, and postorder traversals. Mastering these skills is essential for success in the data structures and algorithms sections of the exam.

树是计算机科学中一种基础的非线性数据结构，用于表示层次关系。根据 CIE GCSE 计算机科学大纲，你需要理解树的概念、构建二叉树，并能进行前序、中序和后序遍历。掌握这些技能是通过数据结构和算法相关考题的关键。

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

A tree is a connected, acyclic (no cycles) graph made up of nodes and edges. It mimics a hierarchical structure by arranging elements in a parent-child relationship, with one top-level node known as the root.

树是由节点和边构成的一个连通且无环的图。它以父子关系组织元素，形成一个层次结构，其中最顶层的节点称为根。

In a tree, every node except the root has exactly one parent. Nodes can have zero or more children, and a node with no children is termed a leaf. The links between nodes are called edges.

在树中，除根节点外每个节点有且只有一个父节点。节点可以有零个或多个子节点，没有子节点的节点称为叶节点。节点之间的连线称为边。

A familiar example is a computer file system: a drive is the root, folders are internal nodes, and files are leaves. This structure makes it easy to locate, store and manage data.

常见的例子是计算机文件系统：驱动器是根，文件夹是内部节点，文件是叶。这种结构便于定位、存储和管理数据。

2. Key Terminology | 关键术语

Understanding the precise vocabulary used to describe trees is essential for both exam questions and practical problem-solving. The table below pairs each important English term with its Chinese equivalent and definition.

理解描述树所用的精确术语对于考试和实际解题都至关重要。下表将每个重要的英文术语与其中文对应及定义配对呈现。

Term (English)	中文术语	Explanation \| 解释
Root	根	The topmost node, with no parent / 最顶层节点，无父节点
Edge	边	The connection between two nodes / 连接两个节点的线
Parent	父节点	A node directly above another node / 直接位于另一个节点上方的节点
Child	子节点	A node directly below another node / 直接位于另一个节点下方的节点
Siblings	兄弟节点	Nodes sharing the same parent / 具有相同父节点的节点
Leaf	叶节点	A node with no children / 没有子节点的节点
Subtree	子树	A node and all its descendants / 一个节点及其所有后代
Depth	深度	The number of edges from the root to a node / 从根到该节点的边数
Height	高度	The maximum depth of any node in the tree / 树中任意节点的最大深度

In exam questions these terms are tested implicitly, for example when asking you to ‘identify the leaf nodes’ or ‘state the depth of the node containing 7’. Being confident with the vocabulary saves valuable time.

在考试中这些术语会隐性地考查，例如要求你“识别所有叶节点”或“指出包含 7 的节点的深度”。熟悉这些术语可以节省宝贵的时间。

3. Binary Trees | 二叉树

A binary tree is a special type of tree in which each node has at most two children, typically referred to as the left child and the right child. Even if a node has only one child, it is still designated as either a left or right child.

二叉树是一种特殊的树，每个节点最多有两个子节点，通常称为左孩子和右孩子。即使一个节点只有一个孩子，它仍然会被明确标定为左孩子或右孩子。

The structure of a binary tree makes it extremely useful for efficient searching, sorting, and representing arithmetic expressions. In the GCSE exam, you will primarily deal with binary trees rather than general trees.

二叉树的结构使其在高效搜索、排序和表示算术表达式方面非常有用。在 GCSE 考试中，你主要接触的是二叉树而非一般树。

Sometimes you may see terms like ‘full binary tree’ (every node has 0 or 2 children) or ‘complete binary tree’ (all levels are filled except possibly the last, which is filled from left to right), but you are only required to understand the basic definition and be able to draw and label binary trees.

有时你可能会看到“满二叉树”（每个节点有 0 或 2 个孩子）或“完全二叉树”（除最后一层外所有层均填满，且最后一层从左向右填充）等术语，但你只需要理解基本定义，并能够绘制和标注二叉树。

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

A binary search tree (BST) is a binary tree organised in a way that allows fast searching. For any given node, all values in its left subtree are smaller than the node’s value, and all values in its right subtree are larger.

二叉搜索树（BST）是一种组织方式便于快速搜索的二叉树。对于任意节点，其左子树中所有值都小于该节点的值，右子树中所有值都大于该节点的值。

This property means that searching for a value becomes a process of comparing and turning left or right at each node, cutting the search space in half on average. It also means that an inorder traversal of a BST will visit the nodes in ascending order.

这一性质意味着查找某个值的过程变成在每个节点进行比较并决定向左或向右，平均而言可将搜索空间减半。同时，对二叉搜索树进行中序遍历会按升序访问所有节点。

Example: inserting values 8, 3, 10, 1, 6, 14 results in the root 8; left subtree root 3 with left child 1 and right child 6; right subtree root 10 with right child 14. You must be able to build a BST from a list of numbers in the exam.

例如：依次插入 8, 3, 10, 1, 6, 14 会得到根为 8；左子树根为 3，其左孩子为 1，右孩子为 6；右子树根为 10，其右孩子为 14。考试中你必须能够根据一组数字画出二叉搜索树。

5. Representing Arithmetic Expressions as Trees | 用树表示算术表达式

Arithmetic expressions can be represented using expression trees, where internal nodes hold operators (such as +, -, ×, ÷) and leaf nodes hold operands (numbers or variables). This representation makes it easy to convert between different notations.

算术表达式可以用表达式树表示，其中内部节点存放运算符（如 +、-、×、÷），叶节点存放操作数（数字或变量）。这种表示法使不同记法之间的转换变得简单。

For example, the infix expression (3 + 4) × 5 is built by placing ‘×’ at the root, with the left child a subtree for ‘3 + 4’ and the right child the leaf ‘5’. The ‘+’ node then has children 3 and 4. Understanding this layout is key to mastering tree traversals.

例如，中缀表达式 (3 + 4) × 5 的表达式树以“×”为根，左孩子是代表“3 + 4”的子树，右孩子是叶节点“5”。“+”节点则拥有孩子 3 和 4。理解这种布局是掌握树遍历的关键。

6. Preorder Traversal | 前序遍历

Preorder traversal visits the current node before its children. The recursive algorithm is: visit the root, then traverse the left subtree in preorder, and finally traverse the right subtree in preorder.

前序遍历在访问子节点之前先访问当前节点。递归算法为：访问根节点，然后以同样的前序方式遍历左子树，最后以同样的前序方式遍历右子树。

Preorder: root → left → right

Applying this to the expression tree for (3 + 4) × 5 gives: ‘×’, then recursively left subtree ‘+’, then its left ‘3’, right ‘4’, and finally right subtree ‘5’. The output is the prefix expression: × + 3 4 5.

将其应用到 (3 + 4) × 5 的表达式树：先输出“×”，然后递归左子树“+”，再输出“3”、“4”，最后输出右子树“5”。得到的结果是前缀表达式：× + 3 4 5。

In the exam you may be asked to write down the preorder sequence for a given binary tree. Always start at the root and keep a clear record of your path.

考试中可能会要求你写出给定二叉树的前序遍历序列。务必从根开始，清晰地记录下访问路径。

7. Inorder Traversal | 中序遍历

Inorder traversal processes the left subtree first, then the current node, and finally the right subtree. This produces a sequence that for a binary search tree is always sorted in ascending order.

中序遍历先处理左子树，然后访问当前节点，最后处理右子树。对于二叉搜索树，这样产生的序列总是按升序排列。

Inorder: left → root → right

Using the same expression tree, inorder traversal returns: 3, ‘+’, 4, then back to the root ‘×’, and finally 5, giving the sequence 3 + 4 × 5. Notice this matches the original infix expression without parentheses, but operator precedence must be considered to restore the correct meaning.

对同一表达式树进行中序遍历得到：3、“+”、4，然后回到根“×”，最后 5，序列为 3 + 4 × 5。注意这正好是不带括号的原中缀表达式，但必须考虑运算符优先级才能恢复原意。

For a BST, inorder traversal is extremely useful: it outputs the data in sorted order without extra sorting algorithms. CIE questions sometimes ask you to verify whether a tree is a valid BST by checking the inorder output.

对于 BST，中序遍历非常有用：它无需额外排序算法就能按顺序输出数据。CIE 考题有时要求你通过检查中序输出验证一棵树是否为合法的 BST。

8. Postorder Traversal | 后序遍历

Postorder traversal visits children before the parent. The rule is: traverse left subtree, traverse right subtree, then visit the root. This is the natural order for deleting a tree or evaluating an expression stack.

后序遍历先访问子节点再访问父节点。规则是：遍历左子树，遍历右子树，然后访问根。这是删除树或求值表达式栈时的自然顺序。

Postorder: left → right → root

For our example, postorder visits left subtree recursively: 3, 4, ‘+’, then right subtree 5, and finally the root ‘×’, producing 3 4 + 5 ×. This is Reverse Polish Notation (RPN), widely used in stack-based calculations.

对于我们的例子，后序遍历先递归访问左子树：3、4、“+”，然后右子树 5，最后根“×”，得到 3 4 + 5 ×。这就是逆波兰记法（RPN），广泛应用于基于栈的计算。

When answering postorder questions, it helps to think from the leaves upward, leaving the root until the very end.

在回答后序遍历问题时，从叶节点开始向上思考，把根留在最后访问往往很有帮助。

9. Constructing a Binary Tree from Traversals | 根据遍历序列构建二叉树

A common higher-tier question asks you to reconstruct the original binary tree given two traversal sequences, typically preorder and inorder, or postorder and inorder.

常见的进阶考题要求你根据两个遍历序列重建原始二叉树，通常提供前序与中序，或者后序与中序。

The key idea: in preorder the first node is the root; in inorder that root separates the left and right subtrees. Similarly, in postorder the last node is the root. By iteratively finding the root and splitting the inorder sequence, you can draw the entire tree.

核心思想：在前序中第一个节点是根；在中序中该根将左右子树分开。同样，在后序中最后一个节点是根。通过反复确定根并分割中序序列，就能画出整棵树。

Example: preorder = [7, 3, 1, 5, 9, 11], inorder = [1, 3, 5, 7, 9, 11]. The root is 7; in inorder, left subtree has [1,3,5], right subtree has [9,11]. Recurse on left: root 3 (from preorder), inorder left part gives [1] and right [5]; and on right: root 9, right child 11. Practice several examples to become fluent.

示例：前序 = [7, 3, 1, 5, 9, 11]，中序 = [1, 3, 5, 7, 9, 11]。根为 7；中序里左子树为 [1,3,5]，右子树为 [9,11]。对左子树递归：根为 3（根据前序），中序左部分为 [1]，右部分为 [5]；右子树递归：根为 9，右孩子为 11。多加练习才能熟练。

10. Applications of Trees in Computing | 树在计算中的应用

Trees are not just an abstract concept; they solve real computing problems. File systems use trees to organise directories and files, enabling efficient navigation and storage.

树并不仅仅是抽象的概念，它们能解决实际的计算机问题。文件系统用树组织目录和文件，实现高效的导航与存储。

Compilers parse source code into syntax trees (parse trees) to check grammar and generate machine code. Expression trees are a simplified version of this idea.

编译器将源代码解析为语法树（分析树）以检查语法并生成机器码。表达式树是这一思想的简化版本。

Routing protocols in networks build spanning trees to prevent loops and find the shortest path. Database systems use B-trees (a variant of search trees) for indexing, allowing rapid data retrieval.

网络中的路由协议构建生成树以防止环路并寻找最短路径。数据库系统使用 B 树（搜索树的一种变体）进行索引，实现数据的快速检索。

Even artificial intelligence uses decision trees for classification and game trees (like minimax) for choosing moves. Knowing these applications helps you appreciate the significance of the topic.

甚至人工智能也使用决策树进行分类，并使用博弈树（如极小极大树）来选择走法。了解这些应用能帮助你理解本专题的重要意义。

11. Common Exam Pitfalls | 常见考试陷阱

Many students lose marks by confusing the three traversal orders. Remember that preorder processes the root first, inorder processes the root in the middle, and postorder processes the root last.

许多学生因混淆三种遍历顺序而丢分。记住：前序最先处理根，中序在

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

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

GCSE CIE Computer Science: Trees | GCSE CIE 计算机：树 考点精讲