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

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

A tree is one of the most important non-linear data structures in GCSE Computer Science. Understanding trees helps you solve problems involving hierarchies, efficient searching, and organising data in a logical way. This revision guide covers all the key points you need for the exam, from terminology to traversal and applications.

树是 GCSE 计算机科学中最重要的非线性数据结构之一。理解树可以帮助你解决涉及层次结构、高效搜索以及以逻辑方式组织数据的问题。本考点精讲涵盖了你考试所需的所有关键知识点，从术语到遍历再到实际应用。

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

A tree is a hierarchical data structure made up of nodes connected by edges. It has no cycles, and the nodes are arranged in levels with a single node at the top.

树是一种分层的数据结构，由通过边连接的节点组成。它没有环，节点按层次排列，顶端只有一个节点。

In a tree, each node can have zero or more child nodes, but every node (except the root) has exactly one parent. This parent-child relationship is what gives the structure its branching, tree-like appearance.

在一棵树中，每个节点可以有零个或多个子节点，但每个节点（根节点除外）恰好有一个父节点。这种父子关系赋予结构分叉的、形如树木的外观。

Trees are often compared to real-life trees that grow downwards: the root is at the top, branches spread out, and leaves are at the bottom.

人们常把树比作倒过来的真实树木：根在最顶部，枝条向外伸展，叶子在最底部。

2. Basic Terminology | 基本术语

You must be familiar with the following terms to describe trees accurately in the exam.

要想在考试中准确描述树，你必须熟悉以下术语。

Node – an element in a tree that holds data. / 节点 – 树中存储数据的元素。
Edge – a connection between two nodes. / 边 – 两个节点之间的连接。
Root – the topmost node with no parent. / 根 – 最顶端的节点，没有父节点。
Parent – a node that has child nodes connected below it. / 父节点 – 拥有子节点的上层节点。
Child – a node directly connected below another node. / 子节点 – 直接连接在另一个节点下方的节点。
Leaf (or external node) – a node with no children. / 叶节点（或外部节点）– 没有子节点的节点。
Subtree – any node and all its descendants form a smaller tree inside the main tree. / 子树 – 任一节点及其所有后代构成主树中的一棵小树。
Depth – the length of the path from the root to a given node (root is at depth 0). / 深度 – 从根到指定节点的路径长度（根的深度为 0）。
Height – the length of the longest path from the root to any leaf. / 高度 – 从根到任意叶节点的最长路径长度。

3. Binary Trees | 二叉树

A binary tree is a special type of tree where each node has at most two children, typically called the left child and the right child.

二叉树是一种特殊的树，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

Binary trees are the foundation of many advanced data structures. They can be used to represent arithmetic expressions, decision processes, and efficient searching algorithms.

二叉树是许多高级数据结构的基础。它们可以用来表示算术表达式、决策过程以及高效的搜索算法。

In a strict (or proper) binary tree, every node has either 0 or 2 children. In a complete binary tree, all levels are completely filled except possibly the last, and the last level is filled from left to right.

在严格（或正则）二叉树中，每个节点要么有 0 个要么有 2 个子节点。在完全二叉树中，除最后一层外所有层均被填满，且最后一层从左向右填充。

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

A binary search tree is an ordered binary tree that follows a strict rule: for any given node, all values in its left subtree are smaller (or equal), and all values in its right subtree are larger.

二叉搜索树是一种有序二叉树，它遵循严格的规则：对于任意给定的节点，其左子树中的所有值均小于（或等于）该节点，右子树中的所有值均大于该节点。

This property makes searching very fast. When you look for a value, you start at the root and decide whether to go left or right, cutting the search space roughly in half each time.

这一特性使得搜索速度非常快。当你查找某个值时，从根开始，决定向左或向右，每次大约将搜索空间减半。

Insertion and deletion in a BST must maintain the ordering rule. The average time complexity for search, insert, and delete operations in a balanced BST is O(log n), but in the worst case (an unbalanced tree) it degrades to O(n).

在 BST 中插入和删除节点必须维持排序规则。在平衡的 BST 中，查找、插入和删除操作的平均时间复杂度为 O(log n)，但在最坏情况下（不平衡的树）会退化为 O(n)。

5. Tree Traversal | 树的遍历

Traversing a tree means visiting each node in a specific order. For GCSE you need to know three depth-first traversals for binary trees.

遍历树意味着按特定顺序访问每个节点。在 GCSE 中，你需要了解二叉树的三种深度优先遍历。

In preorder traversal, you visit the root first, then recursively traverse the left subtree, then the right subtree. Memory aid: Root, Left, Right.

在前序遍历中，首先访问根节点，然后递归遍历左子树，最后遍历右子树。记忆方法：根、左、右。

In inorder traversal, you recursively traverse the left subtree first, then visit the root, then traverse the right subtree. For a BST, this produces nodes in ascending order. Memory aid: Left, Root, Right.

在中序遍历中，先递归遍历左子树，然后访问根节点，再遍历右子树。对于 BST，中序遍历会按升序输出节点。记忆方法：左、根、右。

In postorder traversal, you recursively traverse the left subtree, then the right subtree, and finally visit the root. Memory aid: Left, Right, Root.

在后序遍历中，先递归遍历左子树，然后遍历右子树，最后访问根节点。记忆方法：左、右、根。

For example, consider a tree where root A has left child B and right child C. B has left D and right E. The preorder traversal yields:

例如，考虑一棵树：根 A 有左子 B 和右子 C，B 有左子 D 和右子 E。其前序遍历结果为：

A, B, D, E, C

