IB Computer Science: Trees Key Points | IB 计算机：树考点精讲

📚 IB Computer Science: Trees Key Points | IB 计算机：树考点精讲

In the IB Computer Science curriculum, trees are one of the most fundamental abstract data structures. They appear in Topic 5 (Abstract Data Structures) at both SL and HL, covering binary trees, binary search trees, traversals, and dynamic data structures. Understanding trees is essential not only for the exam but also for grasping advanced concepts in algorithms and programming. This article distills the key points you need to know, with clear explanations in both English and Chinese.

在 IB 计算机科学课程中，树是最基本的抽象数据结构之一。它们出现在 SL 和 HL 的第 5 主题（抽象数据结构）中，涵盖二叉树、二叉搜索树、树的遍历以及动态数据结构。理解树不仅对考试至关重要，也有助于掌握算法和编程中的高级概念。本文将提炼你需掌握的关键考点，并用清晰的中英双语解释。

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

A tree is a non-linear data structure composed of nodes connected by edges. It has a single root node and zero or more subtrees. Each node contains a data element and can have child nodes, forming a hierarchical parent-child relationship. Trees are used to represent data with natural hierarchies, such as file systems, organisational charts, or family trees.

树是一种非线性数据结构，由节点和边连接而成。它有一个根节点和零个或多个子树。每个节点包含一个数据元素，并可以有子节点，形成层次化的父子关系。树用于表示具有自然层次结构的数据，例如文件系统、组织结构图或家谱。

In IB Computer Science, a tree is defined as a collection of nodes where each node may be linked to one parent (except the root) and zero or more children. Trees cannot contain cycles, which distinguishes them from graphs. This acyclic property makes trees ideal for modelling branching processes.

在 IB 计算机科学中，树被定义为节点的集合，其中每个节点都链接到一个父节点（根节点除外）和零个或多个子节点。树中不能有循环，这使其区别于图。这种无环性质使树成为建模分支过程的理想结构。

2. Tree Terminology | 树的基本术语

You must be familiar with the following terms: root (the topmost node), leaf (a node with no children), edge (the connection between two nodes), parent and child (a node directly above or below another), sibling (nodes sharing the same parent), subtree (a node and all its descendants), depth (the number of edges from the root to the node), and height (the number of edges on the longest path from the node to a leaf).

你必须熟悉以下术语：根（最顶层的节点）、叶节点（没有子节点的节点）、边（两个节点之间的连接）、父节点与子节点（直接位于另一个节点上方或下方的节点）、兄弟节点（共享同一父节点的节点）、子树（一个节点及其所有后代）、深度（从根到该节点的边数）、高度（从该节点到叶节点的最长路径上的边数）。

In IB exam questions, these definitions are often tested through diagrams or simple calculations. For example, the height of a tree can be computed recursively: height(node) = 1 + max(height(left), height(right)) for a non-leaf. The size of a tree is the total number of nodes. Ensure you can distinguish between depth and height, as they are occasionally confused.

在 IB 考试题中，这些定义常通过图表或简单计算来考查。例如，树的高度可通过递归计算：对于非叶节点，height(节点) = 1 + max(左子树高度, 右子树高度)。树的大小是所有节点的总数。务必要能区分深度和高度，因为它们偶尔容易被混淆。

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 simpler to implement and traverse. An important property is that the maximum number of nodes at level k (where root is level 0) is 2ᵏ, and a full binary tree of height h has 2ʰ⁺¹ – 1 nodes.

二叉树是每个节点最多有两个子节点的树，这两个子节点分别称为左孩子和右孩子。这种限制使二叉树更易于实现和遍历。一个重要性质是，在第 k 层（根为第 0 层）的节点最大数量为 2ᵏ，而一棵高度为 h 的满二叉树具有 2ʰ⁺¹ – 1 个节点。

IB students should understand the difference between a full binary tree (every node has 0 or 2 children), a complete binary tree (all levels are completely filled except possibly the last, which is filled from left to right), and a perfect binary tree (all internal nodes have two children and all leaves are at the same level). These categories directly influence storage efficiency and algorithm complexity.

