📚 IGCSE OCR Computer Science: Trees – Key Concepts | IGCSE OCR 计算机：树 考点精讲
A tree is a widely used abstract data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. It is one of the fundamental data structures you need to understand for the OCR IGCSE Computer Science examination (J277). Trees are particularly useful for representing data with a natural hierarchy – for example, file systems, family trees, organisational charts, or the structure of a webpage. In this article, we will walk through all the essential concepts required for your exam: the definition of a tree, key terminology, binary trees, tree traversals (pre-order, in-order and post-order), how trees can be used to represent arithmetic expressions, real-world applications, and finally some tips to help you tackle exam questions with confidence.
树是一种广泛使用的抽象数据结构，它模拟了层级状的树形结构，由一个根节点和包含若干子节点的子树组成，每个子节点都连接着一个父节点，整体呈现为一组链接节点的集合。它是 OCR IGCSE 计算机科学（J277）考试中你需要掌握的基础数据结构之一。在表示具有自然层级关系的数据时，树特别有用——例如文件系统、家谱、组织架构图或网页结构。在本文中，我们将逐一讲解考试要求的全部核心概念：树的定义、关键术语、二叉树、树的遍历（前序、中序和后序）、如何用树表示算术表达式、实际应用，最后还会提供一些备考技巧，帮助你自信应对考题。
1. What is a Tree? | 什么是树？
A tree is a non-linear, dynamic data structure consisting of nodes connected by edges. It does not store data in a sequential manner like an array or a list; instead, it organises data hierarchically. Each tree has a single starting node called the root, and from the root, edges branch out to other nodes, forming parent-child relationships. A tree cannot contain cycles, meaning there is exactly one path between any two nodes. This property makes trees an excellent model for hierarchical data. In computer science, trees are used in many areas including compilers, databases, operating systems, and artificial intelligence. Unlike physical trees, computer science trees are typically drawn with the root at the top and the leaves at the bottom.
树是一种非线性的、动态的数据结构，由节点和连接节点的边组成。它不像数组或列表那样以顺序方式存储数据，而是按层级来组织数据。每棵树都有一个唯一的起始节点，称为根，从根出发的边连接到其他节点，形成父子关系。树中不能包含循环，也就是说任意两个节点之间有且只有一条路径。这个特性使树成为层级数据的理想模型。在计算机科学中，树被用于许多领域，包括编译器、数据库、操作系统和人工智能。与自然界的树木不同，计算机科学中的树通常把根画在顶部，叶子画在底部。
2. Tree Terminology | 树的相关术语
Before diving deeper, it is essential to learn the standard terminology used when discussing trees. The main terms are: Node – each individual element in the tree; Edge – the connection between two nodes; Root – the topmost node with no parent; Parent – a node that has one or more connected child nodes; Child – a node directly connected to a parent; Siblings – nodes that share the same parent; Leaf (or external node) – a node with no children; Internal node – a node that has at least one child; Subtree – a portion of the tree that itself is a tree, consisting of a node and all its descendants; Depth – the number of edges from the root to a node; Height – the number of edges on the longest path from a node to a leaf (the height of the entire tree is the height of the root). Understanding these terms will help you accurately describe tree structures and answer exam questions.
在深入学习之前，必须掌握讨论树时使用的标准术语。主要术语有：节点（Node）——树中的每个独立元素；边（Edge）——两个节点之间的连接；根（Root）——最顶层、没有父节点的节点；父节点（Parent）——拥有一个或多个子节点的节点；子节点（Child）——直接连接在父节点下方的节点；兄弟节点（Siblings）——共享同一个父节点的节点；叶子（Leaf，也称外部节点）——没有子节点的节点；内部节点（Internal node）——至少有一个子节点的节点；子树（Subtree）——树中一部分，本身也是一棵树，由某个节点及其所有后代组成；深度（Depth）——从根到某个节点所经过的边的数量；高度（Height）——从一个节点到某片叶子的最长路径上的边数（整棵树的高度就是根的高度）。理解这些术语将帮助你准确描述树的结构，并解答考试题目。
3. Binary Trees | 二叉树
A binary tree is a special type of tree in which each parent node has at most two children, referred to as the left child and the right child. Binary trees are extremely important in computer science because they form the basis of binary search trees, expression trees, and heaps. Even within the IGCSE OCR specification, you are expected to be able to recognise and work with binary trees. The structure is recursive: every node can be considered the root of its own binary subtree. A binary tree can be empty (containing no nodes), or it can consist of a root plus a left binary subtree and a right binary subtree. It is vital to remember that in a binary tree the children are ordered – the left child is distinct from the right child, even if both are absent.
二叉树是一种特殊的树，每个父节点最多拥有两个子节点，分别称为左子节点和右子节点。二叉树在计算机科学中极其重要，因为它们是二叉搜索树、表达式树和堆的基础。即使在 IGCSE OCR 的考纲范围内，也要求你能够识别和使用二叉树。二叉树的结构是递归的：每个节点都可以看作它自己二叉子树的根。一棵二叉树可以为空（不包含任何节点），也可以由一个根节点加上一棵左二叉子树和一棵右二叉子树构成。务必记住，在二叉树中，子节点的顺序是有意义的——左子节点与右子节点是不同的，即使其中一方不存在。
4. Binary Search Trees (Extension) | 二叉搜索树（拓展理解）
Although the IGCSE OCR examination focuses mainly on the basic concepts of trees and their traversals, it can be beneficial to understand a binary search tree (BST) because it demonstrates a practical application of binary trees. A BST is a binary tree with an additional ordering property: for any given node, all values in the left subtree are smaller than the node’s value, and all values in the right subtree are larger. This ordering enables efficient searching, insertion, and deletion, typically in O(log n) time for a balanced tree. In an unbalanced BST, however, these operations can degrade to O(n). BSTs are not explicitly required for J277, but they appear in some specimen questions and provide context for why tree traversals are useful – an in-order traversal of a BST will visit nodes in ascending order.
虽然 IGCSE OCR 考试主要关注树的基本概念及其遍历方式，但了解二叉搜索树（BST）是很有好处的，因为它展示了二叉树的实际应用。BST 是一种带有附加排序性质的二叉树：对于任意给定的节点，其左子树中的所有值都小于该节点的值，而右子树中的所有值都大于该节点的值。这种顺序使得查找、插入和删除操作非常高效，对于平衡树通常能在 O(log n) 时间内完成。然而，在不平衡的 BST 中，这些操作可能会退化到 O(n)。J277 考纲并不明确要求 BST，但一些样题中曾出现过相关概念，并且它能说明为什么树的遍历是有用的——对 BST 进行中序遍历，能够按升序访问节点。
5. Tree Traversal: Pre-order | 树的遍历：前序遍历
Traversing a tree means visiting every node in a systematic way. The OCR specification expects you to be able to describe and apply three common depth-first traversals on binary trees: pre-order, in-order, and post-order. Pre-order traversal visits the current node before its child nodes, following the pattern: (1) Visit the root, (2) recursively traverse the left subtree in pre-order, (3) recursively traverse the right subtree in pre-order. In other words, it is root-left-right. For example, if you have a tree with root A, left child B, right child C, the pre-order traversal would be A, B, C. If B has a left child D, the sequence becomes A, B, D, C. Pre-order is useful for creating a copy of a tree or generating a prefix (Polish) notation from an expression tree.
遍历一棵树是指按照某种系统性的方法访问每一个节点。OCR 考纲要求你能够描述并在二叉树上应用三种常见的深度优先遍历：前序、中序和后序。前序遍历在当前节点之前先访问其子节点，遵循的模式为：(1) 访问根节点，(2) 递归地以前序方式遍历左子树，(3) 递归地以前序方式遍历右子树。换句话说，就是“根-左-右”。例如，如果一棵树的根是 A，左子节点是 B，右子节点是 C，那么它的前序遍历序列就是 A, B, C。如果 B 还有一个左子节点 D，那么序列就变成 A, B, D, C。前序遍历对于复制一棵树或从表达式树生成前缀（波兰）表示法非常有用。
6. In-order Traversal | 中序遍历
In-order traversal visits the nodes in a binary tree according to the pattern: (1) recursively traverse the left subtree in-order, (2) visit the root node, (3) recursively traverse the right subtree in-order. This gives a left-root-right order. Using the same example tree with root A, left child B, right child C, and B having a left child D, the in-order sequence becomes D, B, A, C. Notice that for a binary search tree, in-order traversal will yield the values in ascending order, which is why it is commonly used to output sorted data. In an expression tree, in-order traversal reproduces the original infix expression (though parentheses may need to be added to preserve operator precedence).
中序遍历按照以下模式访问二叉树中的节点：(1) 递归地以中序方式遍历左子树，(2) 访问根节点，(3) 递归地以中序方式遍历右子树。这给出了“左-根-右”的顺序。沿用同样的示例树（根 A，左子 B，右子 C，且 B 有左子 D），中序遍历得到的序列为 D, B, A, C。需要注意的是，对于二叉搜索树，中序遍历会按升序输出所有值，这就是为什么它常被用于输出有序数据。在表达式树中，中序遍历能够重现原始的中缀表达式（不过可能需要添加括号以保持运算符优先级）。
7. Post-order Traversal | 后序遍历
Post-order traversal visits the children before the parent, following the pattern: (1) recursively traverse the left subtree in post-order, (2) recursively traverse the right subtree in post-order, (3) visit the root node. In short, left-right-root. For the tree with A (root), B (left child with left child D), and C (right child), the post-order sequence would be D, B, C, A. Post-order traversal is essential when you need to delete a tree because you should delete children before their parent. In the context of expression trees, post-order traversal produces the postfix (Reverse Polish) notation of an expression, which is directly usable by stack-based evaluators.
后序遍历在访问父节点之前先访问子节点，遵循的模式为：(1) 递归地以后序方式遍历左子树，(2) 递归地以后序方式遍历右子树，(3) 访问根节点。简而言之就是“左-右-根”。对于前面那棵树（根 A，左子 B 带有左子 D，右子 C），其后序遍历序列应为 D, B, C, A。当你需要删除一棵树时，后序遍历至关重要，因为你应当在删除父节点之前先删除子节点。在表达式树中，后序遍历会生成表达式的后缀（逆波兰）表示法，这种表示法可以直接被基于栈的求值器使用。
8. Representing Arithmetic Expressions with Trees | 用树表示算术表达式
One practical application of binary trees that OCR candidates should be comfortable with is the expression tree. An expression tree is a binary tree used to represent an arithmetic expression. In such a tree, leaf nodes store operands (numbers or variables), and internal nodes store operators (+, –, ×, ÷). The structure of the tree reflects the precedence and associativity of operators. For instance, the expression (3 + 4) × 2 could be represented by a tree whose root is × with a left subtree representing 3 + 4 (root +, left child 3, right child 4) and a right child 2. By traversing this tree in post-order, you obtain the postfix notation 3 4 + 2 ×, and in-order traversal yields the infix version. Understanding expression trees helps you see how compilers parse and evaluate mathematical expressions. OCR exam questions may ask you to construct or interpret an expression tree given an infix expression, or to write the output of different traversals on such a tree.
OCR 考生需要熟练掌握的一种二叉树实际应用就是表达式树。表达式树是一棵用来表示算术表达式的二叉树。在这样的树中，叶子节点存储操作数（数字或变量），内部节点存储运算符（+、–、×、÷）。树的结构反映了运算符的优先级和结合性。例如，表达式 (3 + 4) × 2 可以用一棵树来表示，其根为 ×，左子树表示 3 + 4（根为 +，左子 3，右子 4），右子为 2。通过后序遍历这棵树，你可以得到后缀表示法 3 4 + 2 ×，而中序遍历则得出中缀形式。理解表达式树有助于你了解编译器如何解析和计算数学表达式。OCR 考题可能会要求你根据给定的中缀表达式构建或解释表达式树，或者写出在这类树上进行不同遍历的输出结果。
9. Real-World Applications of Trees | 树结构在现实世界中的应用
Trees are everywhere in computing. A classic example is the file system on your computer: directories (folders) act as internal nodes, while files are leaves. The root directory is the top of the tree. The Document Object Model (DOM) used by web browsers to represent HTML pages is a tree structure. Network routing protocols use trees to find shortest paths. In artificial intelligence, game-playing programs often use a game tree to explore possible moves. Databases use tree structures like B-trees for efficient indexing. Even in everyday software, undo/redo functionality can be implemented using a tree variation. For your IGCSE exam, being able to link abstract tree concepts to these concrete applications will not only help you answer context-based questions but also deepen your overall understanding.
树在计算领域无处不在。一个经典例子是计算机上的文件系统：目录（文件夹）充当内部节点，而文件则是叶子。根目录就是树的顶层。网页浏览器用来表示 HTML 页面的文档对象模型（DOM）就是一种树形结构。网络路由协议利用树来寻找最短路径。在人工智能中，游戏对弈程序通常会使用博弈树来探索可能的走法。数据库使用 B 树等树状结构来实现高效索引。甚至在日常软件中，撤销/重做功能也可以利用树的变体来实现。就你的 IGCSE 考试而言，能够将抽象的树概念与这些具体应用联系起来，不仅有助于你回答情境题，还能加深你对知识的整体理解。
10. Common Mistakes and Exam Tips | 常见错误与备考技巧
Many students lose marks on tree questions due to small, avoidable errors. Here are some key tips: Always read the traversal type carefully – confusing pre-order with post-order is a common mistake. When writing a traversal sequence, work step by step, noting down the order of visited nodes explicitly. If the tree is drawn, mark nodes as visited to keep track. For expression trees, verify that the tree structure correctly represents operator precedence – a common pitfall is placing an operator at the wrong level. Practice drawing binary trees from traversal sequences; this reverse process is often tested. Use past paper questions to become familiar with OCR’s style of tree diagrams and traversal tasks. Remember that edges are directional in tree diagrams, so count depth starting from the root (root depth = 0). Finally, if the question asks for an application of trees, refer to the real-world uses discussed above but link your answer clearly to the concept in question.
许多学生在树相关的题目上失分，都是因为一些可以避免的小错误。以下是几条关键建议：一定要仔细阅读遍历类型——将前序与后序混淆是常见错误。在写遍历序列时，要一步步来，明确记录下节点的访问顺序。如果题目给出了树图，可以边访问边标记节点，以防遗漏。对于表达式树，要核实树的结构正确反映了运算符优先级——常见的错误就是把运算符放在了错误的层次上。多做从遍历序列反推画出二叉树的练习，这种逆向过程经常受考。利用往年的真题来熟悉 OCR 关于树图与遍历任务的表现风格。记住，在树图中边是有方向的，因此计算深度要从根开始（根的深度为 0）。最后，如果题目要求给出树的应用，可以参考上文讨论的实际用途，但要将答案清晰地联系到题目所问的概念上。
11. Practice Questions to Solidify Your Knowledge | 巩固知识的练习题
To ensure you are fully prepared, try the following exercises. (1) Draw a binary tree from the pre-order sequence A, B, D, E, C, F, G and in-order sequence D, B, E, A, F, C, G. (2) Given the expression (a + b) × (c – d) ÷ e, construct an expression tree and then list the nodes in pre-order, in-order, and post-order. (3) State whether the following statement is true or false: ‘A binary tree can have at most two children per node’. (4) Explain why post-order traversal is suitable for deleting a tree. (5) Describe one real-world use of a tree structure, clearly identifying what the nodes and edges represent. Attempting these without looking at solutions first will help highlight any gaps in your understanding. If you find any part challenging, revisit the corresponding section above.
为了确保你准备充分，可以尝试以下练习。(1) 根据前序序列 A, B, D, E, C, F, G 和中序序列 D, B, E, A, F, C, G，画出二叉树。(2) 给定表达式 (a + b) × (c – d) ÷ e，构建表达式树，然后分别列出前序、中序和后序遍历的节点。(3) 判断下列说法是否正确：“二叉树的每个节点最多能有两个子节点”。(4) 解释为什么后序遍历适用于删除一棵树。(5) 描述树结构的一种实际应用，清楚指明节点和边分别代表什么。在查看答案之前先尝试完成这些题目，将有助于暴露你理解上的薄弱之处。如果发现某个部分有困难，请重新阅读上文中相应的章节。
12. Summary and Final Advice | 总结与最终建议
Trees are a fundamental hierarchical data structure that you must master for the OCR IGCSE Computer Science exam. Remember the core vocabulary: root, parent, child, leaf, subtree, depth, and height. Focus on binary trees and the three traversal methods: pre-order (root-left-right), in-order (left-root-right), and post-order (left-right-root). Practise constructing and interpreting expression trees, as they link arithmetic to tree operations and are frequently examined. Always apply a methodical approach to traversal by recording each step. Trees also map to real-world scenarios such as file systems and the DOM, which can enrich your long-answer responses. With solid conceptual understanding and plenty of past-paper practice, you can confidently tackle any tree-related question on your paper. Good luck with your revision and your examination!
树是一种基础性的层级数据结构，你必须掌握它，才能在 OCR IGCSE 计算机科学考试中表现出色。记住核心词汇：根、父节点、子节点、叶子、子树、深度和高度。重点掌握二叉树以及三种遍历方法：前序（根-左-右）、中序（左-根-右）和后序（左-右-根）。要练习构建和解读表达式树，因为它们将算术运算与树的遍历联系起来，经常出现在考题中。进行遍历时，务必要有条不紊地记录每一个步骤。此外，树与实际场景（如文件系统和 DOM）相互对应，这有助于丰富你的长篇回答。凭借扎实的概念理解和大量的真题练习，你一定能够自信地应对试卷中任何有关树的题目。祝你复习顺利，考试成功！
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply