Tree Data Structure in GCSE CCEA Computer Science | GCSE CCEA 计算机：树 考点精讲

📚 Tree Data Structure in GCSE CCEA Computer Science | GCSE CCEA 计算机：树 考点精讲

A tree is a hierarchical data structure made up of nodes connected by edges. Unlike arrays or lists, trees do not store data in a linear sequence; instead they model a parent–child relationship that branches out from a single root. In the CCEA GCSE Computer Science specification, understanding trees is essential because they underpin many computing concepts such as file systems, search algorithms, and expression parsing. You are expected to know the basic terminology, the structure of binary trees, the principles of binary search trees, and the three main depth-first traversal methods.

树是一种层次化的数据结构，由节点和连接它们的边组成。与数组或列表不同，树并不按线性顺序存储数据；它模拟从单一根节点出发、不断分支的双亲——孩子关系。在 CCEA GCSE 计算机科学大纲中，理解树结构至关重要，因为它是文件系统、搜索算法和表达式解析等许多计算概念的基础。你需要掌握基本术语、二叉树的结构、二叉搜索树的原理以及三种主要的深度优先遍历方法。

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

A tree consists of a set of nodes. The topmost node is called the root. Every other node is connected by exactly one incoming edge from a parent node, and may have zero or more outgoing edges to child nodes. A node with no children is termed a leaf. Trees are non-linear and extremely versatile; they can represent hierarchies, sortable collections, and even decision processes. In exam questions you will often be shown a diagram and asked to identify the root, leaves, parent, and children.

树由一组节点构成。最顶端的节点称为根。其他每个节点都刚好有一条来自父节点的入边，并可以有零条或多条指向子节点的出边。没有子节点的节点称为叶节点。树是非线性的，用途极其广泛；它可以表示层次结构、可排序的集合，甚至是决策过程。在考试题目中，你经常会看到一幅图，并被要求指出根节点、叶节点、父节点和子节点。

2. Key Terminology | 关键术语

You must be confident with the following terms: node – a single element containing data; root – the unique node with no parent; parent – a node that has one or more children; child – a node directly connected to another node when moving away from the root; sibling – nodes that share the same parent; leaf (or external node) – a node with no children; subtree – a smaller tree formed by selecting a node and all its descendants; depth of a node – the number of edges from the root to that node; height of a tree – the maximum depth among all nodes. Exam questions frequently test these definitions through labelling exercises.

你必须熟练使用以下术语：节点——包含数据的单个元素；根——唯一没有父节点的节点；父节点——拥有一个或多个子节点的节点；子节点——从根出发向下直接连接到另一个节点的节点；兄弟节点——拥有相同父节点的节点；叶节点（或外部节点）——没有子节点的节点；子树——由某一节点及其所有后代构成的更小的树；节点的深度——从根到该节点的边数；树的高度——所有节点中的最大深度。考试经常通过标注练习来测试这些定义。

3. Binary Trees | 二叉树

A binary tree is a tree data structure 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, that child must still be designated as left or right. Binary trees are fundamental for implementing search algorithms and can be used to represent arithmetic expressions. In CCEA questions, you may be given a shape of binary tree and asked to state whether it is full, complete, or balanced, though the core requirement is to understand that each node holds a left and a right pointer.

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左孩子和右孩子。即使一个节点只有一个孩子，也必须明确是左孩子还是右孩子。二叉树是实现搜索算法的基础，也可以用来表示算术表达式。在 CCEA 的考题中，你可能需要根据二叉树的形状判断它是否为满二叉树、完全二叉树或平衡二叉树，但核心要求是理解每个节点都包含一个左指针和一个右指针。

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

A binary search tree is a special binary tree that follows a strict ordering property: for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property enables very fast search, insertion, and deletion operations. When inserting a new value into a BST, the algorithm compares the value with the current node and moves left if smaller, right if larger, until an empty position is found. CCEA papers often include questions that ask you to sketch the BST after a sequence of insertions, or to determine the steps needed to find a particular value.

二叉搜索树是一种特殊的二叉树，它遵循严格的排序性质：对于任意节点，其左子树中的所有值都比该节点小，右子树中的所有值都比该节点大。这一性质使得搜索、插入和删除操作非常迅速。当向二叉搜索树插入一个新值时，算法会将新值与当前节点比较，如果较小就向左走，如果较大就向右走，直到找到一个空位。CCEA 试卷中经常出现这样的题目：要求你在一系列插入操作后画出二叉搜索树的形状，或者确定查找某个特定值所需的步骤。

5. Tree Traversal – Preorder | 树遍历——前序遍历

Traversal means visiting every node in a tree in a systematic way. Preorder traversal visits the root first, then recursively traverses the left subtree, and finally the right subtree. This method is often used to produce a prefix (Polish) notation of an expression tree, or to create a copy of a tree. In preorder notation you record the node as soon as you encounter it. For the CCEA exam, you should be able to list the order of nodes when given a diagram and to explain the rule: Root, Left, Right (NLR).

遍历是指按照系统的方式访问树中的每一个节点。前序遍历先访问根节点，然后递归遍历左子树，最后递归遍历右子树。这种方法常用于生成表达式树的前缀表示（波兰表示法），或者复制一棵树。在前序遍历中，你一旦遇到节点就立即记录。在 CCEA 考试中，考生应能根据给出的示意图列出节点访问顺序，并能够解释规则：根、左、右（NLR）。

6. Tree Traversal – Inorder | 树遍历——中序遍历

Inorder traversal recursively visits the left subtree, then the root, and then the right subtree. This is particularly important for binary search trees because performing an inorder traversal on a BST visits the nodes in ascending order. In the exam you will often be asked to apply inorder traversal to a BST to output a sorted list of data, or to convert an algebraic expression tree into an infix expression. The rule is easy to remember: Left, Root, Right (LNR).

中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树。这对二叉搜索树尤为重要，因为对一棵二叉搜索树进行中序遍历会按升序访问节点。考试经常要求你对二叉搜索树应用中序遍历来输出一个排序列表，或者将代数表达式树转换为中缀表达式。规则很容易记住：左、根、右（LNR）。

7. Tree Traversal – Postorder | 树遍历——后序遍历

Postorder traversal recursively visits the left subtree, then the right subtree, and finally the root. This sequence is used when you need to delete all nodes from the tree (freeing children before the parent) or when converting an expression tree into postfix (Reverse Polish) notation. The CCEA specification expects you to be able to trace postorder on a given tree and to know the rule: Left, Right, Root (LRN). Some questions may ask you to compare the three traversal methods and choose the one that produces a specific output sequence.

后序遍历先递归遍历左子树，然后遍历右子树，最后访问根节点。当需要从树中删除所有节点（在删除父节点之前先释放子节点）或者需要将表达式树转换为后缀表示（逆波兰表示法）时，就会使用这种顺序。CCEA 大纲要求你能够对给定树追踪后序遍历过程，并掌握规则：左、右、根（LRN）。有些题目可能会让你比较这三种遍历方法，并选择能产生特定输出序列的那一种。

8. Expression Trees | 表达式树

An expression tree is a binary tree that represents an arithmetic or logical expression. The leaves contain operands (numbers or variables), while internal nodes contain operators. For GCSE, you may be asked to construct a tree from an infix expression, or to evaluate an expression by traversing the tree. The three traversals give different notations: preorder yields prefix, inorder yields infix (although parentheses may be required for correct interpretation), and postorder yields postfix. Understanding expression trees helps reinforce the relationship between tree traversal and real-world computing tasks like compiling arithmetic.

表达式树是一种表示算术或逻辑表达式的二叉树。叶节点包含操作数（数字或变量），内部节点包含运算符。在 GCSE 阶段，你可能会被要求根据中缀表达式构建一棵树，或者通过遍历树求值。三种遍历会产生不同的表示法：前序遍历得到前缀式，中序遍历得到中缀式（尽管可能需要括号以保证正确的解读），后序遍历得到后缀式。理解表达式树有助于巩固树遍历与实际计算任务（如算术编译）之间的联系。

9. Using Trees to Represent File Systems | 用树表示文件系统

Most operating systems use a tree structure to organise files and folders. The root directory is the top-level folder (for example, ‘C:\’ in Windows). Each folder can contain files (leaf nodes) and subfolders (internal nodes). Moving through the directory tree involves traversing from the root to the desired location. This is a practical application that CCEA often uses to illustrate why hierarchical data structures like trees are more suitable than flat lists for organising related items. A classic exam question might ask you to draw a directory tree from a list of file paths.

大多数操作系统使用树结构来组织文件和文件夹。根目录是顶层文件夹（例如 Windows 中的 C:\）。每个文件夹可以包含文件（叶节点）和子文件夹（内部节点）。在目录树中移动就相当于从根遍历到所需位置。CCEA 经常用这个实际应用来说明为什么像树这样的层次数据结构比扁平列表更适合组织相关联的项目。经典的考题可能会要求你根据一串文件路径画出目录树。

10. Applications and Exam Tips | 应用与考试技巧

Beyond expression trees and file systems, trees are used in network routing, AI game trees, decision trees, and databases (B-trees though not in depth at GCSE). When revising, focus on drawing and interpreting diagrams, applying traversal algorithms step by step, and remembering the BST insertion rule. Use a systematic approach: label the type of tree, identify the root, and for traversals keep track of visited nodes in order. Practice past paper questions where you are asked to fill in the nodes after insertion or list traversal output. Time management is key: once you understand the simple recursive patterns, these questions become straightforward marks.

除了表达式树和文件系统，树还用于网络路由、人工智能博弈树、决策树以及数据库（B 树，不过在 GCSE 阶段不作深入要求）。复习时，重点在于画图和解读示意图、逐步应用遍历算法，并牢记二叉搜索树的插入规则。采用系统化的方法：标明树的类型，确定根节点，在遍历时按顺序记录已访问节点。多做历年真题，练习插入节点后填空或列出遍历输出的题目。时间管理很关键：一旦你掌握了简单的递归模式，这些题目就变成了送分题。

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

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