Tree Data Structures: Key Concepts for IB/CCEA Computer Science | 树数据结构考点精讲 (IB/CCEA 计算机)

📚 Tree Data Structures: Key Concepts for IB/CCEA Computer Science | 树数据结构考点精讲 (IB/CCEA 计算机)

A tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes. Mastering trees is essential for IB and CCEA Computer Science, as they form the basis for many algorithms in searching, sorting, parsing, and artificial intelligence. This article covers the core concepts, terminology, binary trees, tree traversals, and common applications you need to know for your exams.

树是一种广泛使用的抽象数据类型，它模拟具有根值和子树的分层树状结构，由一组相互链接的节点表示。掌握树结构对于 IB 和 CCEA 计算机科学至关重要，因为它们构成了搜索、排序、解析和人工智能中许多算法的基础。本文涵盖了你考试所需的核心概念、术语、二叉树、树的遍历以及常见应用。

1. Basic Tree Terminology | 基本树结构术语

A tree consists of nodes connected by edges. The topmost node is called the root. Each node may have child nodes, and the node directly above is called the parent. Nodes with the same parent are siblings. A node without children is a leaf node. An edge is the link between a parent and a child. A subtree is a node and all its descendants. 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 the root.

树由通过边连接的节点组成。最顶端的节点称为根节点。每个节点可以有子节点，而直接在上方的节点称为父节点。拥有相同父节点的节点为兄弟节点。没有子节点的节点是叶节点。边是父节点与子节点之间的链接。子树是指一个节点及其所有后代。节点的深度是从根到该节点的边数。节点的高度是从该节点到叶节点的最长路径上的边数。树的高度即根节点的高度。

English Term	中文术语	Definition
Root	根节点	The topmost node with no parent.
Parent	父节点	A node directly above another node.
Child	子节点	A node directly below another node.
Sibling	兄弟节点	Nodes sharing the same parent.
Leaf	叶节点	A node with no children.
Edge	边	Connection between two nodes.
Depth	深度	Number of edges from root to the node.
Height	高度	Longest path from the node to a leaf (in edges).

---

2. Binary Trees and Their Types | 二叉树及其种类

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. A strict or full binary tree is one where every node has either 0 or 2 children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a full binary tree where all leaf nodes are at the same depth. A balanced binary tree is one where the height of the left and right subtrees of any node differ by at most one (e.g., AVL trees).

二叉树是每个节点最多有两个子节点的树数据结构，分别称为左孩子和右孩子。严格二叉树或满二叉树是每个节点要么有0个要么有2个子节点的树。完全二叉树是一棵除了最后一层外其余层完全填满，且所有节点尽可能靠左的二叉树。完美二叉树是所有叶节点都在同一深度的满二叉树。平衡二叉树是指任意节点的左右子树高度差最多为1的二叉树（如 AVL 树）。

A binary tree can be represented in memory using nodes with data, left pointer, and right pointer in a linked structure, or by using an array where for a node at index i, the left child is at 2i+1 and right child at 2i+2 (assuming 0-indexing). This array representation is efficient for complete binary trees, such as heaps.

二叉树在内存中可以用包含数据、左指针和右指针的节点通过链表结构表示，或者通过数组表示，对于下标 i 的节点，左孩子在 2i+1，右孩子在 2i+2（假设索引从0开始）。这种数组表示对于完全二叉树（如堆）非常高效。

---

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

A Binary Search Tree is a binary tree with the property that for every node, all values in its left subtree are less than the node’s value, and all values in the right subtree are greater. This ordering allows for efficient searching, insertion, and deletion, typically O(log n) for balanced trees. In the worst case (degenerate tree), operations become O(n).

二叉搜索树是一种特殊的二叉树，其性质是：对于每个节点，左子树中所有值均小于该节点的值，右子树中所有值均大于该节点的值。这种有序性使得查找、插入和删除操作十分高效，对于平衡树通常为 O(log n)。在最坏情况（退化树）下，操作复杂度退化为 O(n)。

To search for a key in a BST, start at the root. If the key equals the root’s value, return true. If the key is less, recurse left; if greater, recurse right. If a null link is reached, the key is not found. Insertion follows a similar path and attaches the new node where the null was encountered. Deletion has three cases: leaf node (simply remove), node with one child (replace with child), and node with two children (find inorder successor, swap values, and delete the successor).

在 BST 中查找一个键值时，从根开始。若键值等于根的值，返回成功；若小于，递归左子树；若大于，递归右子树。如果遇到空链接，说明键值不存在。插入操作同理，最终在空链接处添加新节点。删除操作分三种情况：叶节点（直接删除）；有一个孩子的节点（用孩子替代）；有两个孩子的节点（寻找中序后继节点，交换值后删除后继节点）。

---

4. Tree Traversals | 树的遍历

Traversal means visiting every node in a tree exactly once in a specific order. The two main approaches are depth-first search (DFS) and breadth-first search (BFS). DFS can be performed in three standard orders: pre-order (root, left, right), in-order (left, root, right), and post-order (left, right, root). BFS is also called level-order traversal.

遍历是指按特定顺序恰好访问树中的每个节点一次。主要有深度优先搜索 (DFS) 和广度优先搜索 (BFS) 两种方法。DFS 可按三种标准顺序进行：前序（根、左、右）、中序（左、根、右）和后序（左、右、根）。BFS 也称层序遍历。

In-order traversal of a BST visits nodes in ascending order. Pre-order traversal is useful for creating a copy of the tree or for generating prefix expressions from an expression tree. Post-order traversal is used for deleting a tree or evaluating postfix expressions. Level-order traversal uses a queue to visit nodes level by level.

BST 的中序遍历会按升序访问节点。前序遍历可用于复制树或从表达式树生成前缀表达式。后序遍历用于删除树或计算后缀表达式。层序遍历利用队列逐层访问节点。

Recursive implementations of DFS traversals are elegant and examinable:

DFS 遍历的递归实现简洁且常考：

Pre-order: visit(node); traverse(left); traverse(right)

In-order: traverse(left); visit(node); traverse(right)

Post-order: traverse(left); traverse(right); visit(node)

---

5. Expression Trees | 表达式树

An expression tree is a binary tree that represents an arithmetic expression. Leaf nodes store operands (numbers or variables), and internal nodes store operators. An in-order traversal of the tree reproduces the infix expression (possibly with parentheses for clarity). Post-order traversal gives the postfix (Reverse Polish) notation, and pre-order traversal gives the prefix notation. Expression trees are used in compilers and calculators to parse and evaluate expressions.

表达式树是表示算术表达式的二叉树。叶节点存储操作数（数字或变量），内部节点存储运算符。对该树进行中序遍历可得到中缀表达式（可能需要加括号以明确优先级）。后序遍历得到后缀（逆波兰）表示法，前序遍历得到前缀表示法。表达式树广泛应用于编译器和计算器中解析和求值表达式。

To evaluate an expression tree, recursively evaluate left and right subtrees and apply the operator at the root. This is a natural post-order traversal. Building an expression tree from a postfix expression uses a stack: push operands as nodes; when seeing an operator, pop two nodes, make them children of a new operator node, and push the result back.

求值表达式树时，递归地计算左右子树的值，然后应用根节点的运算符。这本质上是一个后序遍历过程。从后缀表达式构建表达式树使用一个栈：操作数作为节点压栈；遇到运算符时，弹出两个节点，将它们作为新运算符节点的孩子，再将结果压回栈中。

---

6. Heaps and Priority Queues | 堆与优先队列

A heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, for any given node, the value of the node is greater than or equal to the values of its children; in a min-heap, it is less than or equal to its children. Heaps are commonly implemented as complete binary trees using arrays. They are the foundation for priority queues and the heapsort algorithm.

堆是一种基于树的特殊数据结构，满足堆性质。在最大堆中，任意节点的值都大于或等于其子节点的值；在最小堆中，则小于或等于其子节点的值。堆通常用数组实现为完全二叉树。它们是优先队列和堆排序算法的基础。

Key operations: Insert (add element at the end, then sift-up / bubble-up to restore heap property) and Extract-Max/Min (swap root with last element, remove last, then sift-down / bubble-down the new root). Both operations are O(log n). Building a heap from an unsorted array can be done in O(n) time using the heapify procedure.

关键操作：插入（将元素添加到末尾，然后执行上浮/向上调整以恢复堆性质）和提取最大/最小值（将根与最后一个元素交换，移除末尾，然后将新根执行下沉/向下调整）。这两个操作的时间复杂度均为 O(log n)。从无序数组建堆使用堆化过程，可以在 O(n) 时间内完成。

---

7. Balanced Trees and AVL Trees | 平衡树与 AVL 树

To guarantee O(log n) performance in BST operations, trees must remain balanced. An AVL tree is a self-balancing BST where the heights of the two child subtrees of any node differ by at most one. After insertion or deletion, the tree may become unbalanced, requiring rotations to restore balance. Rotations include left rotation, right rotation, left-right, and right-left double rotations.

为了保证 BST 操作的 O(log n) 性能，树必须保持平衡。AVL 树是一种自平衡二叉搜索树，其中任意节点的两个子树高度差最多为1。插入或删除后，树可能失衡，此时需要通过旋转来恢复平衡。旋转包括左旋、右旋、左右双旋和右左双旋。

