A-Level OCR Computer Science: Trees – Key Concepts Explained | A-Level OCR 计算机：树 考点精讲

📚 A-Level OCR Computer Science: Trees – Key Concepts Explained | A-Level OCR 计算机：树 考点精讲

Trees are a fundamental data structure in OCR A-Level Computer Science, enabling efficient organisation and retrieval of data. Understanding trees is essential for mastering algorithms, memory management, and problem-solving in both theoretical papers and programming projects. This guide breaks down every key concept you need to know.

树是 OCR A-Level 计算机科学中的一种基础数据结构，能够高效地组织和检索数据。理解树对于掌握算法、内存管理以及在理论试卷和编程项目中解决问题至关重要。本指南将详细讲解你需要掌握的每个关键概念。

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

A tree is a connected, undirected graph with no cycles, consisting of nodes connected by edges. In computer science, trees are hierarchical data structures where each node contains data and links to child nodes. The topmost node is called the root, and nodes with no children are leaves. Trees are used to model file systems, parse expressions, and implement efficient searching.

树是一种连通、无环的无向图，由节点和边组成。在计算机科学中，树是一种层次化的数据结构，每个节点包含数据和指向子节点的链接。最顶端的节点称为根，没有子节点的节点是叶节点。树用于模拟文件系统、解析表达式以及实现高效搜索。

• A tree with N nodes always has exactly N-1 edges. | 一个有 N 个节点的树总是恰好有 N-1 条边。
• The depth of a node is the number of edges from the root to that node. | 节点的深度是从根到该节点的边数。
• The height of a tree is the maximum depth of any node. | 树的高度是所有节点中深度的最大值。

---

2. Binary Trees | 二叉树

A binary tree is a tree where each node has at most two children, referred to as the left child and right child. Binary trees form the foundation for more specialised trees such as binary search trees and expression trees. They can be implemented using arrays or linked nodes (objects with left and right pointers).

二叉树是一种每个节点最多有两个子节点的树，子节点分别称为左孩子和右孩子。二叉树是二叉搜索树和表达式树等更专业树结构的基础。它们可以使用数组或链接节点（带有左、右指针的对象）来实现。

• A full binary tree has every node with either 0 or 2 children. | 满二叉树中每个节点要么有 0 个子节点，要么有 2 个子节点。
• A complete binary tree has all levels filled except possibly the last, which is filled from left to right. | 完全二叉树除了可能的最后一层外，每一层都是满的，且最后一层从左到右填充。
• A perfect binary tree has all internal nodes with exactly two children and all leaves at the same level. | 完美二叉树中所有内部节点都有两个子节点，且所有叶节点在同一层。

---

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

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 the right subtree are greater. This allows efficient searching, insertion, and deletion in average O(log n) time. BSTs are a core topic in OCR specification H446.

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

Searching a BST: Start at the root; if the target equals the current node, return. If smaller, go left; if larger, go right. Repeat until found or leaf reached. | 搜索二叉搜索树：从根开始；如果目标等于当前节点，返回。如果更小，往左走；如果更大，往右走。重复直到找到或到达叶节点。

Common operations and their complexity:

Operation | 操作	Average | 平均	Worst | 最差
Search | 搜索	O(log n)	O(n)
Insertion | 插入	O(log n)	O(n)
Deletion | 删除	O(log n)	O(n)

Worst-case O(n) occurs when the tree becomes skewed, resembling a linked list.

最差情况 O(n) 发生在树倾斜时，类似于链表。

---

4. Tree Traversals | 树的遍历

Traversal means visiting every node in a tree exactly once. For binary trees, there are three depth-first traversal methods required by OCR: pre-order, in-order, and post-order. Breadth-first (level-order) may also be examined. Understanding traversal is vital for expression evaluation, BST sorting, and serialisation.

遍历是指仅访问树中每个节点一次。对于二叉树，OCR 要求掌握三种深度优先遍历方法：前序、中序和后序。广度优先（层序）也可能考查。理解遍历对于表达式求值、二叉搜索树排序和序列化至关重要。

• Pre-order (Root, Left, Right): Visit root, then recursively left subtree, then right. Used for copying a tree or prefix notation. | 前序（根、左、右）： 先访问根，然后递归左子树，再递归右子树。用于复制树或前缀表示法。
• In-order (Left, Root, Right): Recursively left subtree, root, then right. For a BST, this visits nodes in ascending order. | 中序（左、根、右）： 先递归左子树，然后根，再递归右子树。对于二叉搜索树，这会按升序访问节点。
• Post-order (Left, Right, Root): Recursively left subtree, right subtree, then root. Used for deleting trees or postfix notation. | 后序（左、右、根）： 先递归左子树，再递归右子树，最后根。用于删除树或后缀表示法。

