Trees in Computer Science | 计算机中的树考点精讲

📚 Trees in Computer Science | 计算机中的树考点精讲

Trees are hierarchical data structures that store elements in a parent-child relationship. Understanding trees is fundamental for IB and CIE Computer Science, as they model many real-world systems and efficient algorithms. This article provides a comprehensive review of tree concepts, terminology, binary trees, binary search trees, traversal methods, heaps, array-based implementations, and typical exam-style applications.

树是一种按层次关系组织元素的数据结构，通过父节点与子节点的联系存储数据。掌握树的知识是 IB 和 CIE 计算机科学的基础，因为树可以模拟很多现实系统和高效算法。本文系统梳理了树的定义、术语、二叉树、二叉搜索树、遍历方式、堆、数组实现及常见考试应用场景。

1. Introduction to Trees | 树简介

A tree is a nonlinear data structure consisting of nodes connected by edges. Unlike arrays or linked lists, a tree has a hierarchical arrangement with a single root node at the top, branching out to child nodes. Trees are widely used to represent file systems, organisational charts, and decision processes.

树是一种非线性数据结构，由节点和连接节点的边组成。与数组或链表不同，树采用层次化的组织方式：顶层只有一个根节点，向下分支出子节点。树广泛用于表示文件系统、组织结构图和决策流程。

2. Tree Terminology | 树的术语

Key terms include: root (the topmost node), parent (a node directly above another), child (a node directly below another), siblings (nodes sharing the same parent), leaf (a node with no children), internal node (a node with at least one child), edge (the connection between two nodes), subtree (a portion of the tree considered as a separate tree), depth of a node (number of edges from the root), and height of the tree (the maximum depth of any node).

关键术语包括：根（最顶部的节点）、父节点（直接位于另一节点之上的节点）、子节点（直接位于另一节点之下的节点）、兄弟节点（具有相同父节点的节点）、叶节点（没有子节点的节点）、内部节点（至少有一个子节点的节点）、边（连接两个节点的线）、子树（以某个节点为根，可看作独立的一棵树）、深度（从根到该节点的边数）以及树的高度（所有节点深度的最大值）。

3. Binary Trees | 二叉树

A binary tree is a tree in which every node has at most two children, referred to as the left child and the right child. Even with an empty root, it is still a binary tree. A proper (full) binary tree has every node with either 0 or 2 children. A perfect binary tree is both full and complete, with all leaf nodes at the same depth. A complete binary tree is one where all levels are completely filled except possibly the last level, which is filled from left to right.

二叉树是指每个节点最多有两个子节点的树，分别称为左孩子和右孩子。即使根节点为空，仍属于二叉树。满二叉树（proper binary tree）中每个节点要么有 0 个要么有 2 个子节点。完美二叉树既满又完全，所有叶节点位于同一深度。完全二叉树则要求除最后一层外其余各层均填满，且最后一层的节点从左向右排列。

For a perfect binary tree of height h (where height is the number of edges from root to deepest leaf), the total number of nodes is:

对于高度为 h（从根到最深叶子节点的边数）的完美二叉树，节点总数满足：

n = 2ʰ⁺¹ – 1

If height is defined as the number of levels, the formula becomes 2ᵈ – 1 where d is the depth in levels. In exam contexts, clarify which definition is used.

若高度定义为层数，则公式为 2ᵈ – 1，其中 d 为层数深度。考试时需明确所用的高度定义。

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

A binary search tree is a binary tree with the ordering property: 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. Duplicates are usually disallowed or placed consistently. BSTs support efficient searching, insertion, and deletion, with an average time complexity of O(log n) if the tree is balanced.

二叉搜索树是一种满足排序性质的二叉树：对于任意节点，其左子树中所有值均小于该节点值，右子树中所有值均大于该节点值。通常不允许重复值，或规定重复值的放置策略。BST 支持高效的搜索、插入和删除操作，在树保持平衡的情况下平均时间复杂度为 O(log n)。

Searching a BST: start at the root. If the target equals the current node, return success. If the target is less, go left; if greater, go right. Repeat, treating each visited node as the root of a subtree. Insertion follows a similar pattern, placing the new node as a leaf.

在 BST 中搜索：从根开始。若目标值等于当前节点，返回成功。若目标值较小，转向左子树；若较大，转向右子树。重复该过程，将遇到的每个节点视作子树的根。插入操作遵循类似流程，最终将新节点添加为叶节点。

5. Tree Traversals | 树的遍历

Traversal means visiting every node in a tree exactly once. The four common traversals are: pre-order (visit root, traverse left subtree, traverse right subtree), in-order (left, root, right), post-order (left, right, root), and level-order (breadth-first, visiting nodes level by level from top to bottom, left to right).

遍历是指恰好访问树中的每个节点一次。常见的四种遍历方式为：前序遍历（先访问根，再遍历左子树，最后遍历右子树）、中序遍历（左、根、右）、后序遍历（左、右、根）和层次遍历（广度优先，从上到下逐层从左到右访问）。

Consider a tree with root A, left child B, right child C, B’s left child D, B’s right child E.

Pre-order: A, B, D, E, C
In-order: D, B, E, A, C
Post-order: D, E, B, C, A
Level-order: A, B, C, D, E

以根为 A、左子 B、右子 C、B 的左子 D、B 的右子 E 的树为例：

前序：A, B, D, E, C
中序：D, B, E, A, C
后序：D, E, B, C, A
层次：A, B, C, D, E

In binary search trees, in-order traversal visits nodes in sorted order, which is a frequently tested property. Recursion is the natural way to implement depth-first traversals, while level-order uses a queue.

在二叉搜索树中，中序遍历会按升序访问节点，这是一个常考性质。深度优先遍历通常用递归实现，层次遍历则借助队列。

6. Implementing Trees using Arrays | 用数组实现树

A complete binary tree can be efficiently stored in a one-dimensional array. If the root is at index 0, then for a node at index i:

Left child index: 2i + 1
Right child index: 2i + 2
Parent index: (i – 1) // 2 (integer division)

完全二叉树可以高效地用一维数组存储。若根节点位于索引 0 处，则对于索引为 i 的节点：

左子节点索引：2i + 1
右子节点索引：2i + 2
父节点索引：(i – 1) // 2（整数除法）

This representation saves memory by avoiding explicit pointers, but it is only space-efficient for complete or nearly complete trees. Heap data structures rely on this array representation.

这种表示法避免了显式指针，节省内存，但仅对完全或近乎完全的树具有较高的空间效率。堆数据结构正是基于这种数组表示法。

7. Heaps | 堆

A heap is a specialized 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 less than or equal to its children. The root therefore holds the maximum (or minimum) value. Heaps are usually implemented using arrays for O(1) access to the root and efficient insertion and deletion in O(log n) time.

堆是一种特殊的完全二叉树，满足堆性质：在最大堆中，每个父节点都大于或等于其子节点；在最小堆中，每个父节点都小于或等于其子节点。因此根节点存放最大（或最小）值。堆通常用数组实现，能 O(1) 访问根节点，并以 O(log n) 时间完成插入和删除操作。

Insertion into a max-heap: place the new element at the next available leaf position, then ‘sift up’ by comparing with its parent and swapping if the heap property is violated. Deletion of the root: replace the root with the last element, then ‘sift down’ by repeatedly swapping with the larger child until the heap property is restored. These operations underpin priority queues and the heapsort algorithm.

向最大堆插入元素：将新元素放在下一个可用的叶节点位置，然后“上滤”：与父节点比较，若违反堆性质则交换。删除根节点：用最后一个元素替换根节点，然后“下滤”：反复与较大的子节点交换，直至恢复堆性质。这些操作是优先队列和堆排序算法的基础。

8. Balanced Trees and AVL Concepts | 平衡树与 AVL 概念

