📚 GCSE WJEC Computer Science: Trees – Key Points | GCSE WJEC 计算机：树 考点精讲
Trees are one of the most important non-linear data structures in GCSE WJEC Computer Science. Understanding their terminology, types, traversal methods, and applications is essential for exam success. This article covers every key concept you need to master, from binary trees and BSTs to expression trees and common pitfalls.
树是 GCSE WJEC 计算机科学中最重要的非线性数据结构之一。理解其术语、类型、遍历方法和应用对考试成功至关重要。本文涵盖了你需要掌握的每一个关键概念，从二叉树和二叉搜索树到表达式树和常见陷阱。
1. What is a Tree? | 什么是树？
A tree is a hierarchical data structure consisting of nodes connected by edges. It is used to represent relationships that have a branching, non-linear structure, much like a family tree or a folder system.
树是一种层次化的数据结构，由节点和边连接组成。它用于表示具有分支、非线性结构的关系，很像家谱或文件夹系统。
Each tree has a single root node at the top. All other nodes descend from the root through parent-child relationships.
每棵树在顶部有一个根节点。所有其他节点通过父子关系从根衍生而来。
Trees are widely used in computer science for searching, sorting, expression evaluation, and organising data.
树在计算机科学中广泛用于搜索、排序、表达式求值和数据组织。
2. Basic Terminology | 基本术语
Key terms: Node – an element that holds data and links to other nodes. Parent – a node that has one or more children. Child – a node directly connected to a parent. Siblings – nodes sharing the same parent.
关键术语：节点—保存数据并连接到其他节点的元素。父节点—有一个或多个子节点的节点。子节点—直接连接到父节点的节点。兄弟节点—共享同一父节点的节点。
A leaf node (or terminal node) is a node with no children. A subtree is any node together with 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.
节点的深度是从根到该节点的边数。节点的高度是从该节点到叶节点的最长路径的边数；树的高度是根的高度。
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.
二叉树是一种每个节点最多有两个子节点的树，分别称为左子节点和右子节点。
Even if a node has only one child, the child is still designated as either left or right. This distinction makes binary trees ordered and allows for different traversal orders.
即使一个节点只有一个子节点，该子节点仍被指定为左或右。这种区分使二叉树有序，并允许不同的遍历顺序。
A binary tree can be empty (containing no nodes). The structure is recursive: each child itself forms the root of a binary subtree.
二叉树可以为空（不含节点）。结构是递归的：每个子节点本身构成一个二叉子树的根。
4. Binary Search Trees (BST) | 二叉搜索树
A Binary Search Tree (BST) is a special binary tree that organises data to enable efficient searching. For every node, all values in the left subtree are smaller than the node’s value, and all values in the right subtree are greater.
二叉搜索树是一种特殊的二叉树，它组织数据以实现高效搜索。对于每个节点，左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。
BSTs support fast lookup, insertion, and deletion – typically O(log n) if balanced. WJEC GCSE often tests the ability to construct a BST by inserting values one by one.
二叉搜索树支持快速查找、插入和删除——如果平衡，通常为 O(log n)。WJEC GCSE 常测试通过逐个插入值来构建二叉搜索树的能力。
To insert a new value, start at the root: if the value is less, go left; if greater, go right; repeat until an empty spot is found.
要插入新值，从根开始：如果值较小，向左走；如果较大，向右走；重复直到找到空位置。
5. Pre-order Traversal | 前序遍历
Pre-order traversal visits the current node first, then recursively visits the left subtree, and finally the right subtree. The order is: Root → Left → Right.
前序遍历先访问当前节点，然后递归访问左子树，最后访问右子树。顺序为：根 → 左 → 右。
This traversal is used to create a copy of the tree or to output prefix notation (Polish notation) for an expression tree.
此遍历用于创建树的副本或为表达式树输出前缀表示法（波兰表示法）。
Given the tree with root A, left child B, right child C, pre-order yields: A, B, C.
给定根为 A、左子 B、右子 C 的树，前序遍历结果为：A, B, C。
A recursive algorithm: visit(node), then preorder(left), then preorder(right). An iterative approach uses a stack.
递归算法：访问节点，然后前序遍历左子树，再前序遍历右子树。迭代方法使用栈。
6. In-order Traversal | 中序遍历
In-order traversal visits the left subtree first, then the current node, and then the right subtree: Left → Root → Right.
中序遍历先访问左子树，然后当前节点，最后右子树：左 → 根 → 右。
When applied to a binary search tree, in-order traversal retrieves all values in ascending order. This is a very common exam question.
当应用于二叉搜索树时，中序遍历会按升序检索所有值。这是非常常见的考题。
For the tree with root 10, left child 5, right child 20, in-order produces: 5, 10, 20.
对于根为 10、左子 5、右子 20 的树，中序遍历结果为：5, 10, 20。
If the tree is not a BST, in-order simply visits nodes in a defined left-to-right sequence, which may not be sorted.
如果树不是二叉搜索树，中序遍历只是按定义的从左到右顺序访问节点，可能并不排序。
7. Post-order Traversal | 后序遍历
Post-order traversal visits the left subtree, then the right subtree, and finally the current node: Left → Right → Root.
后序遍历访问左子树，然后右子树，最后当前节点：左 → 右 → 根。
This traversal is useful for deleting a tree (delete children before parent) or generating postfix notation (Reverse Polish Notation) for expressions.
此遍历对于删除树（在父节点之前删除子节点）或为表达式生成后缀表示法（逆波兰表示法）很有用。
For a simple tree A (root), B (left), C (right), post-order gives: B, C, A.
对于简单树 A（根）、B（左）、C（右），后序遍历结果为：B, C, A。
As with all traversals, it can be implemented recursively; the base case is an empty tree.
与所有遍历一样，它可以递归实现；基本情况是空树。
8. Traversal Algorithms in Pseudocode | 遍历算法伪代码
WJEC pseudocode often uses recursive procedures. For pre-order traversal:
WJEC 伪代码常使用递归过程。前序遍历：
PROCEDURE preorder(node)
IF node ≠ NULL THEN
OUTPUT node.data
preorder(node.left)
preorder(node.right)
ENDIF
END PROCEDURE
过程 preorder(node): 如果节点非空，输出节点数据，然后对左子节点调用 preorder，再对右子节点调用。结束过程。
In-order pseudocode:
PROCEDURE inorder(node)
IF node ≠ NULL THEN
inorder(node.left)
OUTPUT node.data
inorder(node.right)
ENDIF
END PROCEDURE
中序伪代码：先递归访问左子树，输出节点数据，再递归访问右子树。
Post-order pseudocode:
PROCEDURE postorder(node)
IF node ≠ NULL THEN
postorder(node.left)
postorder(node.right)
OUTPUT node.data
ENDIF
END PROCEDURE
后序伪代码：先递归左子，再右子，最后输出节点数据。
9. Building a Binary Tree from Traversals | 从遍历序列构建二叉树
Given pre-order and in-order traversal sequences, it is possible to uniquely reconstruct the original binary tree. The first element in pre-order is always the root. Locate this root in the in-order sequence; everything to its
Published by TutorHao | GCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply