Trees in IB & Edexcel Computer Science | IB Edexcel 计算机：树考点精讲

📚 Trees in IB & Edexcel Computer Science | IB Edexcel 计算机：树考点精讲

Trees are one of the most fundamental non-linear data structures in computer science, appearing prominently in both the IB Diploma and Edexcel A-Level specifications. A solid understanding of trees is essential for solving problems ranging from hierarchical data representation to efficient searching and sorting. This article breaks down every critical concept you need to master, from basic terminology to advanced operations on binary search trees and heaps.

树是计算机科学中最基础的非线性数据结构之一，在 IB 文凭课程和 Edexcel A-Level 大纲中都占据重要地位。扎实掌握树结构对于解决从层次化数据表示到高效搜索与排序等各种问题至关重要。本文详细拆解你需要掌握的每一个核心概念，从基本术语到二叉搜索树和堆的高级操作。

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

A tree is a collection of nodes connected by edges, where the structure is acyclic and hierarchical. It has a single root node, and every other node is connected by a unique path from the root. Trees are used to represent file systems, document object models, decision processes, and network routing tables.

树是由边连接的一系列节点的集合，结构是无环且层次化的。它有一个单一的根节点，从根到其他每个节点都有唯一路径。树用于表示文件系统、文档对象模型、决策过程和网络路由表。

A tree with n nodes always has exactly n−1 edges. This property is often examined in both IB paper 1 and Edexcel pseudocode tasks, where you might be asked to verify whether a given graph is a tree.

一棵有 n 个节点的树恰好有 n−1 条边。这一性质经常在 IB 试卷一和 Edexcel 伪代码题中出现，要求你判断给定图是否为树。

2. Tree Terminology | 树的基本术语

Key terms you must define accurately: root (the topmost node), parent (a node that has children), child (a node directly connected to another when moving away from the root), leaf (a node with no children), subtree (a node and all its descendants). The depth of a node is the number of edges from the root to that node, and the height of a tree is the maximum depth among all leaves.

必须准确定义的关键术语：根（最顶端的节点）、父节点（有子节点的节点）、子节点（从根向外移动时直接连接到另一节点的节点）、叶节点（没有子节点的节点）、子树（一个节点及其所有后代）。节点的深度是从根到该节点的边的数量，树的高度是所有叶节点深度的最大值。

In IB, you may be asked to calculate the height of a binary tree given its array representation; in Edexcel, you could be asked to trace the depth of a particular node during a traversal algorithm.

在 IB 中，你可能会被要求根据数组表示计算二叉树的高度；在 Edexcel 中，你可能需要在遍历算法执行过程中追踪特定节点的深度。

Term	Definition	术语	定义
Root	The only node with no parent	根	唯一没有父节点的节点
Leaf	Node with no children	叶	没有子节点的节点
Edge	Connection between two nodes	边	节点间的连接
Subtree	A node and all its descendants	子树	一个节点及其所有后代

3. Binary Trees | 二叉树

A binary tree is a tree where each node has at most two children, typically referred to as left child and right child. It is the most common form of tree examined in both IB and Edexcel. A full binary tree has every node with either 0 or 2 children; a complete binary tree has all levels completely filled except possibly the last, which is filled from left to right.

二叉树是每个节点最多有两个子节点的树，通常称为左孩子和右孩子。这是 IB 和 Edexcel 考试中最常见的树形式。满二叉树每个节点要么有 0 个要么有 2 个子节点；完全二叉树除最后一层外所有层都被完全填充，最后一层从左到右填充。

The maximum number of nodes at level i in a binary tree is 2ⁱ (counting the root as level 0). The maximum total number of nodes in a binary tree of height h is 2ʰ⁺¹ − 1.

二叉树中第 i 层最大节点数为 2ⁱ（根为第 0 层）。高度为 h 的二叉树最大总节点数为 2ʰ⁺¹ − 1。

n_max = 2ʰ⁺¹ − 1

IB often asks for this formula in multiple-choice questions, while Edexcel may expect you to implement a function calculating the size of a binary tree.

IB 常以选择题形式考查此公式，而 Edexcel 会期望你能实现一个计算二叉树节点数的函数。

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

A binary search tree is a binary tree with an ordering property: for every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This allows efficient searching, insertion, and deletion with average time complexity O(log n).

