📚 IB WJEC Computer Science: Trees Exam Essentials | IB WJEC 计算机：树 考点精讲
Understanding tree data structures is fundamental for IB Computer Science students following the WJEC specification. Trees model hierarchical relationships, forming the backbone of many algorithms and applications—from file systems to binary search and priority queues. This revision guide covers all the essential tree concepts you need to know, including terminology, binary trees, traversals, binary search trees, heaps, and their applications, with clear explanations and examples to help you excel in exams.
对于攻读 IB 计算机科学并遵循 WJEC 大纲的学生来说，理解树数据结构至关重要。树结构模拟层次关系，构成了许多算法和应用的基础——从文件系统到二叉搜索和优先队列。本考点精讲覆盖了你需要掌握的所有关键树概念，包括术语、二叉树、遍历、二叉搜索树、堆及其应用，并辅以清晰的解释和示例，助你在考试中脱颖而出。
1. Tree Fundamentals | 树的基本概念
A tree is a nonlinear, hierarchical data structure consisting of nodes connected by edges. It has a single root node at the top, and each node (except the root) has exactly one parent. Nodes with no children are called leaf nodes or external nodes, while internal nodes have at least one child. The depth of a node is the number of edges from the root to that node; the height of a node is the number of edges on the longest path from that node to a leaf. The height of the tree is the height of its root.
树是一种非线性、层次化的数据结构，由节点和连接节点的边组成。它只有一个根节点位于顶部，除根节点外每个节点有且仅有一个父节点。没有子节点的节点称为叶节点或外部节点，而内部节点至少有一个子节点。节点的深度是从根节点到该节点的边的数量；节点的高度是从该节点到叶节点的最长路径上边的数量。树的高度就是根节点的高度。
A subtree is any node in a tree together with all its descendants. Trees are widely used in computer science because they naturally represent hierarchical data such as file systems, organisation charts, HTML DOM, and family trees. In IB and WJEC exams, you will be expected to identify roots, parents, children, siblings, leaves, internal nodes, depth, and height on a given tree diagram.
子树是树中任意一个节点及其所有后代。树在计算机科学中被广泛使用，因为它能自然地表示层次数据，例如文件系统、组织结构图、HTML 文档对象模型和家谱。在 IB 和 WJEC 考试中，你需要能够在给定的树形图上识别根、父、子、兄弟、叶、内部节点、深度和高度。
2. Binary Trees and Properties | 二叉树及其性质
A binary tree is a special tree in which each parent node has at most two children, referred to as the left child and the right child. A full binary tree is one where 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 in the last level are as far left as possible. A perfect binary tree is both full and complete.
二叉树是一种特殊的树，其中每个父节点最多有两个子节点，分别称为左子节点和右子节点。满二叉树是每个节点要么有 0 个要么有 2 个子节点的树。完全二叉树是除最后一层外所有层都被完全填满，并且最后一层的所有节点都尽可能靠左的树。完美二叉树既是满的也是完全的。
Important properties to remember: in a binary tree of height h, the maximum number of nodes on level i is 2i (where level 0 has 1 node). The maximum total number of nodes in a binary tree of height h is 2h+1 − 1. The minimum height of a binary tree with n nodes is ⌊log2 n⌋. For a complete binary tree, the height is ⌊log2 n⌋ as well. These properties are often tested in multiple-choice questions.
需要记住的重要性质：在高度为 h 的二叉树中，第 i 层的最大节点数是 2i（第 0 层有 1 个节点）。高度为 h 的二叉树的最大总节点数是 2h+1 − 1。有 n 个节点的二叉树的最小高度是 ⌊log2 n⌋。对于完全二叉树，高度也是 ⌊log2 n⌋。这些性质常在选择题中考查。
In the WJEC specification, implementing a binary tree using arrays is sometimes covered: for a node at index i (starting from 0), its left child is at 2i + 1, its right child at 2i + 2, and its parent at ⌊(i − 1)/2⌋. This representation works efficiently for complete binary trees, such as when implementing heaps.
在 WJEC 大纲中，有时会涉及使用数组实现二叉树：对于索引为 i（从 0 开始）的节点，其左子节点位于 2i + 1，右子节点位于 2i + 2，父节点位于 ⌊(i − 1)/2⌋。这种表示法对于完全二叉树非常高效，例如实现堆时。
3. Tree Traversals: Depth-First | 树的遍历：深度优先
Tree traversal means visiting every node in a tree in a specific order. Depth-first traversals follow a path as far down as possible before backtracking. The three classic depth-first traversals for binary trees are preorder, inorder, and postorder. These differ in the order in which a node is visited relative to its left and right subtrees.
树的遍历是指按照特定顺序访问树中的每一个节点。深度优先遍历会尽可能沿着路径向下走，然后再回溯。二叉树的三种经典深度优先遍历是前序、中序和后序遍历。它们的区别在于访问节点的顺序与其左右子树的相对关系。
| Traversal | Order | Use case |
|---|---|---|
| Preorder | Root → Left → Right | Copying a tree, prefix expression |
| Inorder | Left → Root → Right | Getting sorted order from BST |
| Postorder | Left → Right → Root | Deleting a tree, postfix expression |
| 遍历方式 | 顺序 | 应用场景 |
|---|---|---|
| 前序 | 根 → 左 → 右 | 复制一棵树，前缀表达式 |
| 中序 | 左 → 根 → 右 | 从 BST 获得有序序列 |
| 后序 | 左 → 右 → 根 | 删除一棵树，后缀表达式 |
You can implement these traversals iteratively using a stack or elegantly with recursion. In IB exams, you are often required to trace a traversal on a given binary tree and write the sequence of visited nodes. Remember that for any binary search tree, inorder traversal visits nodes in ascending order.
你可以使用栈迭代实现这些遍历，也可以用递归优雅地实现。在 IB 考试中，常常要求对给定的二叉树进行遍历跟踪，并写出访问节点的序列。需要记住，对于任何二叉搜索树，中序遍历会按升序访问节点。
4. Tree Traversals: Breadth-First | 树的遍历：广度优先
Breadth-first traversal, also called level-order traversal, visits nodes level by level from top to bottom and from left to right within each level. This traversal uses a queue data structure: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its left and right children (if they exist).
广度优先遍历，也称为层序遍历，是从上到下逐层访问节点，并且在每一层内从左到右访问。这种遍历使用队列数据结构：将根节点入队，然后重复地将节点出队、访问该节点，并将其左右子节点（如果存在）入队。
Breadth-first traversal is useful for problems where you need to process nodes by proximity to the root, such as finding the shortest path in an unweighted tree or building a binary heap from an array. In WJEC exams, you should be prepared to write the level-order sequence for a given binary tree and to describe the algorithm.
广度优先遍历对于需要按节点到根节点的距离进行处理的问题很有用，例如在无权树中寻找最短路径，或者从数组构建二叉堆。在 WJEC 考试中，你应该准备好写出给定二叉树的层序序列，并描述该算法。
The time complexity of both depth-first and breadth-first traversals is O(n), where n is the number of nodes, because every node is visited exactly once. The space complexity is O(h) for depth-first recursion (h being the height of the tree) and O(n) for breadth-first in the worst case when the tree is a complete binary tree at the lowest level.
深度优先和广度优先遍历的时间复杂度都是 O(n)，其中 n 是节点数，因为每个节点恰好被访问一次。深度优先递归的空间复杂度为 O(h)（h 为树的高度），而广度优先在最坏情况下的空间复杂度为 O(n)，例如当最底层为完全二叉树时。
5. Binary Search Trees (BST) | 二叉搜索树
A binary search tree (BST) is a binary tree that satisfies the BST invariant: for any node, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. Duplicate values are usually handled by allowing them on the left or right consistently, or by not allowing duplicates at all.
二叉搜索树（BST）是一种满足 BST 不变性的二叉树：对于任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。重复值通常通过统一放在左或右子树中处理，或者干脆不允许重复。
BSTs enable efficient searching, insertion, and deletion operations. The average-case time complexity for these operations is O(log n) when the tree is balanced, but it degrades to O(n) in the worst case if the tree becomes skewed (like a linked list). This makes balancing techniques such as AVL trees and red-black trees important for maintaining performance, though these are often beyond the IB and WJEC core syllabus.
二叉搜索树能实现高效的搜索、插入和删除操作。当树保持平衡时，这些操作的平均时间复杂度为 O(log n)，但如果树发生倾斜（像链表一样），最坏情况会退化为 O(n)。因此，AVL 树和红黑树等平衡技术对于维持性能至关重要，不过这些通常超出了 IB 和 WJEC 核心大纲的范围。
In exams, you must be able to construct a BST from a sequence of numbers by inserting each value in order, always maintaining the BST property. You may also be asked to state the resulting inorder sequence, which will always be sorted.
在考试中，你必须能够通过依次插入每个值来从一个数字序列构建 BST，并始终保持 BST 性质。你还可能被要求写出最终的中序遍历序列，该序列始终是有序的。
6. BST Operations: Search and Insert | BST 操作：搜索与插入
To search for a key in a BST, start at the root and compare the key with the current node’s value. If it matches, the search is successful. If the key is smaller, go to the left child; if larger, go to the right child. Repeat until the key is found or a leaf is reached (unsuccessful search). This algorithm runs in O(h) time, where h is the height of the tree.
在 BST 中搜索一个键值，从根节点开始，将键值与当前节点的值进行比较。如果匹配，则搜索成功。如果键值较小，则转向左子节点；如果较大，则转向右子节点。重复这一过程直到找到键值或到达叶节点（搜索失败）。该算法的时间复杂度为 O(h)，其中 h 是树的高度。
Insertion follows a similar path: compare the new value with the current node; if smaller, go left; if larger, go right. When you reach a null (empty) position where a child is missing, insert the new node there. This maintains the BST property. For example, inserting 8,3,10,1,6,14,4,7,13 into an initially empty BST yields a specific tree shape that you should be able to draw.
插入操作遵循类似的路径：将新值与当前节点比较；如果较小则向左，如果较大则向右。当你到达一个空位（缺失子节点的位置）时，就在那里插入新节点。这维持了 BST 性质。例如，将 8,3,10,1,6,14,4,7,13 依次插入一个初始为空的 BST 中会产生一种特定的树形，你需要能够画出它。
In introductory coding tasks, these operations are implemented using either recursion or iteration. The WJEC specification expects you to understand pseudocode for search and insert operations, and to trace them on given trees.
在入门编程任务中，这些操作使用递归或迭代来实现。WJEC 大纲要求你理解搜索和插入操作的伪代码，并能在给定的树上进行跟踪执行。
7. BST Deletion Cases | BST 删除的几种情况
Deleting a node from a BST is more complex and has three main cases. Case 1: the node to delete is a leaf – simply remove it. Case 2: the node has exactly one child – replace the node with its child. Case 3: the node has two children – find the inorder successor (the smallest node in the right subtree) or the inorder predecessor (the largest in the left subtree), copy its value to the node, and then delete that successor/predecessor, which falls into Case 1 or Case 2.
从 BST 中删除节点更为复杂，主要有三种情况。情况 1：要删除的节点是叶子节点——直接删除它。情况 2：该节点只有一个子节点——用其子节点替换该节点。情况 3：该节点有两个子节点——找到中序后继节点（右子树中的最小节点）或中序前驱节点（左子树中的最大节点），将其值复制到该节点，然后删除该后继/前驱节点，这属于情况 1 或情况 2。
It is crucial to maintain the BST property throughout the deletion process. In exam questions, you might be asked to show the resulting BST after deleting a specific node from a given tree. Be careful with the choice of successor or predecessor and ensure no node is left with incorrect relationships.
在整个删除过程中必须保持 BST 性质。在考试题目中，你可能需要展示从给定树中删除特定节点后得到的 BST。注意选择后继或前驱，并确保没有节点留下不正确的关系。
Example: delete 10 from a BST containing the values from the earlier example. Since 10 has two children (14 and …), the inorder successor is 13 (the minimum of right subtree). Copy 13 into 10’s position, then delete the original 13 leaf. The resulting tree must still satisfy the BST invariant. Practise tracing such changes step by step.
示例：从包含之前示例数值的 BST 中删除 10。由于 10 有两个子节点，其中序后继是 13（右子树的最小值）。将 13 复制到 10 的位置，然后删除原本的 13 叶子节点。得到的树必须仍然满足 BST 不变性。请逐步练习跟踪这些变化。
8. Heaps: Min-Heap and Max-Heap | 堆：最小堆与最大堆
A heap is a specialized complete binary tree that satisfies the heap order property. In a max-heap, the value of each parent is greater than or equal to the values of its children; the root contains the maximum element. In a min-heap, each parent is less than or equal to its children; the root contains the minimum element. Heaps are not necessarily binary search trees – the only guarantee is the relationship between parent and children, not between siblings.
堆是一种特殊的完全二叉树，满足堆序性质。在最大堆中，每个父节点的值大于或等于其子节点的值；根包含最大元素。在最小堆中，每个父节点的值小于或等于其子节点的值；根包含最小元素。堆不一定是二叉搜索树——唯一保证的是父节点与子节点之间的关系，而不是兄弟节点之间的关系。
Heaps are most efficiently implemented using arrays due to the complete tree property. As stated earlier, for a node at index i, its children are at 2i+1 and 2i+2, and its parent is at (i−1)//2. This implicit representation saves memory and simplifies coding. Heaps underlie priority queues, which are a fundamental abstract data type.
由于完全二叉树的性质，堆通常使用数组最高效地实现。如前所述，对于索引为 i 的节点，其子节点位于 2i+1 和 2i+2，父节点位于 (i−1)//2。这种隐式表示法节省内存并简化编程。堆是优先队列的基础，优先队列是一种基本的抽象数据类型。
9. Heap Operations and Heap Sort | 堆操作与堆排序
The two key heap operations are insertion (push) and deletion of the root (pop, also called extract-max or extract-min). Insertion adds a new element at the next available leaf position (end of array) and then ‘bubbles up’ or ‘sifts up’ by swapping with its parent until the heap order is restored. This takes O(log n) time.
两个关键的堆操作是插入（push）和删除根节点（pop，也称为 extract-max 或 extract-min）。插入在下一个可用叶子位置（数组末尾）添加新元素，然后通过与其父节点交换来“上浮”或“筛选上移”，直到恢复堆序。这需要 O(log n) 时间。
Deletion of the root replaces the root with the last leaf (last element of array) and then ‘bubbles down’ or ‘sifts down’ by swapping with the larger child (in max-heap) or smaller child (in min-heap) until the heap property is satisfied. Again, complexity is O(log n). Building a heap from an arbitrary array can be done in O(n) time using the Floyd’s algorithm, which sifts down internal nodes starting from the bottom.
删除根节点时，将根节点替换为最后一个叶子节点（数组最后一个元素），然后通过与其较大的子节点（最大堆）或较小的子节点（最小堆）交换来“下沉”或“筛选下移”，直到满足堆性质。时间复杂度同样为 O(log n)。使用 Floyd 算法可以从任意数组在 O(n) 时间内建堆，该算法从底部开始对内节点进行下移操作。
Heap sort is an efficient, in-place sorting algorithm. First, build a max-heap from the input array. Then, repeatedly extract the maximum element (swap root with the last element, reduce heap size, and sift down the new root). After n−1 extractions, the array is sorted in ascending order. Heap sort has O(n log n) worst-case complexity and uses O(1) extra space. It is an important comparison-based sort often compared with quicksort and merge sort in WJEC exams.
堆排序是一种高效的原地排序算法。首先，从输入数组构建一个最大堆。然后，重复抽取最大元素（将根与最后一个元素交换，减小堆的大小，并对新根进行下移操作）。经过 n−1 次抽取后，数组按升序排列。堆排序的最坏情况时间复杂度为 O(n log n)，仅使用 O(1) 额外空间。它是一种重要的基于比较的排序算法，在 WJEC 考试中常与快速排序和归并排序进行比较。
10. Expression Trees and Applications | 表达式树与应用
An expression tree is a binary tree that represents a mathematical expression. Each leaf node stores an operand (number or variable), and each internal node stores an operator. The tree structure encodes the order of operations without needing parentheses. Preorder traversal yields prefix notation, inorder yields infix (which may need brackets to preserve order), and postorder yields postfix (Reverse Polish) notation.
表达式树是一种表示数学表达式的二叉树。每个叶节点存储一个操作数（数字或变量），每个内部节点存储一个运算符。树的结构编码了运算顺序，无需括号。前序遍历产生前缀表示法，中序遍历产生中缀表示法（可能需要括号以保持顺序），后序遍历产生后缀（逆波兰）表示法。
Expression trees are used in compilers and calculators to parse and evaluate expressions. Evaluating a tree can be done via a postorder traversal: recursively evaluate left subtree, evaluate right subtree, then apply the operator. This is a classic recursive algorithm tested in IB Computer Science.
表达式树在编译器和计算器中被用于解析和求值表达式。可以通过后序遍历对树求值：递归地对左子树求值，再对右子树求值，然后应用运算符。这是 IB 计算机科学中考查的一种经典递归算法。
Other tree applications you should know for WJEC include Huffman coding trees for data compression (greedy algorithm, assigning shorter binary codes to more frequent characters), trie data structures for prefix-based string retrieval, and disjoint-set trees (union-find) for connectivity problems. These illustrate the versatility of tree structures across computer science.
你应该了解的 WJEC 涉及的其他树应用包括用于数据压缩的哈夫曼编码树（贪心算法，为出现频率较高的字符分配较短的二进制编码）、用于基于前缀的字符串检索的字典树，以及用于连通性问题的并查集树。这些体现了树结构在计算机科学中的广泛适用性。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导