B.4 抽象数据类型 · HL

追踪链式结构与树

分析引用、递归结构与遍历顺序。

示例使用 Python。HL 路径包含 SL 之外的额外课程。

链接存储关系

链表节点保存一个值以及指向下一节点的引用。在当前节点后插入节点时，应先保存原来的 next 引用再替换。丢失引用可能使后续节点无法从表头到达。

二叉搜索树把较小键放入左子树，较大键放入右子树，并明确相等键的处理规则。符合排序规则时，搜索在当前节点比较后只需选择一侧子树。

中序遍历按左子树、当前节点、右子树的顺序访问。对有效二叉搜索树，它产生有序键。子树为空时停止递归。前序与后序遍历对当前节点的访问位置不同。

平衡树可把搜索层数降至对数级，但在不平衡树中按有序顺序连续插入，可能形成很长的链。应根据实际树形分析效率，而不是默认所有树都平衡。

图中树的中序遍历是什么？查看答案

是 1、3、6、8、12。每个节点都在它的左右子树之间访问。

我们在编写本课程时参考了这些官方文件，用以确定考纲结构和课程要求。

International Baccalaureate · 2027 年首次评估

此 PDF 为 IB 公开学科简介。完整学科指南与评估要求可通过学校或 IB 课程资源中心获取。