二叉搜索树是一种具有排序性质的二叉树：对于每个节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。这使得搜索、插入和删除操作的平均时间复杂度为 O(log n)。

Both syllabi require you to trace and construct BSTs by repeatedly inserting given data. For example, insert 8, 3, 10, 1, 6, 14, 4, 7, 13 into an initially empty BST. You must be able to draw the resulting tree and explain each step.

两个大纲都要求你通过反复插入给定数据来追踪和构建 BST。例如，将 8, 3, 10, 1, 6, 14, 4, 7, 13 依次插入一棵空 BST。你必须能够画出最终树并解释每一步。

In Edexcel, you are often required to write pseudocode for BST insertion and search algorithms that use recursion or iteration.

在 Edexcel 中，你经常需要编写二叉搜索树插入和搜索算法的伪代码，使用递归或迭代。

5. BST Search Algorithm | BST 搜索算法

Searching in a BST follows the ordering property. Start at the root, compare the target value with the current node: if equal, return found; if smaller, go left; if larger, go right. Repeat until the target is found or a null subtree is reached. This algorithm runs in O(h) time, where h is the height.

BST 中的搜索遵循排序性质。从根开始，将目标值与当前节点比较：如果相等则返回找到；如果较小则向左走；如果较大则向右走。重复直到找到目标或遇到空子树。该算法时间复杂度为 O(h)，其中 h 为高度。

You must be able to express this in pseudocode, handling both recursive and iterative implementations. The IB often tests this with a diagram showing search steps.

你必须能用伪代码表达，掌握递归和迭代两种实现。IB 经常通过图示搜索步骤进行考查。

Iterative Search Pseudocode:
SEARCH(root, target)
  current = root
  while current is not null
    if current.data == target
      return current
    else if target < current.data
      current = current.left
    else
      current = current.right
  return null

6. BST Insertion | BST 插入

Insertion in a BST always adds a new leaf node at the correct position, preserving the ordering property. Start at the root, follow the left or right child pointers comparing the new value, until reaching a null position, and insert there. Duplicates are usually disallowed or handled explicitly.

BST 插入操作总是在正确位置添加一个新的叶节点，维护排序性质。从根开始，比较新值，跟随左或右子指针，直到到达 null 位置，然后插入。重复值通常不允许插入或需明确说明处理方式。

In both IB and Edexcel, you might be asked to insert a set of values and predict the shape; an unbalanced BST from sorted input degenerates into a linked list with height n-1, leading to O(n) operations.

在 IB 和 Edexcel 中，你可能会被要求插入一组值并预测形状；如果输入已排序，BST 会退化成高度为 n-1 的链表，导致 O(n) 操作。

7. BST Deletion | BST 删除

Deletion is more complex and has three cases: deleting a leaf (simply remove), deleting a node with one child (replace with its child), deleting a node with two children (find the in-order successor – the smallest node in the right subtree – copy its value, then delete that successor).

删除操作更复杂，有三种情况：删除叶节点（直接移除）、删除只有一个子节点的节点（用其子节点替换）、删除有两个子节点的节点（找到中序后继——右子树中最小的节点——复制其值，然后删除该后继节点）。

The in-order successor is crucial because it maintains the BST property. In an examination, you must be able to trace deletion step by step and redraw the tree.

中序后继至关重要，因为它维护 BST 性质。在考试中，你必须能够逐步追踪删除操作并重新绘制树。

8. Tree Traversals | 树的遍历

Both IB and Edexcel require knowledge of three depth-first traversals: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root). Breadth-first (level order) traversal is also tested. For a BST, inorder traversal visits nodes in ascending order, which is a key property.

IB 和 Edexcel 都要求掌握三种深度优先遍历：前序（根，左，右）、中序（左，根，右）、后序（左，右，根）。广度优先（层次）遍历也会考查。对于 BST，中序遍历按升序访问节点，这是一个关键性质。

Preorder: + × a b − c d
Inorder: a × b + c − d
Postorder: a b × c d − +

These traversals are frequently linked to expression trees. IB often presents a tree and asks for the output of a given traversal pseudocode. Edexcel may ask you to write recursive traversal procedures.

这些遍历经常与表达式树关联。IB 常给出一棵树并要求给出指定遍历伪代码的输出。Edexcel 可能要求你编写递归遍历过程。

9. Expression Trees | 表达式树