Balance factor = height(left subtree) – height(right subtree). In AVL, this factor must be -1, 0, or 1. When a node’s balance factor becomes -2 or 2, the appropriate rotation is applied. AVL trees are crucial for high-performance data retrieval, though they add complexity to insertion and deletion compared to standard BSTs.

平衡因子 = 左子树高度 – 右子树高度。在 AVL 树中，该因子必须为 -1、0 或 1。当某节点的平衡因子变为 -2 或 2 时，需执行相应的旋转。AVL 树对于高性能数据检索至关重要，但与标准 BST 相比，增加了插入和删除操作的复杂性。

---

8. Trie (Prefix Tree) | 字典树 (前缀树)

A trie, or prefix tree, is a tree-like data structure used to store a dynamic set of strings where keys are usually sequences. Each node represents a single character; the path from the root to a node spells out a prefix. Nodes can be marked as the end of a word. Tries allow fast retrieval of keys with common prefixes and are used in autocomplete, spell checkers, and IP routing.

字典树（也称为前缀树）是一种用于存储动态字符串集合的树形数据结构，其中键通常是字符串序列。每个节点表示一个字符；从根到某节点的路径拼写出一个前缀。节点可以标记为单词的结束。字典树支持快速检索具有公共前缀的键，用于自动补全、拼写检查和 IP 路由等场景。

Insertion traverses the characters, creating new nodes as needed, and marks the final node as a word end. Search follows the path; if all characters match and the final node is marked, the word exists. Deletion removes the end marker and prunes unused branches. The time complexity for insert/search is O(L) where L is the length of the key, independent of the number of entries.

插入操作遍历每个字符，在需要时创建新节点，最后将终点节点标记为单词结束。搜索操作沿路径移动；若所有字符匹配且终点节点被标记，则单词存在。删除操作移除结束标记并剪去不再使用的分支。插入/搜索的时间复杂度为 O(L)，其中 L 为键的长度，与条目数量无关。

---

9. Huffman Coding Tree | 哈夫曼编码树

Huffman coding is a compression algorithm that assigns variable-length codes to characters based on their frequencies. A Huffman tree is a binary tree built using a greedy algorithm: repeatedly merge the two nodes with the lowest frequencies into a new internal node whose frequency is their sum, until one node remains. Edges are labeled 0 (left) and 1 (right), and the path from root to a leaf gives the Huffman code for that character.

哈夫曼编码是一种根据字符频率分配可变长编码的压缩算法。哈夫曼树是通过贪心算法构建的二叉树：反复将频率最小的两个节点合并为一个新内部节点，其频率为两者之和，直到只剩下一个节点。边标记为 0（左）和 1（右），从根到叶的路径给出该字符的哈夫曼编码。

Characters with higher frequencies end up with shorter codes, minimizing the overall encoded length. This prefix-code property ensures no code is a prefix of another, guaranteeing unambiguous decoding. Huffman coding is a classic example of a greedy algorithm and frequently appears in IB/CCEA exams on trees and data compression.

频率较高的字符获得较短的编码，从而最小化总编码长度。这种前缀码性质确保没有任何编码是另一个编码的前缀，保证解码无歧义。哈夫曼编码是贪心算法的经典实例，经常出现在 IB/CCEA 有关树和数据压缩的考题中。

---

10. Applications and Exam Tips | 应用与考试技巧

Trees are everywhere in computer science: file systems (directory trees), DOM in web pages, decision trees in machine learning, Abstract Syntax Trees in compilers, and network routing tables (tries). Understanding tree traversal and recursion is key to solving many algorithmic problems. In exams, you may be asked to draw a tree after a series of operations, write pseudo-code for a traversal, or explain the advantages of balanced trees.

树结构在计算机科学中无处不在：文件系统（目录树）、网页 DOM、机器学习中的决策树、编译器中的抽象语法树以及网络路由表（字典树）。理解树的遍历和递归是解决众多算法问题的关键。考试中可能要求你画出一系列操作后的树形结构，撰写遍历的伪代码，或解释平衡树的优势。

Common pitfalls include confusing depth with height, forgetting to update pointers during deletion, or misapplying rotations in AVL trees. Practice drawing step-by-step and tracing algorithms on paper. Remember: recursion is your friend for tree problems, but always define the base case carefully.

常见易错点包括混淆深度和高度、删除时忘记更新指针、或在 AVL 树中误用旋转。建议多加练习逐步绘图和纸上追踪算法。记住：递归是解决树问题的利器，但务必仔细定义基准情况。

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

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