Breadth-first traversal (level-order): Visit nodes level by level from left to right, typically using a queue. | 广度优先遍历（层序）：从左到右逐层访问节点，通常使用队列。

---

5. Implementing Trees | 树的实现

In OCR A-Level, you are expected to understand both linked-list (object-oriented) and array-based implementations of binary trees. A linked implementation uses a node class with attributes for data, left, and right. An array implementation stores nodes in an array where the root is at index 1, and for a node at index i, left child is at 2i, right child at 2i+1.

在 OCR A-Level 中，你需要理解二叉树的链表（面向对象）和基于数组的实现方式。链表实现使用具有数据、左指针和右指针属性的节点类。数组实现将节点存储在一个数组中，根在下标 1 处，对于下标 i 的节点，左孩子在 2i，右孩子在 2i+1。

Class definition in pseudocode (linked implementation):

class Node
  data: Integer
  left: Node
  right: Node
endclass

Array implementation formula: if root at index 1, then left child of node i is at 2i, right child at 2i+1, parent at i div 2. This is commonly used for heap structures.

数组实现公式：如果根在下标 1，则节点 i 的左孩子在下标 2i，右孩子在 2i+1，父节点在 i div 2。这种表示通常用于堆结构。

---

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

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 typically implemented using arrays and are used to implement priority queues, which are tested in OCR papers.

堆是一种满足堆性质的完全二叉树。在最大堆中，每个父节点都大于或等于其子节点；在最小堆中，每个父节点都小于或等于其子节点。堆通常使用数组实现，并用于实现优先队列，这在 OCR 试题中常被考查。

• Insertion: add element at next available position (end of array), then ‘heapify-up’ by swapping with parent until heap property is restored. Time complexity O(log n). | 插入：将元素添加到下一个可用位置（数组末尾），然后通过与其父节点交换进行“向上堆化”，直到恢复堆性质。时间复杂度 O(log n)。
• Deletion (extract max/min): replace root with last element, remove last, then ‘heapify-down’ by swapping with the larger (max-heap) or smaller (min-heap) child until heap property is restored. O(log n). | 删除（提取最大值/最小值）：用最后一个元素替换根，删除最后一个元素，然后通过与较大的（最大堆）或较小的（最小堆）子节点交换进行“向下堆化”。O(log n)。
• Heaps can also be used for heap sort: build a heap then repeatedly extract the root. Heap sort runs in O(n log n). | 堆还可用于堆排序：构建一个堆，然后重复提取根。堆排序运行时间为 O(n log n)。

---

7. Expression Trees | 表达式树

An expression tree is a binary tree that represents arithmetic or Boolean expressions. Leaves contain operands (numbers or variables), and internal nodes contain operators. Evaluating the tree via post-order traversal yields the result. OCR often asks students to construct or traverse expression trees for notations like infix, prefix, and postfix.

表达式树是一种表示算术或布尔表达式的二叉树。叶节点包含操作数（数字或变量），内部节点包含运算符。通过后序遍历对该树进行求值可得到结果。OCR 经常要求学生构造或遍历表达式树，以表示中缀、前缀和后缀表示法。

Example: (a + b) * (c – d) has postfix form a b + c d – *. Its expression tree has ‘*’ as root, ‘+’ and ‘-‘ as children. | 示例：(a + b) * (c – d) 的后缀形式为 a b + c d – *。其表达式树以 ‘*’ 为根，’+’ 和 ‘-‘ 为子节点。

Traversal mapping:

• In-order traversal → infix expression (may need parentheses). | 中序遍历 → 中缀表达式（可能需要括号）。
• Pre-order → prefix notation (Polish). | 前序 → 前缀表示法（波兰式）。
• Post-order → postfix notation (Reverse Polish). | 后序 → 后缀表示法（逆波兰式）。

---

8. Balanced Trees and Efficiency | 平衡树与效率

Unbalanced degenerate trees degrade to O(n) operations. Self-balancing trees like AVL or red-black trees maintain O(log n) through rotations, but OCR focuses on the concept rather than implementation details. You should understand the impact of balance on search efficiency and be able to calculate the maximum height of a balanced vs. unbalanced tree.

不平衡的退化树会使操作效率降至 O(n)。自平衡树（如 AVL 树或红黑树）通过旋转保持 O(log n)，但 OCR 更注重概念而非实现细节。你应该理解平衡对搜索效率的影响，并能计算平衡树与不平衡树的最大高度。

Key relationship: In a binary tree of height h, the maximum number of nodes is 2^(h+1) – 1, and the minimum number of nodes (balanced) is 2^h – 1 (assuming root at height 1). A balanced BST ensures search is O(log n), which is vital for large datasets. | 关键关系：在一棵高度为 h 的二叉树中，最大节点数为 2^(h+1) – 1，而（平衡时）最小节点数为 2^h – 1（假设根高度为 1）。平衡的二叉搜索树可确保搜索为 O(log n)，这对于大数据集至关重要。

---

9. Recursion and Trees | 递归与树

Tree algorithms are naturally recursive because trees are recursively defined: a tree consists of a root and subtrees. OCR expects you to trace and write recursive functions for insertion, searching, and traversal. Understanding base cases (e.g., null node) and recursive cases (e.g., go left or right) is crucial. Recursion links directly to the call stack visualisation of tree traversals.

树算法天生具有递归性，因为树是递归定义的：一棵树由一个根和若干子树组成。OCR 要求你追踪并编写递归函数，用于插入、搜索和遍历。理解基本情况（例如空节点）和递归情况（例如向左或向右）至关重要。递归与树遍历的调用栈可视化直接相关。

Example recursive in-order traversal pseudocode:

procedure inOrder(node)
  if node != null then
    inOrder(node.left)
    output node.data
    inOrder(node.right)
  endif
endprocedure

Without recursion, you can use explicit stacks to simulate, which is sometimes examined.

如果不使用递归，可以使用显式栈来模拟，这有时会考查。

---

10. Exam-style Applications | 考试风格的应用

OCR exam questions often integrate trees with other topics: compilers (parse trees), operating systems (directory structures), artificial intelligence (game trees, decision trees), and networking (spanning trees). You may be given a scenario and asked to design or analyse a tree structure, or trace an algorithm on a given tree.

OCR 考试题目经常将树与其他主题结合：编译器（解析树）、操作系统（目录结构）、人工智能（博弈树、决策树）和网络（生成树）。你可能会遇到一个场景，要求设计或分析树结构，或在给定的树上追踪算法。

Common question types:

• Draw a binary search tree after a series of insertions/deletions. | 一系列插入/删除操作后画出二叉搜索树。
• List the order of nodes visited in a given traversal. | 列出给定遍历中访问节点的顺序。
• Explain how a heap can be used to implement a priority queue. | 解释如何使用堆来实现优先队列。
• Compare the efficiency of trees vs. arrays for searching. | 比较树与数组在搜索方面的效率。

Always justify your answers using big-O notation where appropriate, and show working for traversal steps.

在适当的时候，始终使用大 O 表示法对你的答案进行解释，并展示遍历步骤的推导过程。

---

11. Common Pitfalls and Tips | 常见错误与建议

Avoid confusing in-order with pre-order traversal. Remember that in-order gives sorted output only for BSTs. When deleting a node with two children in a BST, replace it with its in-order successor (smallest node in right subtree) or predecessor. Be cautious with array implementation indices: starting at 0 or 1 changes the child formulas. Always check edge cases like empty trees and single-node trees.

避免混淆中序遍历和前序遍历。记住，只有对于二叉搜索树，中序遍历才会产生有序输出。在二叉搜索树中删除具有两个子节点的节点时，要用其中序后继（右子树中的最小节点）或前驱来替换它。注意数组实现的下标：从 0 还是从 1 开始会改变子节点公式。始终检查空树和单节点树的边界情况。

For heaps, remember that the array representation may have unused index 0. During heapify-down, choose the larger child in max-heaps and the smaller child in min-heaps. Recursion depth for skewed trees can cause stack overflow, so iterative approaches using stacks may be considered in practical projects.

对于堆，要记住数组表示法可能未使用下标 0。在向下堆化时，最大堆选择较大的子节点，最小堆选择较小的子节点。倾斜树的递归深度可能导致栈溢出，因此在实际项目中可考虑使用显式栈的迭代方法。

---

12. Summary and Keyword Check | 总结与关键词检查

To excel in OCR A-Level Computer Science, you must be confident with tree terminology, binary search tree operations, tree traversal algorithms, heap properties, expression tree construction, and the recursive nature of tree algorithms. Relate these to real-world applications and practice past-paper questions regularly. Remember that efficiency and correctness are always assessed.

要在 OCR A-Level 计算机科学中取得优异成绩，你必须熟练掌握树术语、二叉搜索树操作、树的遍历算法、堆性质、表达式树构造以及树算法的递归特性。将这些联系到现实世界的应用，并定期练习历年真题。请记住，效率和正确性始终是考查重点。

Key terms: root, leaf, edge, depth, height, binary tree, BST, pre-order, in-order, post-order, heap, priority queue, expression tree, balanced tree, recursion, big-O notation.

关键术语：根、叶、边、深度、高度、二叉树、二叉搜索树、前序、中序、后序、堆、优先队列、表达式树、平衡树、递归、大 O 表示法。

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

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