Expression trees are binary trees where leaves are operands and internal nodes are operators. They are used to represent arithmetic expressions unambiguously. Inorder traversal gives the infix expression (brackets sometimes needed), postorder gives postfix (Reverse Polish Notation), and preorder gives prefix.

表达式树是一种二叉树，叶节点是操作数，内部节点是运算符。它们用于无歧义地表示算术表达式。中序遍历给出中缀表达式（有时需要括号），后序遍历给出后缀（逆波兰表示法），前序遍历给出前缀。

For example, the expression (a + b) × c can be represented as a tree with root ×, left child +, right child c, with left of + being a and right being b. Both syllabi may ask to build and traverse such trees.

例如，表达式 (a + b) × c 可以用根为 × 的树表示，左孩子是 +，右孩子是 c，+ 的左孩子是 a，右孩子是 b。两个大纲都可能要求构建并遍历这样的树。

10. Heaps | 堆

A heap is a complete binary tree that satisfies the heap property: in a max-heap, every parent is greater than or equal to its children; in a min-heap, every parent is less than or equal to its children. Heaps are used to implement priority queues and heap sort, which is an in-place O(n log n) sorting algorithm.

堆是一种完全二叉树，满足堆性质：在最大堆中，每个父节点大于或等于其子节点；在最小堆中，每个父节点小于或等于其子节点。堆用于实现优先队列和堆排序，堆排序是一种原地 O(n log n) 排序算法。

Heaps are usually represented in an array, with root at index 1 (or 0 in some implementations). For a node at index i: left child is at 2i, right child at 2i+1, parent at i//2 (using 1-based indexing). Both IB and Edexcel require you to perform heap operations like inserting and deleting elements (extracting max/min) and to rebuild the heap.

堆通常用数组表示，根在索引 1（某些实现为 0）。对于索引 i 的节点：左孩子在 2i，右孩子在 2i+1，父节点在 i//2（基于 1 的索引）。IB 和 Edexcel 都要求你执行堆操作，如插入元素、删除元素（提取最大/最小值）并重建堆。

11. Applications and Comparison | 应用与比较

Binary search trees provide efficient dynamic-set operations when balanced; unbalanced trees degrade to O(n). Balanced trees like AVL or red-black trees are not explicitly required but are mentioned in IB HL as a concept. Edexcel focuses on BST and heaps. Hash tables are compared to BSTs: search in a hash table averages O(1) but cannot support ordered operations like range queries.

平衡时，二叉搜索树提供高效的动态集合操作；不平衡的树退化为 O(n)。平衡树如 AVL 或红黑树不在大纲中明确要求，但 IB HL 中提及概念。Edexcel 侧重 BST 和堆。哈希表与 BST 比较：哈希表平均搜索为 O(1)，但不支持有序操作如范围查询。

Heaps are preferred for priority queues where only the extreme element is needed rapidly. Trees are also the underlying structure for file systems, syntax trees in compilers, and decision trees in machine learning, which may appear in context-based Paper 2 questions.

堆适用于只需快速获取最值元素的优先队列。树也是文件系统、编译器语法树和机器学习决策树的基础结构，可能出现在基于场景的试卷二中。

12. Exam Tips & Common Pitfalls | 考试技巧与常见错误

Traversal ordering: Many students confuse preorder and postorder. Remember preorder visits root first, postorder visits root last.
遍历顺序：许多学生混淆前序和后序。记住前序先访问根，后序最后访问根。
BST deletion with two children: Always replace with in-order successor, not predecessor unless specified; ensure you delete the successor from its original location.
有两个子节点的 BST 删除：总是用中序后继替换，除非明确指定用前驱；确保从原位置删除后继节点。
Heap array indexing: Check whether indexing starts at 0 or 1; adjust formulas accordingly. In IB pseudocode, often 1-based.
堆的数组索引：检查索引是从 0 还是 1 开始；相应调整公式。IB 伪代码中常用基于 1 的索引。
Drawing clear diagrams: In written answers, use clear, well-labelled diagrams; they are often worth marks.
绘制清晰的图：在笔试答案中，使用清晰标注的图示；通常有分值。
Recursion base case: Always include a base case for null nodes in traversal and search pseudocode to avoid infinite loops.
递归基案：遍历和搜索伪代码中始终包含空节点的基案，以避免无限循环。

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

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

Trees in IB & Edexcel Computer Science | IB Edexcel 计算机：树 考点精讲