Trees in A-Level Computer Science | 树考点精讲

📚 Trees in A-Level Computer Science | 树考点精讲

Trees form one of the most fundamental abstract data types in computer science, underpinning everything from file systems and databases to compilers and network routing. Mastering trees at A‑Level means understanding their recursive structure, essential terminology, storage representations, traversal algorithms and common variants such as binary search trees and heaps. This revision guide walks through each concept with clarity, linking theory to exam‑style thinking so you can approach any tree‑related question with confidence.

树是计算机科学中最基本的抽象数据类型之一，支撑着从文件系统、数据库到编译器和网络路由的一切。在A‑Level考试中掌握树，意味着要理解其递归结构、基本术语、存储表示、遍历算法以及二叉搜索树和堆等常见变体。这份复习指南将逐一梳理每个概念，将理论与考试思路联系起来，让你能够自信应对任何与树相关的问题。

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

A tree is a connected, acyclic graph consisting of nodes linked by edges, where any two nodes are connected by exactly one simple path. The hierarchical nature of a tree makes it perfect for representing relationships such as parent‑child, ancestor‑descendant, and sibling. In computer science, a tree is usually drawn with the root at the top and leaves at the bottom, growing downwards – an inverted natural tree. Because there are no cycles, you can never return to a previously visited node without backtracking.

树是一个由节点和边组成的连通无环图，任意两个节点之间恰好由一条简单路径连接。树的层次结构特性使其非常适合表示父子、祖先后代和兄弟等关系。在计算机科学中，树通常被绘制为根在上、叶在下、向下生长——一棵倒置的自然树。由于没有环，你永远不可能在不回溯的情况下回到之前访问过的节点。

The abstract data type (ADT) of a tree supports operations such as inserting a child, deleting a subtree, searching for a value, and traversing all nodes in a defined order. In A‑Level exams, you are expected to recognise a tree structure, distinguish it from a general graph, and apply tree properties to solve problems like expression evaluation and data storage.

树的抽象数据类型支持诸如插入子节点、删除子树、搜索某个值以及按指定顺序遍历所有节点等操作。在A‑Level考试中，你需要识别树结构、将其与一般图区分开来，并能应用树的性质解决如表达式求值和数据存储等问题。

2. Tree Terminology | 树的基本术语

A clear grasp of vocabulary is essential. The root is the top‑most node with no parent. A leaf (or external node) has no children. An internal node has at least one child. Parent, child and sibling describe immediate relationships. The depth of a node counts the number of edges from the root to that node, while the height of a node is the number of edges on the longest downward path to a leaf. The height of the tree is the height of its root. An edge is the link between two nodes.

清晰掌握术语至关重要。根是最顶层没有父节点的节点。叶节点（或外部节点）没有子节点。内部节点至少有一个子节点。父节点、子节点和兄弟节点描述了直接的亲属关系。节点的深度是从根到该节点的边数，而节点的高度是从该节点到叶节点的最长向下路径的边数。整棵树的高度就是其根节点的高度。边是两个节点之间的连接。

Other important terms include degree (number of children a node has), subtree (a portion of a tree that is itself a tree rooted at a particular node), and path (a sequence of connected nodes). The term binary tree is central at A‑Level: a tree where every node has degree at most 2. You will also encounter full and complete binary trees – a full binary tree has every node with either 0 or 2 children, while a complete binary tree has all levels completely filled except possibly the last, which is filled from left to right.

其他重要术语包括度（一个节点拥有的子节点数量）、子树（树的一部分，它本身也是一棵以某个特定节点为根的树）和路径（一系列相互连接的节点）。在A‑Level中，二叉树是核心概念：每个节点的度不超过2的树。你还会遇到满二叉树和完全二叉树——满二叉树的每个节点都有0个或2个子节点，而完全二叉树除了可能的最底层外所有层都被完全填满，且最底层的节点从左到右填充。

3. Binary Trees and Their Properties | 二叉树及其性质

A binary tree divides its children into a left child and a right child; the order matters. Two binary trees with the same set of nodes can be structurally different depending on how children are assigned. The maximum number of nodes at level L is 2ᴸ (where root is level 0). For a binary tree of height h, the maximum number of nodes is 2ʰ⁺¹ − 1. These formulas are derived by noticing that each level can double the number of nodes. Conversely, the minimum height of a binary tree with N nodes is ⌈log₂(N+1) − 1⌉, which occurs when the tree is complete.

二叉树将其子节点划分为左子节点和右子节点；顺序很重要。即使节点集合相同，两棵二叉树也可能因子节点的分配方式不同而在结构上有所区别。在第L层的最大节点数为2ᴸ（根节点为第0层）。对于高度为h的二叉树，最大节点数为2ʰ⁺¹ − 1。这些公式的推导基于每一层的节点数可以加倍。反之，含有N个节点的二叉树的最小高度为⌈log₂(N+1) − 1⌉，此时树是完全二叉树。