IB 学生应理解满二叉树（每个节点有 0 或 2 个孩子）、完全二叉树（除最后一层外所有层均填满，且最后一层从左向右填充）和完美二叉树（所有内部节点都有两个孩子，且所有叶子在同一层）之间的区别。这些分类直接影响存储效率和算法复杂度。

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

A binary search tree (BST) is a binary tree with an ordering invariant: for any node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This property enables efficient searching, insertion, and deletion in O(h) time, where h is the height. In a balanced BST, h ≈ log₂ n, giving O(log n) average-case operations.

二叉搜索树（BST）是一种具有排序不变式的二叉树：对于任一节点，其左子树中的所有值均小于该节点的值，且右子树中的所有值均大于该节点的值。该性质使得搜索、插入和删除操作能在 O(h) 时间内完成，其中 h 为树高。在平衡的 BST 中，h ≈ log₂ n，因此平均操作复杂度为 O(log n)。

To insert a value, you compare it with the root and recursively descend left or right until you reach a null link, where you place the new node. Deletion has three cases: node is a leaf (simply remove), node has one child (replace with child), node has two children (replace with in-order successor, the smallest node in the right subtree). You must be able to trace these algorithms on paper, as IB often asks for step-by-step diagrams.

要插入一个值，你需将其与根比较，并递归地向左或向右下降，直至达到空链接处，在此放入新节点。删除有三种情况：节点是叶子（直接删除）、节点有一个孩子（用孩子替换）、节点有两个孩子（用中序后继，即右子树中的最小节点替换）。你必须能够在纸上追踪这些算法，因为 IB 常要求绘制分步示意图。

5. Tree Traversals | 树的遍历

Traversal means visiting every node in a tree systematically. For binary trees, there are three depth-first strategies: pre-order (visit root, then left subtree, then right subtree), in-order (left, root, right), and post-order (left, right, root). Breadth-first (level-order) traversal visits nodes level by level from left to right, typically using a queue.

遍历是指系统地访问树中的每个节点。对于二叉树，有三种深度优先策略：前序遍历（访问根，然后左子树，然后右子树）、中序遍历（左，根，右）和后序遍历（左，右，根）。广度优先（层序）遍历从左到右逐层访问节点，通常使用队列实现。

These traversal sequences are extremely exam-relevant. For example, in-order traversal of a BST outputs the values in ascending sorted order. Post-order is used to delete a tree or evaluate postfix expressions in expression trees. Pre-order can be used to create a prefix copy or serialise the tree. You must be able to produce the traversal sequence given a tree diagram, or reconstruct a tree from two traversal sequences (typically in-order + pre-order or in-order + post-order).

这些遍历序列是考试的绝对重点。例如，对一棵 BST 进行中序遍历会按升序输出所有值。后序遍历常用于删除树或在表达式树中计算后缀表达式。前序遍历可用于创建前缀副本或序列化树。你必须能根据树图给出遍历序列，或从两种遍历序列（通常是中序 + 前序或中序 + 后序）重建一棵树。

6. Implementing Trees: Arrays vs Nodes | 树的实现：数组与节点

Trees can be implemented using linked nodes (each node stores data and pointers to left and right children) or arrays (especially for complete binary trees, where children of node at index i are at 2i+1 and 2i+2). The linked-node approach is dynamic and memory-efficient for irregular trees. The array representation is fast and cache-friendly but wastes space if the tree is not nearly complete.

树可以通过链接节点（每个节点存储数据以及指向左、右孩子的指针）或数组来实现（尤其对于完全二叉树，索引为 i 的节点的孩子位于 2i+1 和 2i+2）。链接节点方式对于不规则树是动态且内存高效的。数组表示速度快且对缓存友好，但如果树并非接近完全平衡，则会浪费空间。

In IB Java/Python code examples, you typically see a Node class with attributes value, left, and right. Array-based trees are often used when implementing heaps or when the tree structure is static. Understanding both representations helps you evaluate trade-offs in different scenarios.

在 IB 的 Java/Python 代码示例中，通常可以看到一个 Node 类，具有 value、left 和 right 属性。基于数组的树通常用于实现堆，或树结构为静态时。理解两种表示法有助于你在不同情景中评估权衡取舍。

