📚 IGCSE CIE Computer Science: Trees – Exam-Focused Mastery | IGCSE CIE 计算机：树 考点精讲
A tree is a hierarchical data structure that stores elements in a parent-child relationship. In IGCSE Computer Science, you must understand its terminology, binary trees, binary search trees, traversals, and applications. This article breaks down every key point you need for the CIE exam, with paired English–Chinese explanations to reinforce your learning.
树是一种分层数据结构，以父子关系存储元素。在IGCSE计算机科学中，你需要掌握树的术语、二叉树、二叉搜索树、遍历方式及其应用。本文逐点拆解CIE考试的核心考点，并配有英中对照解释，帮助你巩固理解。
1. What is a Tree? | 什么是树？
A tree consists of nodes connected by edges. It starts from a root node and branches out into child nodes. Unlike arrays or linked lists, a tree is non-linear and can represent hierarchical relationships effectively, such as file systems or organisation charts.
树由节点和连接节点的边组成。它从一个根节点开始，分支出子节点。与数组或链表不同，树是非线性的，能够有效表示层次关系，例如文件系统或组织结构图。
Every node (except the root) has exactly one parent. The root has no parent. A node can have zero or more children. This structure is acyclic, meaning there are no loops.
除根节点外，每个节点恰好有一个父节点；根节点没有父节点。一个节点可以有零个或多个子节点。该结构是无环的，这意味着不存在回路。
2. Key Terminology | 基本术语
Node – a single element in the tree that holds data.
节点 – 树中的一个单独元素，用于存放数据。
Edge – the link between two nodes.
边 – 两个节点之间的连接。
Root – the topmost node with no parent.
根 – 最顶层且没有父节点的节点。
Leaf (or terminal node) – a node with no children.
叶节点（或终端节点） – 没有子节点的节点。
Parent and Child – if node A is directly connected to node B below it, A is the parent of B, and B is a child of A.
父节点与子节点 – 如果节点 A 直接连接到其下方的节点 B，则 A 是 B 的父节点，B 是 A 的子节点。
Siblings – nodes that share the same parent.
兄弟节点 – 共享同一个父节点的节点。
Subtree – a portion of a tree consisting of 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 number of edges on the longest path from the root to a leaf. (Sometimes defined as number of nodes; for IGCSE CIE, depth/height often refers to edge count, but check pseudocode context.)
树的高度 – 从根到叶的最长路径上的边数。（有时定义为节点数；在IGCSE CIE中，深度/高度通常指边数，但需注意伪代码上下文。）
3. Binary Trees | 二叉树
A binary tree is a tree in which each node has at most two children, referred to as left child and right child.
二叉树是一种每个节点最多有两个子节点的树，分别称为左子节点和右子节点。
A full binary tree is a binary tree where every node has either 0 or 2 children (no node has exactly 1 child).
满二叉树是一种二叉树，每个节点要么有0个要么有2个子节点（没有节点恰好只有1个子节点）。
A complete binary tree is a binary tree in which all levels are completely filled except possibly the last level, and the last level has all its nodes as far left as possible.
完全二叉树是一种二叉树，所有层都是完全填满的，除了可能的最后一层，且最后一层的节点尽可能靠左排列。
A perfect binary tree is both full and complete: all leaf nodes are at the same level, and every internal node has two children.
完美二叉树既是满二叉树也是完全二叉树：所有叶节点位于同一层，每个内部节点都有两个子节点。
These definitions appear in exam questions about tree properties. You should be able to calculate maximum number of nodes: for a binary tree of height h (with root at height 0), maximum nodes = 2^(h+1) − 1.
这些定义会出现在关于树性质的考题中。你应该能够计算最大节点数：对于高度为 h 的二叉树（根节点高度为0），最大节点数 = 2ʰ⁺¹ − 1。
4. Binary Search Trees (BST) | 二叉搜索树
A binary search tree is a binary tree with the following ordering property: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. Duplicates are usually not allowed or are handled in a consistent way (e.g., always put on right).
二叉搜索树是一种具有以下排序性质的二叉树：对于任意节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。通常不允许重复值，或以一致的方式处理（例如总是放在右边）。
This property makes searching efficient: you can eliminate half of the remaining tree at each step, giving O(log n) search time on average if the tree is balanced.
这一性质使得搜索效率很高：如果树是平衡的，每一步可以排除一半剩余节点，平均搜索时间为 O(log n)。
IGCSE CIE questions often ask you to insert values into a BST step by step, or to state whether a given tree is a valid BST. Always check the left-smaller, right-larger rule at every node, not just root.
IGCSE CIE 的题目经常要求你逐步将值插入二叉搜索树，或判断给定的树是否为合法的BST。务必在每个节点处检查左小右大的规则，而不仅仅是根节点。
5. Tree Traversals: In-order, Pre-order, Post-order | 遍历：中序、前序、后序
Traversal means visiting every node in a tree exactly once. For binary trees, three depth-first traversals are essential:
遍历意味着恰好访问树中的每个节点一次。对于二叉树，三种深度优先遍历是必须掌握的：
In-order traversal (Left, Root, Right): Recursively traverse the left subtree, then visit the root, then the right subtree. For a BST, in-order gives values in ascending order.
中序遍历（左，根，右）： 递归遍历左子树，然后访问根，再遍历右子树。对于BST，中序遍历会按升序输出值。
Pre-order traversal (Root, Left, Right): Visit the root, then traverse left subtree, then right subtree. Used to create a copy of the tree or to generate a prefix expression from an expression tree.
前序遍历（根，左，右）： 访问根，然后遍历左子树，再遍历右子树。用于复制树或从表达式树生成前缀表达式。
Post-order traversal (Left, Right, Root): Traverse left subtree, then right subtree, then visit the root. Used to delete the tree or to generate a postfix expression (Reverse Polish Notation) from an expression tree.
后序遍历（左，右，根）： 遍历左子树，然后右子树，最后访问根。用于删除树或从表达式树生成后缀表达式（逆波兰表示法）。
You must be able to write the traversal sequence for a given tree and identify which traversal was used from a given sequence.
你必须能写出给定树的遍历序列，并能根据给定序列识别使用的是哪种遍历方式。
6. Level-order Traversal | 层序遍历
Level-order traversal (breadth-first) visits nodes level by level, from left to right. You typically use a queue to implement it.
层序遍历（广度优先）按层级从左到右访问节点。通常使用队列来实现。
Algorithm: enqueue the root. While queue is not empty, dequeue a node, visit it, then enqueue its left child (if any) and its right child (if any).
算法：根节点入队。当队列不为空时，出队一个节点并访问它，然后将其左子节点（如果有）和右子节点（如果有）依次入队。
IGCSE CIE may include questions that ask for level-order output or to trace a level-order algorithm. Practise with small trees until you can do it quickly.
IGCSE CIE 可能会要求你写出层序遍历的输出或追踪层序遍历算法。多练习小规模树，直到能快速完成。
7. Expression Trees | 表达式树
An expression tree is a binary tree that represents an arithmetic or logical expression. Leaves contain operands (numbers), and internal nodes contain operators. The structure reflects the precedence of operators, with lower-precedence operators closer to the root.
表达式树是一种表示算术或逻辑表达式的二叉树。叶节点存放操作数（数字），内部节点存放运算符。结构反映运算符的优先级，优先级较低的运算符更靠近根节点。
In-order traversal of an expression tree gives an infix expression (may need brackets), pre-order gives prefix (Polish) notation, and post-order gives postfix (Reverse Polish) notation.
表达式树的中序遍历给出中缀表达式（可能需要括号），前序遍历给出前缀（波兰）表示法，后序遍历给出后缀（逆波兰）表示法。
Example: For the expression (3 + 4) × 5, the tree has × at the root, + as left child, 5 as right child; left child + has 3 and 4 as its children. Post-order output: 3 4 + 5 ×.
示例：对于表达式 (3 + 4) × 5，树的根为 ×，左子节点为 +，右子节点为 5；左子节点 + 有子节点 3 和 4。后序遍历输出：3 4 + 5 ×。
You need to be able to draw an expression tree from an infix expression and produce RPN or PN from the tree.
你需要能根据中缀表达式画出表达式树，并从树生成逆波兰表示法或波兰表示法。
8. Decision Trees | 决策树
A decision tree is a tree structure used for classification and decision-making. Each internal node represents a test on an attribute, each branch an outcome of the test, and each leaf a final decision or class label.
决策树是用于分类和决策的树结构。每个内部节点代表对一个属性的测试，每个分支代表测试的结果，每个叶节点代表最终决策或分类标签。
IGCSE CIE may present a simple decision tree for a scenario, e.g., diagnosing a device fault. You should be able to trace a path for given inputs and state the expected output.
IGCSE CIE 可能会给出一个简单场景的决策树，比如诊断设备故障。你应该能根据给定输入追踪路径，并说出预期的输出。
There is no formal algorithm tested for building decision trees at this level, only interpretation and traversal.
在这个阶段不考察构建决策树的正式算法，只需要解释和遍历。
9. Heaps – An Introduction | 堆 – 入门介绍
A heap is a special binary tree that satisfies the heap property. In a max-heap, every parent node has a value greater than or equal to its children. In a min-heap, every parent has a value less than or equal to its children.
堆是一种满足堆性质的特殊二叉树。在最大堆中，每个父节点的值大于或等于其子节点；在最小堆中，每个父节点的值小于或等于其子节点。
A binary heap is typically stored in an array, with children of node at index i located at 2i+1 and 2i+2 (if using 0-based indexing). CIE may ask you to interpret a heap stored as an array or to perform insertions and deletions in a heap, maintaining the heap property.
二叉堆通常存储在数组中，索引 i 处的节点的子节点位于 2i+1 和 2i+2（若使用0基索引）。CIE 可能会要求你解释以数组存储的堆，或在堆中执行插入和删除操作，并维护堆性质。
Understanding heap operations, such as sift-up and sift-down, is important for priority queue applications, which are relevant to the syllabus.
理解堆的操作，如上浮和下沉，对于优先队列的应用很重要，这与教学大纲相关。
10. Trees vs Other Data Structures | 树与其他数据结构的比较
Why use a tree instead of an array or a linked list? Trees enable hierarchical representation and faster search when balanced (BST search O(log n) vs O(n) for linear structures). They also naturally support recursive algorithms.
为什么要用树而不是数组或链表？树可以表达层次关系，并且在平衡时提供更快的搜索（BST搜索 O(log n)，而线性结构为 O(n)）。树还天然支持递归算法。
However, trees use more memory due to storing pointers, and unbalanced trees can degrade to linked list performance (O(n)).
然而，由于存储指针，树占用更多内存；不平衡的树可能退化为链表性能（O(n)）。
For the IGCSE exam, you should be able to discuss the advantages and disadvantages of trees in given scenarios, e.g., a file directory structure is best modelled as a tree.
在IGCSE考试中，你应该能够讨论在给定场景下树的优缺点，例如文件目录结构最适合用树来建模。
11. Common Exam Mistakes and Tips | 常见考试错误与技巧
Mistake: Confusing in-order and pre-order sequences. Tip: Always write L-Root-R for in-order, Root-L-R for pre-order. Trace the tree with a finger to avoid skipping nodes.
错误： 混淆中序和前序序列。技巧： 始终记住中序为左-根-右，前序为根-左-右。用手指追踪树以避免遗漏节点。
Mistake: Forgetting that a BST node’s left subtree contains only smaller values – not just its left child. Check the whole subtree.
错误： 忘记BST节点的左子树只包含更小的值——而不只是其左子节点。检查整个子树。
Mistake: Assuming a tree is balanced when it is not. In the worst case, BST operations become O(n).
错误： 在树不平衡时假设其是平衡的。在最坏情况下，BST 操作退化为 O(n)。
Tip: When asked to insert values into a BST, draw each step clearly and check the property after every insertion.
技巧： 当要求将值插入BST时，清晰地画出每一步，并在每次插入后检查性质。
Tip: For expression trees, always apply operator precedence rules when building the tree. The last operator evaluated becomes the root.
技巧： 对于表达式树，在构建时始终遵循运算符优先级规则。最后计算的运算符成为根。
12. Practice Prompts for Self-Test | 自测练习提示
Try these to check your understanding: (1) Draw a BST after inserting: 50, 30, 70, 20, 40, 60, 80. Write pre-order, in-order, and post-order sequences. (2) Construct an expression tree for 8 − 3 × 2 + 1. (3) Explain why in-order traversal of a BST gives sorted output. (4) Describe how a level-order traversal uses a queue.
尝试以下自测： (1) 按顺序插入 50, 30, 70, 20, 40, 60, 80 后画出BST，并写出前序、中序和后序序列。(2) 构建表达式 8 − 3 × 2 + 1 的表达式树。(3) 解释为什么BST的中序遍历会得到排序输出。(4) 描述层序遍历如何使用队列。
If you can answer these confidently, you have covered the core IGCSE concepts on trees.
如果你能自信地回答这些问题，你就已经掌握了IGCSE树的核心概念。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导