📚 GCSE OCR Computer Science: Trees Revision Guide | GCSE OCR 计算机：树 考点精讲
A tree is a non-linear data structure that organises data in a hierarchical way. In GCSE OCR Computer Science, you need to understand what trees are, how binary trees work, and how to traverse them using pre-order, in-order, and post-order methods. You also need to be able to represent mathematical expressions as binary trees. This guide covers all the essential points you’ll be tested on.
树是一种以层次化方式组织数据的非线性数据结构。在 GCSE OCR 计算机科学中，你需要了解树是什么、二叉树如何工作，以及如何使用前序、中序和后序遍历它们。你还需要能够将数学表达式表示为二叉树。本指南涵盖了你将考查的所有要点。
1. Introduction to Trees | 树结构简介
A tree is a collection of nodes connected by edges. Unlike arrays or lists, a tree does not store data in a linear sequence. Instead, it has a root node at the top, which branches out to child nodes, forming a structure that resembles an upside-down tree. Each node may have a parent, children, and in some cases a sibling. Trees are used in many areas of computing, such as file systems, routing tables, and expression evaluation.
树是由边连接的节点集合。与数组或列表不同，树不以线性顺序存储数据。它有一个位于顶部的根节点，该节点分支到子节点，形成类似于倒置的树的结构。每个节点可以有父节点、子节点，有时还有兄弟节点。树用于计算中的许多领域，例如文件系统、路由表和表达式求值。
In computer science, a tree is defined as a connected, acyclic graph. The topmost node is called the root. Nodes that have no children are called leaves. A node with at least one child is an internal node. The relationships between nodes are described using family terminology: parent, child, sibling, ancestor, and descendant.
在计算机科学中，树被定义为连通的无环图。最顶部的节点称为根。没有子节点的节点称为叶。至少有一个子节点的节点是内部节点。节点之间的关系使用家族术语描述：父节点、子节点、兄弟节点、祖先节点和子孙节点。
2. Tree Terminology | 树的术语
Working with trees requires knowing a few key terms. The root is the starting point of the tree. An edge is the connection between two nodes. A leaf node (or terminal node) has no children. A subtree is a smaller tree that is part of a larger tree, consisting of a node and all its descendants. 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 among its nodes. The degree of a node is the number of children it has.
使用树需要了解几个关键术语。根是树的起点。边是两个节点之间的连接。叶节点（或终端节点）没有子节点。子树是较大树的一部分，由一个节点及其所有后代组成。节点的深度是从根到该节点的边数。树的高度是其节点之间的最大深度。节点的度是它拥有的子节点数量。
For example, in a typical tree the root is at depth 0. If a root has two children, each child is at depth 1. Any node in the tree can be considered the root of its own subtree. Understanding this vocabulary is essential for answering descriptive questions in the exam.
例如，在典型的树中，根位于深度 0。如果根有两个子节点，则每个子节点位于深度 1。树中的任何节点都可以被视为其自身子树的根。理解这些词汇对于回答考试中的描述性问题至关重要。
3. Binary Trees | 二叉树
A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child. This restriction makes binary trees easier to implement and traverse. Even though a node can have zero, one, or two children, the tree remains a binary tree as long as the maximum number of children per node is two.
二叉树是每个节点最多有两个子节点的树，分别称为左子节点和右子节点。这种限制使二叉树更易于实现和遍历。尽管一个节点可以有零个、一个或两个子节点，只要每个节点的最大子节点数为两个，该树仍是二叉树。
Binary trees form the basis of many data structures, such as binary search trees and expression trees. In GCSE OCR, you will encounter binary trees mainly for representing arithmetic expressions and for applying different traversal algorithms.
二叉树构成了许多数据结构的基础，例如二叉搜索树和表达式树。在 GCSE OCR 中，你遇到的二叉树主要用于表示算术表达式以及应用不同的遍历算法。
A full binary tree is one in which every node has either 0 or 2 children. A complete binary tree is one where all levels, except possibly the last, are completely filled, and all nodes are as far left as possible. While you do not need to memorise these variations, recognising them can help with traversal and visualisation.
满二叉树是每个节点都有 0 个或 2 个子节点的二叉树。完全二叉树是指除了最后一层之外的所有层都被完全填满，并且所有节点都尽可能靠左的二叉树。虽然你不需要记住这些变体，但识别它们有助于遍历和可视化。
4. Representing Expression Trees | 表达式树的表示
In arithmetic, expressions can be written in infix notation, such as (A + B) x C. A binary tree can be used to represent such expressions, making it easy to evaluate them or convert them into different notations. In an expression tree, the leaf nodes contain operands (numbers or variables), and the internal nodes contain operators (+, -, x, /).
在算术中，表达式可以用中缀表示法书写，例如 (A + B) x C。二叉树可以用来表示这样的表达式，从而更容易求值或将其转换为不同的表示法。在表达式树中，叶节点包含操作数（数字或变量），内部节点包含运算符（+、-、x、/）。
To build an expression tree, you start from the root operator that is evaluated last according to the order of operations. The left subtree represents the left operand, and the right subtree represents the right operand. Brackets in infix expressions determine the tree’s structure.
要构建表达式树，你需从根据运算顺序最后求值的根运算符开始。左子树表示左操作数，右子树表示右操作数。中缀表达式中的括号决定了树的结构。
Example: Infix (A + B) x C –> Root: x, Left child: +, Right child: C, and the + node has children A (left) and B (right)
示例：中缀 (A + B) x C –> 根：x，左子节点：+，右子节点：C，而 + 节点有子节点 A（左）和 B（右）
Being able to draw or interpret expression trees is a key skill for the OCR exam. The examiner may ask you to deduce the original infix, prefix, or postfix expression by reading the tree.
能够绘制或解释表达式树是 OCR 考试的关键技能。考官可能会要求你通过读取树来推导原始的中缀、前缀或后缀表达式。
5. Tree Traversals Overview | 遍历概述
Traversal means visiting each node in a tree exactly once in a specific order. For binary trees, there are three depth-first traversal methods specified by the OCR syllabus: pre-order, in-order, and post-order. The names refer to when the root of the current subtree is visited relative to its left and right subtrees.
遍历意味着以特定顺序恰好访问树中的每个节点一次。对于二叉树，OCR 教学大纲规定了三种深度优先遍历方法：前序、中序和后序。这些名称指的是当前子树的根相对于其左子树和右子树的访问时间。
These three algorithms are recursive: you apply the same rule to every subtree. You can remember them with short rules: for pre-order you visit Root, then Left, then Right (RLR from the perspective of the node? Actually pre-order: root, left, right). In-order: Left, Root, Right. Post-order: Left, Right, Root. It is important to know these rules by heart as you will be expected to produce the output sequence for a given binary tree.
这三种算法都是递归的：你对每个子树应用相同的规则。你可以用简单的规则记住它们：前序遍历先访问根，然后左子树，然后右子树。中序：左子树，根，右子树。后序：左子树，右子树，根。熟记这些规则很重要，因为你需要对给定的二叉树生成输出序列。
6. Pre-order Traversal | 前序遍历
Pre-order traversal visits the current node first, then recursively traverses the left subtree, followed by the right subtree. The rule is: Node, Left, Right (often abbreviated NLR). Because the root comes first, pre-order gives a prefix notation of an expression tree.
前序遍历首先访问当前节点，然后递归遍历左子树，接着遍历右子树。规则是：节点、左、右（通常缩写为 NLR）。由于根节点在前，前序遍历会给出表达式树的前缀表示法。
To perform pre-order on paper, start at the root and write its value. Then move left, repeating the process. When you reach a leaf, its left child is null, so you backtrack and go right. Continue until every node has been visited.
要在纸上执行前序遍历，从根开始并写下其值。然后向左移动，重复该过程。当你到达叶子时，其左子节点为空，因此你回溯并向右移动。继续直到每个节点都被访问。
Pre-order sequence for (A + B) x C: x, +, A, B, C
(A + B) x C 的前序序列：x, +, A, B, C
If the exam provides a tree, you will need to list the items in the correct pre-order. Clearly showing your working can help avoid mistakes.
如果考试提供一棵树，你需要以正确的前序列出项目。清晰地展示你的工作过程有助于避免错误。
7. In-order Traversal | 中序遍历
In-order traversal visits the left subtree first, then the current node, and finally the right subtree. The rule is: Left, Node, Right (LNR). When applied to an expression tree, in-order traversal yields the infix notation, but without brackets. This is one reason why we need to add brackets manually when re-creating the original infix expression.
中序遍历首先访问左子树，然后访问当前节点，最后访问右子树。规则是：左、节点、右（LNR）。当应用于表达式树时，中序遍历产生中缀表示法，但没有括号。这就是我们在重建原始中缀表达式时需要手动添加括号的原因之一。
For the tree of (A + B) x C, the in-order sequence is A, +, B, x, C. To recover the original infix expression with correct order of operations, you must insert brackets around the left subtree’s result: (A + B) x C.
对于 (A + B) x C 的树，中序序列是 A、+、B、x、C。要恢复具有正确运算顺序的原始中缀表达式，你必须对左子树的结果加上括号：(A + B) x C。
In-order traversal is widely used because it visits nodes in sorted order when applied to a binary search tree. Although BST is not directly required for OCR, knowing this property can deepen your understanding.
中序遍历被广泛使用，因为当应用于二叉搜索树时，它按排序顺序访问节点。虽然 OCR 不直接要求二叉搜索树，但了解这一属性可以加深你的理解。
8. Post-order Traversal | 后序遍历
Post-order traversal recursively visits the left subtree, then the right subtree, and finally the current node. The rule is: Left, Right, Node (LRN). For expression trees, this outputs the postfix (Reverse Polish) notation, which is very useful for stack-based evaluation without needing brackets.
后序遍历递归访问左子树，然后右子树，最后访问当前节点。规则是：左、右、节点（LRN）。对于表达式树，它输出后缀（逆波兰）表示法，这对于无需括号的基于栈的求值非常有用。
Using the same tree, the post-order sequence is A, B, +, C, x. This corresponds to the postfix expression A B + C x. In an exam, you might be asked to convert a tree to postfix and then evaluate it, or to compare traversal outputs.
使用同一棵树，后序序列是 A、B、+、C、x。这对应于后缀表达式 A B + C x。在考试中，你可能会被要求将树转换为后缀表达式然后求值，或比较遍历的输出。
To avoid errors, always double-check that you have traversed every subtree fully before writing the parent node. Tracing the steps with a finger on the diagram often helps.
为避免错误，在写下父节点之前，请务必双重检查你是否已经完全遍历了每个子树。在图上用手指追踪步骤通常有帮助。
9. Traversal Examples on Expression Trees | 表达式树上的遍历示例
Let’s consolidate with a more complex expression: (A x B) + (C / D). The tree has root ‘+’, left child ‘x’ with children A and B, right child ‘/’ with children C and D. Applying the three traversals:
让我们用一个更复杂的表达式来巩固：(A x B) + (C / D)。树的根是 ‘+’，左子节点 ‘x’ 有子节点 A 和 B，右子节点 ‘/’ 有子节点 C 和 D。应用三种遍历：
| Traversal 遍历方式 | Rule 规则 | Output 输出 |
|---|---|---|
| Pre-order 前序 | NLR | +, x, A, B, /, C, D |
| In-order 中序 | LNR | A, x, B, +, C, /, D |
| Post-order 后序 | LRN | A, B, x, C, D, /, + |
Notice that the in-order output lacks brackets, so it looks like A x B + C / D, which is ambiguous without operator precedence. However, post-order A B x C D / + unambiguously evaluates using a stack: push operands, apply operators to the last two operands popped.
请注意，中序输出缺少括号，因此看起来像 A x B + C / D，在没有运算符优先级的情况下会产生歧义。然而，后序 A B x C D / + 使用栈进行明确求值：压入操作数，对弹出的最后两个操作数应用运算符。
The exam may ask you to construct a tree from a given infix expression and then produce the postfix form. Practice with brackets and different operator combinations to become fluent.
考试可能会要求你根据给定的中缀表达式构建树，然后生成后缀形式。练习使用括号和不同的运算符组合以达到熟练。
10. Uses of Trees in Computing | 树在计算机中的应用
Trees are not only used for expressions. They underpin many computer systems. A file system on your computer is organised as a tree: the root directory contains subdirectories (branches) and files (leaves). The Document Object Model (DOM) that represents a web page structure is a tree. Decision trees in artificial intelligence use nodes to represent decisions and leaves to represent outcomes.
树不仅用于表达式。它们支撑着许多计算机系统。你计算机上的文件系统以树的形式组织：根目录包含子目录（分支）和文件（叶子）。表示网页结构的文档对象模型 (DOM) 是一棵树。人工智能中的决策树使用节点表示决策，使用叶子表示结果。
In networking, routing algorithms use spanning trees to prevent loops. Even though you may not be examined on these details, understanding these real-world connections can help you remember why trees matter and how traversal techniques apply in scenarios like navigating a file hierarchy.
在网络中，路由算法使用生成树来防止循环。虽然你可能不会考查这些细节，但了解这些现实世界的联系可以帮助你记住树为何重要，以及遍历技术如何在导航文件层次结构等场景中应用。
For OCR GCSE, focus on expression trees and traversal, but knowing that trees are a fundamental concept across computing will strengthen your answers to open-ended questions.
对于 OCR GCSE，要重点掌握表达式树和遍历，但了解树是整个计算中的基本概念将加强你对开放式问题的回答。
11. Exam Tips | 考试技巧
When tackling a tree traversal question, always read the question carefully to see whether it provides an infix expression or a drawn tree. If a tree is given, label each node’s left and right edges to avoid confusion. If you need to build a tree from an expression, identify the last operator to be executed according to BODMAS (brackets, orders, division/multiplication, addition/subtraction) and make that the root. Then recursively process the left and right subexpressions.
在处理树遍历问题时，务必仔细阅读题目，看是提供了中缀表达式还是绘制的树。如果给出一棵树，请标记每个节点的左右边以避免混淆。如果你需要从表达式构建树，请根据 BODMAS（括号、幂、除/乘、加/减）确定最后执行的运算符，并将其作为根。然后递归处理左右子表达式。
When writing traversal sequences, use commas or spaces to separate items, just as the mark scheme expects. Some questions ask you to give the output of a traversal; others may give an output sequence and ask you to reconstruct the tree. Practice both directions. Always check that your tree has the correct in-order sequence (which should match the original infix expression) as a sanity check.
在编写遍历序列时，使用逗号或空格分隔项目，正如评分方案所期望的那样。有些问题要求你给出遍历的输出；其他问题可能给出输出序列并要求你重建树。两个方向都要练习。务必检查你的树是否具有正确的中序序列（应与原始中缀表达式匹配）作为合理性检查。
Time management is key. If you find yourself stuck on a tree diagram, list the recursive calls or mark the traversal path with a highlighter in the exam (if allowed). A systematic approach will save you valuable minutes.
时间管理是关键。如果你在树图上卡住了，可以在考试中列出递归调用或用荧光笔标记遍历路径（如果允许）。系统的方法将为你节省宝贵的时间。
12. Summary | 总结
Trees are a hierarchical data structure with a root, branches, and leaves. Binary trees restrict each node to at most two children. Expression trees use binary trees to represent arithmetic, with operators as internal nodes and operands as leaves. The three traversal methods – pre-order, in-order, and post-order – visit nodes in different orders, producing prefix, infix (without brackets), and postfix notations respectively. Mastering these concepts by practicing with various trees will give you confidence in the OCR GCSE exam. Remember, traversal is entirely rule-based; if you apply the rules systematically, you will always arrive at the correct answer.
树是一种具有根、分支和叶子的层次数据结构。二叉树限制每个节点最多有两个子节点。表达式树使用二叉树表示算术，以运算符为内部节点，操作数为叶节点。三种遍历方法——前序、中序和后序——以不同顺序访问节点，分别产生前缀、中缀（无括号）和后缀表示法。通过练习各种树来掌握这些概念将使你在 OCR GCSE 考试中充满信心。请记住，遍历完全基于规则；如果你系统地应用这些规则，你将始终得到正确的答案。
Published by TutorHao | GCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导