7. Heaps: A Special Tree | 堆：一种特殊的树

A heap is a complete binary tree that satisfies the heap property: in a max-heap, every parent node is greater than or equal to its children; in a min-heap, every parent is smaller than or equal to its children. Heaps are commonly implemented using arrays and support insertion and removal of the root in O(log n) time, making them ideal for priority queues.

堆是一种完全二叉树，满足堆性质：在最大堆中，每个父节点都大于或等于其孩子；在最小堆中，每个父节点都小于或等于其孩子。堆通常用数组实现，支持 O(log n) 时间的插入和移除根节点操作，这使其成为实现优先队列的理想数据结构。

IB may ask you to perform heapify (building a heap from an unsorted array), insert (add an element to the end and bubble up), or extractMax/remove root (replace root with last element and sift down). You must be able to trace these operations on a diagram. Heapsort applies these operations repeatedly to sort an array in O(n log n) time.

IB 可能会要求你执行堆化（从未排序数组构建堆）、插入（将元素添加到末尾并向上冒泡）或 extractMax/移除根（用最后一个元素替换根并向下筛）。你必须能在图上追踪这些操作。堆排序通过重复这些操作，在 O(n log n) 时间内对数组排序。

8. Expression Trees | 表达式树

An expression tree is a binary tree where internal nodes are operators and leaves are operands (numbers or variables). It represents an arithmetic or logical expression. Traversals correspond to different notational forms: in-order gives infix expression (with parentheses needed), pre-order gives prefix, and post-order gives postfix. Building an expression tree from a postfix expression using a stack is a classic algorithm tested in IB.

表达式树是一种二叉树，其中内部节点是运算符，叶节点是操作数（数字或变量）。它表示一个算术或逻辑表达式。遍历方式对应不同的记法：中序遍历给出中缀表达式（需要括号），前序遍历给出前缀表达式，后序遍历给出后缀表达式。使用栈从后缀表达式构建表达式树是 IB 中经典的考查算法。

For example, the postfix ‘3 4 + 5 *’ constructs a tree where ‘*’ is root, left child is ‘+’ (with children 3 and 4), right child is 5. Evaluating an expression tree recursively is straightforward: if node is leaf, return its value; else compute operator on left and right subtree values.

例如，后缀表达式 ‘3 4 + 5 *’ 构建的树中 ‘*’ 为根，左孩子为 ‘+’（带有 3 和 4 两个孩子），右孩子为 5。递归计算表达式树很简单：若节点为叶子，则返回其值；否则对左右子树的值执行该运算符的计算。

9. Balanced Trees: AVL and Red-Black | 平衡树：AVL 树与红黑树

To prevent a BST from degenerating into a linked list (worst-case O(n) operations), balanced trees maintain a height difference constraint. AVL trees enforce that for every node, the heights of left and right subtrees differ by at most 1. After insertion or deletion, rotations (single or double) restructure the tree to restore balance. IB may ask you to identify imbalance and demonstrate the correct rotation sequence.

为防止 BST 退化为链表（最坏情况 O(n) 操作），平衡树维持高度差的约束。AVL 树要求对于每个节点，左右子树的高度差最多为 1。插入或删除后，通过旋转（单旋转或双旋转）重新调整结构以恢复平衡。IB 可能要求你识别不平衡，并演示正确的旋转序列。

Red-black trees are another self-balancing BST that use colouring rules (root is black, no adjacent red nodes, equal black-height) to ensure O(log n) performance. Although detailed red-black algorithms are beyond IB scope, you should know they are widely used in real-world libraries (e.g., Java’s TreeMap). The concept of balanced trees ties directly to the IB emphasis on efficiency of algorithms.

红黑树是另一种自平衡 BST，它使用着色规则（根为黑、无相邻红色节点、等黑高）来确保 O(log n) 性能。虽然红黑树的详细算法超出了 IB 范围，但你应知道它们在现实库中广泛使用（如 Java 的 TreeMap）。平衡树的概念直接关联到 IB 对算法效率的重视。

10. Common Applications of Trees | 树的常见应用