A‑Level questions frequently test whether a given tree is a binary search tree, a full binary tree, or a complete binary tree. You must be able to sketch a binary tree from its traversal orders or array representation, and to calculate its height, size, or number of leaf nodes. Knowing that a full binary tree with L leaves has exactly L − 1 internal nodes is a helpful shortcut.

A‑Level考题经常测试所给树是否为二叉搜索树、满二叉树或完全二叉树。你必须能够根据遍历顺序或数组表示画出二叉树，并计算其高度、大小或叶节点数。知道“有L个叶子的满二叉树恰好有L − 1个内部节点”是一个有用的捷径。

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

A binary search tree (BST) enforces 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. Duplicate values are usually handled by a consistent rule (e.g., placed in the right subtree). This property allows efficient searching, insertion and deletion – in a balanced BST these operations take O(log n) time on average, because approximately half the remaining elements are discarded with each comparison.

二叉搜索树（BST）遵循一个顺序不变性：对于任意节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。重复值通常按一致的规则处理（例如放入右子树）。这一性质使得高效的查找、插入和删除成为可能——在平衡的BST中，这些操作平均需要O(log n)时间，因为每次比较大约会丢弃剩余元素的一半。

Constructing a BST by inserting elements in a given order is a classic exam task. The shape of the resulting tree depends on the insertion sequence: inserting sorted data produces a degenerate (skewed) tree that is essentially a linked list, giving O(n) worst‑case performance. To maintain efficiency, self‑balancing variants like AVL trees and Red‑Black trees are used, but for A‑Level you only need to understand why balancing matters and perhaps how a balance factor is computed in an AVL tree.

按照给定顺序插入元素来构造一棵BST是经典的考试任务。最终树的结构取决于插入序列：插入已排序的数据会产生一棵退化的（偏斜的）树，本质上是一个链表，其最坏情况性能为O(n)。为了保持效率，会使用AVL树和红黑树等自平衡变体，但对于A‑Level你只需要理解为什么平衡很重要，或许还要知道如何在AVL树中计算平衡因子。

5. Tree Traversals | 树的遍历

Traversing a tree means visiting every node in a systematic way. The three depth‑first traversals for binary trees are pre‑order (root, left, right), in‑order (left, root, right), and post‑order (left, right, root). Pre‑order is useful for creating a copy of a tree; in‑order visits a BST in sorted order; post‑order is used for deleting a tree or evaluating postfix expressions in expression trees. You must be able to list the nodes for a given tree in each order, and to reconstruct a tree from two traversal sequences (typically in‑order combined with pre‑ or post‑order).

遍历一棵树意味着以系统的方式访问每个节点。二叉树的三种深度优先遍历是前序遍历（根、左、右）、中序遍历（左、根、右）和后序遍历（左、右、根）。前序遍历对创建树的副本很有用；中序遍历会按排序顺序访问BST；后序遍历用于删除树或在表达式树中计算后缀表达式。你必须能够为给定树列出每种顺序下的节点，并且能根据两种遍历序列（通常是中序结合前序或后序）重建一棵树。

Breadth‑first traversal (level‑order) visits nodes level by level, left to right. It is naturally implemented using a queue. Exam questions may ask you to write the level‑order sequence for a tree, to compare the order of visits between depth‑first and breadth‑first approaches, or to explain which traversal would be suitable for finding the shortest path in a decision tree.

广度优先遍历（层序遍历）逐层、从左到右访问节点。它很自然地使用队列来实现。考题可能会要求你写出树的层序遍历序列，比较深度优先和广度优先方法访问顺序的不同，或者解释哪种遍历适合在决策树中寻找最短路径。

6. Representing Trees in Memory | 树的存储表示

There are two common implementations: a linked structure using nodes and pointers, and an array‑based representation. In the linked representation, each node stores a data value and pointers (or references) to its left and right children. This approach is memory‑efficient for sparse trees and allows dynamic insertion and deletion. You may be asked to draw a node‑pointer diagram or to write pseudocode for creating a new node and linking it into the tree.

有两种常见的实现方式：使用节点和指针的链式结构，以及基于数组的表示。在链式表示中，每个节点存储一个数据值以及指向其左子节点和右子节点的指针（或引用）。这种方法对于稀疏树来说内存效率高，并允许动态插入和删除。你可能会被要求画出节点指针图，或编写创建新节点并将其链接到树中的伪代码。

The array representation stores a binary tree as a flat list where the root is at index 1 (or sometimes 0). For a node stored at index i, its left child is at 2i, its right child at 2i + 1, and its parent at ⌊i/2⌋. This scheme works beautifully for complete binary trees and heaps, wasting no space. However, for skewed trees it becomes extremely inefficient. A‑Level questions often involve drawing the array representation of a complete tree, or deducing relationships between parent and child indices.

数组表示将二叉树存储为一个扁平列表，其中根节点位于索引1（有时为0）。对于存储在索引i的节点，其左子节点在2i处，右子节点在2i + 1处，父节点在⌊i/2⌋处。这种方案对于完全二叉树和堆非常有效，不会浪费空间。然而，对于偏斜的树，它会变得极其低效。A‑Level题目经常涉及画出完全树的数组表示，或推导父子索引之间的关系。

7. Balanced Trees and AVL Rotations | 平衡树与AVL旋转

A tree is balanced if the height of the left and right subtrees of every node differ by no more than some constant. In an AVL tree, this balance factor must be −1, 0 or +1. When an insertion or deletion violates the balance condition, rotations are performed to restore balance. The four rotation cases are: left‑left (LL), right‑right (RR), left‑right (LR), and right‑left (RL). Understanding the mechanics of a single or double rotation is a key skill – you may be given an unbalanced AVL tree and asked to show the tree after rotation.

如果每个节点的左右子树高度差不超过某个常数，就说这棵树是平衡的。在AVL树中，这个平衡因子必须为−1、0或+1。当插入或删除操作违反了平衡条件时，就会通过旋转来恢复平衡。四种旋转情形是：左‑左（LL）、右‑右（RR）、左‑右（LR）和右‑左（RL）。理解单旋转或双旋转的机制是一项关键技能——你可能会被给出一棵不平衡的AVL树，并要求展示旋转后的树。

While detailed implementation of rotations may not be required in every A‑Level specification, the concept of “height‑balanced tree” and the reason for using rotations – to keep search, insert and delete operations at O(log n) – is definitely examined. Being able to state that an unbalanced BST degrades to O(n) and that AVL trees solve this problem through local restructuring is often the distinction between a pass and a merit.

虽然并非每种A‑Level考试大纲都要求旋转的详细实现，但“高度平衡树”的概念以及使用旋转的原因——保持查找、插入和删除操作为O(log n)——肯定是考查范围。能够说明不平衡的BST会退化至O(n)，而AVL树通过局部重构解决了这一问题，这往往是及格和优秀的区别所在。

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

A heap is a specialised 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. Heaps are typically implemented using an array, exploiting the parent‑child index relationships of a complete binary tree. The most common heap operations are insert (add an element and bubble it up) and extract‑max/min (remove the root, replace with the last element, and bubble down). Both run in O(log n).

堆是一种满足堆性质的特殊完全二叉树：在最大堆中，每个父节点都大于或等于其子节点；在最小堆中，每个父节点都小于或等于其子节点。堆通常使用数组实现，利用了完全二叉树中父子索引间的关系。最常见的堆操作是插入（添加一个元素并向上冒泡）和取出最大/最小值（移除根节点，用最后一个元素替换，然后向下冒泡）。两者都在O(log n)时间内完成。

Heaps are widely used in priority queues, heap sort, and graph algorithms such as Dijkstra’s shortest path. In A‑Level, you should be comfortable drawing the heap at each step of an insertion or deletion, converting between the tree and array representations, and explaining why a heap is not a binary search tree (there is no left‑right ordering constraint).

堆广泛应用于优先队列、堆排序以及像Dijkstra最短路径这样的图算法中。在A‑Level中，你应该能够熟练地画出插入或删除每一步后的堆，在树和数组表示之间进行转换，并解释为什么堆不是二叉搜索树（堆没有左‑右顺序的限制）。

9. Expression Trees | 表达式树

An expression tree is a binary tree where internal nodes are operators and leaves are operands (variables or constants). The tree captures the precedence and associativity of a mathematical expression without needing parentheses. For example, the infix expression (3 + 4) × 5 is represented by a tree with root ‘×’, left child ‘+’, right child ‘5’, and the left child of ‘+’ has leaves ‘3’ and ‘4’. The tree’s structure directly reflects the order of evaluation.

表达式树是一种二叉树，其内部节点为运算符，叶节点为操作数（变量或常量）。这棵树无需括号即可捕获数学表达式中的优先级和结合性。例如，中缀表达式 (3 + 4) × 5 可以用一棵根为“×”、左子节点为“+”、右子节点为“5”、且“+”的左子节点有叶节点“3”和“4”的树来表示。树的结构直接反映了求值顺序。

Traversing an expression tree in post‑order yields the postfix (Reverse Polish Notation) form, while pre‑order traversal gives prefix notation. A‑Level tasks often involve drawing an expression tree from an infix string, evaluating the tree recursively, or converting between infix, postfix and prefix representations. Being able to build a tree from a postfix expression using a stack is a classic exam scenario.

以后序遍历一棵表达式树会得到后缀（逆波兰记法）形式，而前序遍历则产生前缀记法。A‑Level任务往往包括根据中缀字符串画出表达式树、递归地对树求值，或在中缀、后缀和前缀表示之间进行转换。能够使用栈从后缀表达式构建一棵树是经典的考试情景。

10. Common Algorithms and Recursive Thinking | 常见算法与递归思维

Tree algorithms are usually expressed recursively, mirroring the recursive definition of a tree. Searching in a BST: compare the target with the root; if equal, found; if smaller, search left; if larger, search right. Insertion follows the same pattern until an empty spot is reached. Counting nodes, computing height, and checking if a tree is a BST are all naturally recursive. You may be asked to write or trace pseudocode for such routines, being careful with base cases (empty tree).

树的算法通常用递归表示，这与树的递归定义相对应。在BST中进行查找：将目标值与根比较；若相等则找到；若更小则向左查找；若更大则向右查找。插入遵循同样的模式，直到找到一个空位。计算节点数、计算高度以及检查一棵树是否为BST都自然具有递归性质。你可能会被要求为这些例程编写或跟踪伪代码，并注意基础情况（空树）。

Non‑recursive algorithms exist, typically using explicit stacks or queues to simulate recursion. For example, breadth‑first traversal uses a queue, and depth‑first traversals can be implemented iteratively with a stack. Understanding when recursion might cause a stack overflow (very deep skewed tree) and how an iterative approach avoids this is a mark‑earning insight.

也存在非递归算法，通常使用显式的栈或队列来模拟递归。例如，广度优先遍历使用队列，而深度优先遍历可以用栈迭代实现。理解递归何时可能导致栈溢出（非常深的偏斜树）以及迭代方法如何避免这一点，是一个能得分的见解。

11. Exam Focus: Tracing and Diagram Questions | 考试重点：跟踪与绘图题

A large proportion of tree questions require you to draw diagrams step by step, trace an algorithm on a given tree, or fill in missing values after a series of operations. Practise by taking a sequence of numbers, inserting them one by one into an initially empty BST, and drawing the tree after each insertion. Then perform deletions, showing how you replace a node with its in‑order successor when removing a node with two children. Do the same for an AVL tree, identifying when a rotation becomes necessary.

很大一部分树的考题要求你逐步绘制图表、在给定树上跟踪算法，或在一系列操作后填写缺失的值。练习的方法是：取一个数字序列，逐个插入到一棵初始为空的BST中，并在每次插入后画出树。然后进行删除操作，展示在删除含有两个子节点的节点时，如何用其中序后继来替换它。对于AVL树也做同样的练习，识别何时需要旋转。

When a question asks “State one advantage of a BST over an array”, the expected answer is about efficient O(log n) search while maintaining dynamic size, compared to O(n) for unsorted arrays or costly insertion in sorted arrays. Be precise and align with command word expectations. If asked to “explain”, give a reason and an example; if asked to “state”, a concise sentence suffices.

当问题问到“说明BST相对于数组的一个优势”时，预期的答案是关于在保持动态大小的同时具有O(log n)的高效查找，而未排序数组的查找为O(n)而排序数组的插入代价高昂。答案要精确，并符合指令词的要求。如果要求“解释”，则给出理由和例子；如果要求“陈述”，简洁的一句话就够了。

12. Key Takeaways for Revision | 复习要点总结

Memorise the definitions: root, leaf, internal node, parent, child, sibling, depth, height, degree, subtree, binary tree, full tree, complete tree.

牢记定义：根、叶、内部节点、父节点、子节点、兄弟节点、深度、高度、度、子树、二叉树、满树、完全树。
Know the array index formulas: parent = ⌊i/2⌋, left = 2i, right = 2i+1 (1‑based).

记住数组索引公式：父节点 = ⌊i/2⌋，左子节点 = 2i，右子节点 = 2i+1（从1开始索引）。
Be fluent in pre‑order, in‑order and post‑order traversal for any binary tree. Be able to reconstruct a tree from in‑order + pre‑order or in‑order + post‑order.

熟练地对任何二叉树进行前序、中序和后序遍历。能够从中序+前序或中序+后序遍历序列重建一棵树。
Understand BST operations and the consequences of unbalanced insertion. Recognise a degenerate tree and state its poor O(n) performance.

理解BST的操作以及不平衡插入的后果。识别退化树，并说明其糟糕的O(n)性能。
Explain the role of AVL rotations in keeping the tree height O(log n).

解释AVL旋转在保持树高为O(log n)方面的作用。
Describe heap properties and how insertion/extraction works in a min‑heap or max‑heap, both in array and tree form.

描述堆的性质以及最小堆或最大堆中插入/取出操作的工作原理，包括数组和树两种形式。
Draw expression trees and convert between infix, postfix and prefix notations.

绘制表达式树，并在中缀、后缀和前缀记法间进行转换。

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

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

Trees in A-Level Computer Science | 树 考点精讲