Unbalanced binary search trees can degenerate into linked lists, degrading operations to O(n). To guarantee O(log n) performance, self-balancing trees such as AVL trees and red-black trees are introduced. An AVL tree maintains a balance factor (height of left subtree minus height of right subtree) of –1, 0, or +1 for every node. Rotations (single and double) are performed after insertions and deletions to restore balance.

不平衡的二叉搜索树可能退化为链表，操作复杂度降至 O(n)。为保证 O(log n) 性能，需要引入自平衡树，如 AVL 树和红黑树。AVL 树要求每个节点的平衡因子（左子树高度减去右子树高度）保持在 –1、0 或 +1。插入或删除后通过旋转（单旋转或双旋转）恢复平衡。

While detailed rotation algorithms are often beyond core syllabus requirements, understanding the motivation and the concept of height balance is important. Exam questions may ask you to identify whether a given tree is an AVL tree or to show the result of simple rotations.

虽然详细旋转算法可能超出核心大纲，但理解其动机和高度平衡的概念很重要。考题可能会要求判断某树是否为 AVL 树，或画出简单旋转后的结果。

9. Applications of Trees | 树的应用

Trees appear in numerous areas: file systems (directory hierarchies), expression parsing (syntax trees, abstract syntax trees), decision trees in machine learning, data compression (Huffman trees), network routing (spanning trees), database indexing (B-trees and B+ trees), and game trees (minimax). Understanding tree structures helps in designing algorithms for many real-world problems.

树广泛应用于多个领域：文件系统（目录层次结构）、表达式解析（语法树、抽象语法树）、机器学习中的决策树、数据压缩（哈夫曼树）、网络路由（生成树）、数据库索引（B 树和 B+ 树）以及博弈树（极小极大算法）等。理解树结构有助于为许多现实问题设计算法。

In examinations, you may be asked to draw an expression tree for a given arithmetic expression, traverse it to produce prefix/infix/postfix notation, or explain how a binary search tree can be used to implement a dictionary.

在考试中，可能会要求画出给定算术表达式的表达式树，通过遍历获得前缀/中缀/后缀表示法，或解释如何使用二叉搜索树实现字典。

10. Common Exam Pitfalls and Tips | 常见失分点与应试技巧

Many students confuse the order of traversals. A reliable method is to write a small recursive trace. For BST operations, always verify the ordering property after insertion or deletion, and be careful when removing a node with two children (replace with in-order successor or predecessor). When using the array representation, check whether indexing starts at 0 or 1, as formulas differ. For heap questions, draw the tree alongside the array to visualise the sift operations clearly.

很多学生容易混淆遍历顺序，建议编写简短递归过程进行推演。对于 BST 操作，插入或删除后务必验证排序性质，删除具有两个孩子的节点时要注意替代策略（用中序后继或前驱替换）。使用数组表示时，要明确索引是从 0 还是 1 开始，因为公式不同。堆问题中，可以同时画出树和数组来清晰呈现上滤与下滤过程。

Read the question carefully to know which height definition is being used, and always label your diagrams. Practice writing pseudocode for recursive tree algorithms, as this solidifies understanding and is often required in higher-mark questions.

仔细审题确定高度定义，并为图示添加标注。多练习编写树递归算法的伪代码，这有助于加深理解，也是高分题目常见要求。

11. Summary | 小结

Trees are a versatile and exam-relevant topic covering terminology, binary trees, BSTs, traversals, heaps, and real-world applications. Mastery requires hands-on practice with drawing, traversing, and implementing trees. Keep the key properties at your fingertips: binary tree shapes, BST invariant, traversal orders, heap invariant, and array index relationships. With these fundamentals, you can confidently tackle tree-based questions in IB and CIE Computer Science.

树是一个用途广泛且常考的主题，涵盖术语、二叉树、二叉搜索树、遍历、堆和实际应用。熟练掌握需要通过画图、遍历和实现树来进行大量练习。熟记二叉树的形态、BST 的不变性、遍历顺序、堆的不变性以及数组索引关系。掌握了这些基础，你就能自信应对 IB 和 CIE 计算机科学中与树相关的考题。

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

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

Trees in Computer Science | 计算机中的树考点精讲