Trees are ubiquitous in computer science. File systems use directory trees; compilers construct syntax trees to parse source code; network routing relies on spanning trees; databases employ B-trees for indexing; AI uses decision trees for classification. Recognising these applications demonstrates higher-level understanding in IB Paper 1 and Paper 2 discussions.

树在计算机科学中无处不在。文件系统使用目录树；编译器构建语法树来解析源代码；网络路由依赖生成树；数据库使用 B 树进行索引；人工智能使用决策树进行分类。在 IB 试卷 1 和试卷 2 的讨论中，识别这些应用能展示更高层次的理解。

In your IB IA (Internal Assessment), you might use a tree structure to store hierarchical data, such as an organisation chart or a game state tree (minimax). Justifying your choice of data structure in the criterion C (Development) often requires explaining why a tree provided efficient access or recursion.

在你的 IB IA（内部评估）中，你可能会使用树结构存储层次化数据，例如组织结构图或游戏状态树（极小化极大算法）。在 C 标准（开发）中，证明数据结构选择合理通常需要解释为什么树能提供高效的访问或递归。

11. Exam Pitfalls and Tips | 考点常见误区与技巧

Do not confuse the height of a leaf (which is 0 or 1 depending on convention: IB typically defines leaf height as 0) with depth. Always clarify the definition used in the question. When drawing trees, label each node clearly and show the links. For traversal traces, follow the recursion precisely; many students incorrectly traverse order in post-order or in-order under time pressure.

不要混淆叶子的高度（取决于惯例是 0 还是 1：IB 通常定义叶子高度为 0）和深度。务必澄清题目所使用的定义。在绘制树时，清楚地标记每个节点并标出链接。在遍历追踪中，严格遵循递归；很多学生在时间压力下会错误地写出后序或中序遍历顺序。

Memory aid: Pre- (root first), In- (root in middle), Post- (root last). Another common pitfall is forgetting that BST insertion always creates a leaf node; you never shift existing nodes. When deleting a node with two children, the successor is the minimum of the right subtree – do not just pick a random child. For arrays representing complete trees, check that the index 2i+1 and 2i+2 are within bounds to avoid out-of-range errors.

记忆技巧：Pre-（根在前），In-（根在中），Post-（根在后）。另一个常见误区是忘记 BST 插入总是在叶子位置创建新节点；你从不移动已有节点。删除带有两个孩子的节点时，后继是右子树中的最小值——不要随便选个孩子。对于表示完全树的数组，要检查索引 2i+1 和 2i+2 是否在界内，避免越界错误。

Practise writing recursive solutions for tree traversal and depth calculation in pseudocode or Java/Python. IB markers look for correct base case (null node) and correct recursion on left/right subtrees.

在伪代码或 Java/Python 中练习用递归实现树遍历和深度计算。IB 阅卷人看重正确的基本情形（空节点）和左右子树的正确递归调用。

12. Summary and Revision Strategy | 总结与复习策略

Focus on these core areas: tree terminology, binary tree properties, BST invariants and operations, three depth-first traversals, heap as an array-based structure, and expression trees. Practice constructing trees from traversal sequences, tracing insert/delete in BSTs, and manipulating heaps. Write short pseudocode algorithms and verify them with sample data.

聚焦以下核心领域：树的术语、二叉树的性质、BST 的不变式与操作、三种深度优先遍历、基于数组的堆结构以及表达式树。练习从遍历序列构建树、追踪 BST 的插入/删除以及操作堆。编写简短的伪代码算法，并用样本数据验证。

For HL extension, be ready to discuss self-balancing trees conceptually and explain why balance factors matter. Remember that IB often combines trees with other abstract data types, such as using a stack for iteration or a queue for level-order traversal – these composite problems test your integrated knowledge.

对于 HL 的扩展内容，准备好从概念上讨论自平衡树，并解释为什么平衡因子很重要。记住 IB 常将树与其他抽象数据类型结合起来考查，例如用栈进行迭代、用队列进行层序遍历——这些复合问题测试你的综合知识。

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

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

IB Computer Science: Trees Key Points | IB 计算机：树 考点精讲