Inorder produces: D, B, E, A, C. Postorder produces: D, E, B, C, A.

中序遍历结果为：D, B, E, A, C。后序遍历结果为：D, E, B, C, A。

6. Applications of Trees | 树的应用

Trees appear in many real-world computing contexts. Recognising these helps you appreciate why trees are studied.

树出现在许多现实世界的计算场景中。了解这些有助于理解为什么要学习树。

File systems – folders contain subfolders and files, forming a natural tree hierarchy. / 文件系统 – 文件夹包含子文件夹和文件，构成自然的树形层次。
HTML DOM – the structure of a web page is a tree where elements are nested inside each other. / HTML DOM – 网页的结构是一棵树，元素相互嵌套。
Expression trees – used in compilers to represent arithmetic expressions like (3+2)×(7-5), with operators as internal nodes and operands as leaves. / 表达式树 – 编译器中用于表示算术表达式如 (3+2)×(7-5)，运算符作为内部节点，操作数作为叶节点。
Network routing – spanning trees help find efficient paths without loops. / 网络路由 – 生成树帮助找到无环的高效路径。
Artificial intelligence – game trees represent possible moves in strategy games. / 人工智能 – 博弈树表示策略游戏中可能的走法。
Organisational charts – company structures often modelled as trees. / 组织结构图 – 公司结构常用树来建模。

7. Representing Trees | 树的表示

In a computer program, trees can be represented using nodes that contain data and links (pointers) to other nodes.

在计算机程序中，树可以使用包含数据以及指向其他节点的链接（指针）的节点来表示。

The most common representation uses objects with at least two fields: one for the data and one or more for child references. In a binary tree, each node typically has ‘left’ and ‘right’ references.

最常见的表示方法使用对象，至少包含两个字段：一个用于数据，一个或多个用于子节点引用。在二叉树中，每个节点通常有 ‘left’ 和 ‘right’ 两个引用。

Trees can also be stored in arrays, especially for complete binary trees. If a node is at index i, its left child is at 2i+1 and its right child at 2i+2 (using zero-based indexing). This approach is used in heaps.

树也可以存储在数组中，尤其是完全二叉树。如果节点位于索引 i 处，其左子节点位于 2i+1，右子节点位于 2i+2（基于零的索引）。这种方法用于堆结构中。

8. Trees vs Graphs | 树与图的区别

GCSE exams sometimes ask you to compare trees with general graphs. Both are collections of nodes and edges, but there are key differences.

GCSE 考试有时会要求你比较树和一般的图。两者都是节点和边的集合，但存在关键区别。

A tree is an undirected graph that is connected and has no cycles. A graph can have cycles and may even be disconnected. Every tree is a graph, but not every graph is a tree.

树是无向连通且无环的图。图可以有环，甚至可以不连通。每棵树都是图，但并非每个图都是树。

In a tree with n nodes, there are exactly n-1 edges. Adding just one more edge would create a cycle. A graph can have any number of edges.

在有 n 个节点的树中，恰好有 n-1 条边。再多加一条边就会产生环。图可以有任意数量的边。

9. Common GCSE Exam Questions | 常见考试题型

You are likely to see questions that test your ability to apply tree concepts rather than just recall definitions.

你可能会遇到的题目旨在测试你运用树概念的能力，而不仅是回忆定义。

Drawing a binary search tree after inserting a sequence of values, e.g., 8, 3, 10, 1, 6. Show the final tree and state the root. / 插入一系列值（如 8, 3, 10, 1, 6）后绘制二叉搜索树，展示最终树并指出根。
Performing tree traversals – given a tree diagram, write the nodes in preorder, inorder, and postorder. / 执行树的遍历 – 根据给定的树图，写出前序、中序和后序遍历的节点顺序。
Reconstructing a tree from two traversals, e.g., use preorder and inorder to draw the unique tree. / 根据两种遍历顺序重建树，例如用前序和中序绘制唯一的树。
Identifying properties – count the number of leaves, height, depth of a node, or identify whether a tree is a valid BST. / 识别属性 – 计算叶节点数、高度、节点深度，或判断一棵树是否是有效的 BST。
Describing applications – explain why a tree would be suitable for modelling a file system or an expression. / 描述应用 – 解释为什么树适合对文件系统或表达式进行建模。
Tracing a search in a BST – given a target value, list the nodes visited before finding it or deciding it is not present. / 在 BST 中追踪搜索 – 给定目标值，列出找到它或判定其不存在前访问的节点序列。

10. Summary and Revision Tips | 总结与复习建议

A tree is a hierarchical, non-linear structure with a root, branches, and leaves. Binary trees restrict children to a maximum of two, while binary search trees add an ordering rule for efficient search and retrieval.

树是一种层次化的非线性结构，拥有根、枝干和叶。二叉树将子节点数量限制为最多两个，而二叉搜索树则增加了排序规则，以实现高效的搜索和检索。

The three main traversals – preorder, inorder, and postorder – are essential tools for processing tree data. Recognising the order in which nodes are visited allows you to reconstruct trees and understand algorithm behaviour.

三种主要的遍历方法——前序、中序和后序——是处理树数据的基本工具。识别节点被访问的顺序可以帮助你重建树并理解算法行为。

When revising, practise drawing trees from sequences, performing traversals on paper, and explaining the difference between a tree and a general graph. Use mnemonics like ‘Root, Left, Right’ for preorder to avoid confusion during the exam.

复习时，请练习根据序列绘制树木、在纸上执行遍历，并解释树与一般图的区别。使用诸如“根、左、右”的口诀来记忆前序遍历，以避免考试时混淆。

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

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

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