Lecture 18: 树、遍历与搜索；从 C 到 LC-3 汇编 (Trees, Traversal and Search; From C to LC-3 Assembly with Linked Data Structures)
Lecture 18: 树、遍历与搜索；从 C 到 LC-3 汇编 (Trees, Traversal and Search; From C to LC-3 Assembly with Linked Data Structures)
概述
本讲把上一讲的”一个结点带一条链”推广为”一个结点带两条链”，得到二叉树 (binary tree)，并在此基础上实现二叉搜索树 (binary search tree, BST) 的插入、查找与三种深度优先遍历。 关键的新机制是递归与自引用结构的组合：遍历、求高度、统计结点数、整树释放全部写成递归函数，其中整树释放必须使用后序遍历 (postorder)。 最后我们把一个递归树函数手工翻译成 LC-3 汇编，看清 p->value、p = p->left 如何变成带常量偏移的 LDR，以及为什么任何含子程序调用的函数都必须在栈帧中保存 R7——这正是 ECE 220 “C 语句如何变成机器码”这一教学目标的核心演练。
核心概念与底层机制图解
- 树 (tree) 作为层级式指针结构：每个结点可以有多个后继，且无环；从根到任一结点恰有一条路径。
- 直观解释：像家族谱系或文件系统的目录树——每个”父亲”可以有若干个”儿子”，但每个结点只有一个”父亲”。
- 底层机制图解：树的实现方式有两类。指针式 (pointer-based)：结点用
malloc分配在堆上，用指针成员连接（本讲bst.c）；数组式 (array-based)：所有结点放在一个数组里，用下标算式表达父子关系——课程的金字塔树 (pyramid tree) 就是后者，mp9.c中下标N的结点其子结点下标为4N+1…4N+4，叶子结点直接对应图的顶点，从而整棵树只需一次malloc、遍历时缓存友好。 - 作用域与存储期：指针式树的结点是 allocated storage duration，必须逐结点
free；数组式树的结点随那一个数组一起生死，释放只需一次free。
- 二叉树结点 (binary tree node) 与内存布局：
struct node_t { node_t* left; int32_t value; node_t* right; };- 直观解释：每个结点像一张卡片，卡片上写着”左孩子在哪个房间、右孩子在哪个房间、我自己是多少”。
- 底层机制图解：
left在偏移 0、value在偏移 1、right在偏移 2（LC-3 按 16 位字编址）；64 位平台上含填充共 24 字节，其中 16 字节是”结构开销”。p->value编译成LDR R1,R0,#1，p = p->left编译成LDR R0,R0,#0，都是一条指令——结构体成员访问就是”基址 + 编译期常量偏移”。
二叉树的内存布局图解（结点散布在堆上，用两个指针连接）：
栈（automatic） 堆（allocated）
+-------------+ +----------------+ +----------------+ +----------------+
| root = 0x8A00|---> | left = 0x8B40 |--------->| left = 0x0000 | | left = 0x0000 |
+-------------+ | value = 50 | | value = 30 | | value = 20 |
| right = 0x8C20 |---+ | right = 0x8D60 |---> | right = 0x0000 |
+----------------+ | +----------------+ +----------------+
@0x8A00 | @0x8B40 @0x8D60
v
+----------------+ +----------------+
| left = 0x8F00 | | left = 0x0000 |
| value = 70 | | value = 80 |
| right = 0x8F90 |---> | right = 0x0000 |
+----------------+ +----------------+
@0x8C20 @0x8F90
注意：父结点与子结点的地址毫无关系；树的"形状"完全由指针字段表达
- 二叉搜索树的有序不变量 (BST ordering invariant)：对任意结点
n，其左子树所有值 <n->value< 右子树所有值。- 直观解释：像一本按字母排好的电话簿：左边全是”更小的”，右边全是”更大的”。
- 底层机制图解：不变量约束的是整棵子树而不是直接孩子：
left->value < n->value只是它的必要条件，不是充分条件。它带来的直接好处是”每次比较都能丢弃一棵子树”，于是查找路径长度等于树高h，平均O(log n)。 - 作用域与存储期：不变量是所有修改函数共同维护的契约（
insert/delete/旋转都要保证），一旦某个函数破坏它，search会静默地找不到存在的元素——这类 bug 最难调试。
- 插入 (insertion)：沿查找路径下降，走到
NULL处挂上新结点。- 直观解释：像按字母顺序往书架上插书，一路比较，找到空位就放进去。
- 底层机制图解：递归写法直接使用返回值回填父子链接：
root->left = insert(root->left, value);——这是”用返回值修改指针字段”的技巧；迭代写法则需要node_t** find（与上一讲链表的指针的指针完全同源）。时间复杂度O(h)，插入顺序决定树的形状。 - 作用域与存储期：新结点由
malloc分配，挂到树上后其生命周期由”谁负责free整棵树”决定；函数返回时只有局部变量消失，结点留在堆上。
- 查找与其
O(height)代价 (search and its cost)：从根出发，比较后只走一边。- 直观解释：像查字典——比目标小就翻左边，比目标大就翻右边。
- 底层机制图解：迭代版本只用一个指针变量，无需递归，空间
O(1)：while (NULL != root && value != root->value) { root = (value < root->value) ? root->left : root->right; }。代价取决于树高h：平衡时h ≈ log2(n)，退化时h = n - 1（下一节）。 - 作用域与存储期：
search返回指向堆中结点的指针；只要不free，该指针一直有效；但一旦整树被释放，所有旧指针立即变成悬垂指针。
- 三种深度优先遍历 (depth-first traversals)：区别只在于”什么时候处理根结点”。
- 直观解释：把每个结点的工作分成”打印自己、走左子树、走右子树”三件事，三种顺序对应三种遍历。
- 底层机制图解：以本讲
bst.c实际插入顺序50, 30, 70, 20, 40, 60, 80建成的树为例：
50
/ \
30 70
/ \ / \
20 40 60 80
前序 preorder (根, 左, 右): 50 30 20 40 70 60 80
中序 inorder (左, 根, 右): 20 30 40 50 60 70 80 <- 升序！
后序 postorder (左, 右, 根): 20 40 30 60 80 70 50
层序 breadth-first (用队列): 50 30 70 20 40 60 80
**为什么 BST 的中序是升序**：对任意结点，中序先完整输出它的左子树（全比它小），再输出它自己，最后输出右子树（全比它大）；由数学归纳法，整个序列严格递增。这也是验证 BST 正确性的标准手段。
* *作用域与存储期*：递归遍历的每个活动调用在自己的栈帧里保存一份局部变量与返回地址，递归深度等于树高 `h`，因此栈空间开销是 `O(h)`；对退化的 `n = 10^5` 的链状树，递归会耗尽栈（stack overflow）。
- 递归统计与整树释放 (recursive metrics and teardown)：高度、结点数、求和都可以用同一种”左右递归 + 合并”模板；释放则必须后序。
- 直观解释：数一棵树有多少片叶子，先数左半边再数右半边；拆房子则必须先拆完上面两层，才能拆地基。
- 底层机制图解：
count(n) = 1 + count(left) + count(right)，sum(n) = n->value + sum(left) + sum(right)，height(n) = 1 + max(height(left), height(right))（空树高度定义为-1，使单结点树高度为 0）。释放必须是free_tree(left); free_tree(right); free(n);——若先free(n)就再也拿不到两个子结点地址了。课程的trees.c里free_tree正是三叉版本：先递归释放right、mid、left，最后free (n)。 - 作用域与存储期：递归函数每层的局部变量都是 automatic，随该层栈帧销毁；堆上的结点只有在对应的
free之后才结束生命周期。
- 退化与平衡 (degeneration and balance)：按升序插入
1, 2, …, n得到的是一棵”只有右孩子的链”，高度n - 1。- 直观解释：每次新元素都最大，于是永远往右走——树长成了一根竹竿。
- 底层机制图解：本讲
bst.c实测：插入1..8得到的树height = 7, nodes = 8，search退化为O(n)，递归的栈深度也变成n。平衡带来的收益是h = O(log n)：n = 10^6时h ≈ 20而不是10^6。保持平衡需要旋转 (rotation)（AVL 树、红黑树）或随机化插入顺序；平衡的代价是每次修改多几次指针改写。
- 广度优先遍历 (breadth-first traversal)：用队列逐层访问，不需要递归。
- 直观解释：像水波纹一圈圈扩散：先看根，再看根的两个孩子，再看四个孙子……
- 底层机制图解：把根入队，然后循环”出队一个、访问它、把它的非空孩子依次入队”。队列可以用上一讲的链式队列，也可以用环形数组（
bst.c用的是简单数组 +head/tail下标）。BFS 与 DFS 的差别只在容器：栈 → DFS，队列 → BFS。 - 作用域与存储期：BFS 的队列所需空间正比于树的最大宽度（最坏
n/2），DFS 的栈空间正比于树高——这是选择遍历策略时的重要工程权衡。
- 结构层级与”首字段包含” (hierarchies of structures)：把共同字段放进父类型，并让父类型作为子类型的第一个字段，就能安全地把子类型指针向上转型。
- 直观解释：所有证件的第一页都是”姓名 + 照片”，于是不管后面的内容是驾驶证还是护照，只看第一页都能当”身份证”来处理。
- 底层机制图解：课程例子里
book_t的第一个字段是reference_t，reference_t的第一个字段是double_list_t；因为偏移为 0，book_t*、reference_t*、double_list_t*三者的地址完全相同，向上转型（(reference_t*)elt）是安全的。反过来从父类型指针转到子类型不安全：仅凭reference_t*无法知道后面跟着的是什么，必须先有一个type字段做动态类型标记，再用switch分派。这正是 C 语言里”虚函数”的手工实现方式（对比 Lecture 12 的函数指针回调）。
代码示例与底层机制分析
示例 1：二叉搜索树的插入、查找、四种遍历与统计
代码 (C) — /tmp/ece220_l18/bst.c（完整文件已编译运行）：
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t node_t;
struct node_t {
node_t* left;
int32_t value;
node_t* right;
};
static node_t* make_node(int32_t value)
{
node_t* n = malloc(sizeof(*n));
if (NULL == n) {
fprintf(stderr, "out of memory\n");
exit(2);
}
n->left = NULL;
n->right = NULL;
n->value = value;
return n;
}
/* 返回新的子树根；维持 left < node < right 的不变量 */
static node_t* insert(node_t* root, int32_t value)
{
if (NULL == root) {
return make_node(value);
}
if (value < root->value) {
root->left = insert(root->left, value);
} else if (value > root->value) {
root->right = insert(root->right, value);
}
return root;
}
static node_t* search(node_t* root, int32_t value) /* 迭代版：O(height)，空间 O(1) */
{
while (NULL != root && value != root->value) {
root = (value < root->value) ? root->left : root->right;
}
return root;
}
static void preorder(node_t* root) /* 根, 左, 右 */
{
if (NULL == root) {
return;
}
printf(" %d", root->value);
preorder(root->left);
preorder(root->right);
}
static void inorder(node_t* root) /* 左, 根, 右 */
{
if (NULL == root) {
return;
}
inorder(root->left);
printf(" %d", root->value);
inorder(root->right);
}
static void postorder(node_t* root) /* 左, 右, 根 */
{
if (NULL == root) {
return;
}
postorder(root->left);
postorder(root->right);
printf(" %d", root->value);
}
static int32_t height(node_t* root)
{
int32_t lh;
int32_t rh;
if (NULL == root) {
return -1; /* 空树高度 -1，单结点树高度 0 */
}
lh = height(root->left);
rh = height(root->right);
return 1 + ((lh > rh) ? lh : rh);
}
static int32_t count(node_t* root)
{
if (NULL == root) {
return 0;
}
return 1 + count(root->left) + count(root->right);
}
static int32_t sum(node_t* root)
{
if (NULL == root) {
return 0;
}
return root->value + sum(root->left) + sum(root->right);
}
static void free_tree(node_t* root) /* 必须后序：先孩子后自己 */
{
if (NULL == root) {
return;
}
free_tree(root->left);
free_tree(root->right);
free(root);
}
验证到的真实输出（gcc -g -std=c99 -Wall -Werror bst.c -o bst && ./bst）：
preorder : 50 30 20 40 70 60 80
inorder : 20 30 40 50 60 70 80
postorder : 20 40 30 60 80 70 50
breadth : 50 30 70 20 40 60 80
height = 2, nodes = 7, sum = 350
search 60 -> found
search 65 -> no
balanced tree: allocated = 7, freed = 7
degenerate tree 1..8: height = 7, nodes = 8
inorder of degenerate tree is still sorted: 1 2 3 4 5 6 7 8
total allocated = 15, freed = 15
【代码做什么？】
- 以
50, 30, 70, 20, 40, 60, 80的顺序调用insert，每次下降比较后挂到NULL位置，得到根为 50、高度为 2 的完全二叉树。 preorder/inorder/postorder分别按”根左右 / 左根右 / 左右根”输出，得到50 30 20 40 70 60 80/20 30 40 50 60 70 80/20 40 30 60 80 70 50。breadth_first用数组队列逐层输出50 30 70 20 40 60 80。height返回 2（以边数计），count返回 7，sum返回 350 = 50+30+70+20+40+60+80，三者都由递归合并子树结果得到。search(root, 60)命中返回结点地址，search(root, 65)走到NULL返回空。free_tree后分配/释放计数 7 = 7；再插入1..8得到退化树，实测height = 7, nodes = 8，但其中序仍然是升序，说明不变量未被破坏、退化的只是形状。
【底层机制透视】 insert 用 root->left = insert(root->left, value); 这种”把递归结果写回指针字段”的写法，好处是插入新结点时不需要区分特例：当 root->left == NULL 时递归返回新结点地址，赋值语句恰好把它挂上。 递归函数的每一层都在栈上占一个栈帧，因此遍历的空间开销是 O(h)；height 的递归分叉是”两次调用 + 取较大值”，属于树形递归，总调用次数为 2n + 1。 search 写成迭代版是为了强调：递归不是必需的，只要每步只走一条分支就可以用循环。反之，需要访问两条分支（遍历、统计、释放）时，用递归保存”另一半还没做”的状态最自然。 free_tree 若改成前序（先 free(root) 再递归孩子），会在 free 之后读 root->left，属于 UB；这也是本讲最常见的错误。
【内存布局图解】 以插入顺序 50, 30, 70, 20, 40, 60, 80 建成的树为例（地址为示意）：
栈 堆
+-------------+ +----------------+ +----------------+ +----------------+
| root=0x8A00 |-->| left = 0x8B40 |-->| left = 0x8D60 | | value = 20 |
| p =0x8C20 | | value = 50 | | value = 30 | | left = 0x0000 |
+-------------+ | right = 0x8C20 | | right = 0x8E10 | | right = 0x0000 |
+----------------+ +----------------+ +----------------+
@0x8A00 (50) @0x8B40 (30) @0x8D60 (20)
\
+---------> +----------------+ +----------------+
| value = 70 | | value = 80 |
| left = 0x8F00 | | right = 0x0000 |
| right = 0x8F90 |-->| @0x8F90 |
+----------------+ +----------------+
@0x8C20 (70) (80)
inorder 访问顺序：0x8D60 -> 0x8B40 -> 0x8E10 -> 0x8A00 -> 0x8F00 -> 0x8C20 -> 0x8F90
即 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80（地址乱序，值有序）
【与汇编的对应】 p->value、p->left、p->right 都是一条 LDR；比较后用条件分支选择走哪边：
; ---- search：while (root != NULL && value != root->value) ----
; 参数：root 在 R5+4，value 在 R5+5
SEARCH LDR R0,R5,#4 ; R0 = root
LDR R1,R5,#5 ; R1 = value
S_LOOP BRz S_NULL ; root == NULL ? 没找到
LDR R2,R0,#1 ; R2 = root->value （value 在偏移 1）
NOT R3,R2
ADD R3,R3,#1 ; R3 = -root->value
ADD R3,R3,R1 ; R3 = value - root->value
BRz S_FOUND ; 相等，命中
BRn S_GO_LEFT ; value < root->value
LDR R0,R0,#2 ; root = root->right （right 在偏移 2）
BRnzp S_LOOP
S_GO_LEFT
LDR R0,R0,#0 ; root = root->left （left 在偏移 0）
BRnzp S_LOOP
S_NULL AND R0,R0,#0 ; 返回 NULL
BRnzp S_DONE
S_FOUND LDR R0,R5,#4 ; 返回命中的结点地址
S_DONE STR R0,R5,#3 ; 写入返回值槽
RET
示例 2：把树”压平”成数组再复原（课程的 flattening 例子）
代码 (C) — /tmp/ece220_l18/flatten.c（核心部分；课程原版为 Ccode/flattening/trees.c，三叉树）：
#define ABSENT 0x80000000
/* 孩子先写、结点最后写 —— 这正是后序（左, 中, 右, 根）*/
static int32_t pack(node_t* root, int32_t ar[], int32_t pos)
{
if (NULL == root) {
ar[pos] = ABSENT;
return pos + 1;
}
pos = pack(root->left, ar, pos);
pos = pack(root->mid, ar, pos);
pos = pack(root->right, ar, pos);
ar[pos] = root->value;
return pos + 1;
}
/* 从数组末尾倒着读：先读根，再读右、中、左 */
static node_t* build(const int32_t ar[], int32_t* pos)
{
int32_t v = ar[--(*pos)];
node_t* n;
if (ABSENT == v) {
return NULL;
}
n = make_node(v);
n->right = build(ar, pos);
n->mid = build(ar, pos);
n->left = build(ar, pos);
return n;
}
验证到的真实输出：
packed : ABSENT ABSENT ABSENT 5 ABSENT ABSENT ABSENT ABSENT 6 2 ABSENT ABSENT ABSENT 3 ABSENT ABSENT ABSENT ABSENT 7 ABSENT 4 1
build consumed 22 of 22 words
repacked : ABSENT ABSENT ABSENT 5 ABSENT ABSENT ABSENT ABSENT 6 2 ABSENT ABSENT ABSENT 3 ABSENT ABSENT ABSENT ABSENT 7 ABSENT 4 1
repacked identical: yes
课程原版 trees.c 用真实输入文件做往返 (round trip) 测试，我也实际编译运行过：
$ gcc -g -std=c99 -Wall -Werror trees.c -o trees
$ ./trees sample out # 读入 sample，反压平成树，再压平写回 out
$ diff sample out && echo IDENTICAL
IDENTICAL
（sample 的首行是数组长度 25，随后 25 个 int32_t 数据，其中 -2147483648 即 ABSENT 标记，代表”空子树”。）
【代码做什么？】
pack递归压平三叉树：遇到NULL子树就写一个ABSENT标记，否则先写左、中、右三棵子树，最后写自己的值。- 输出显示 22 个数据字，末尾的
4 1说明根结点1的值写在数组最后——因为它是最后被”完成”的。 build从数组末尾倒着读：第一个读出的是根1，然后依次递归还原right、mid、left，与写入顺序严格互逆。build consumed 22 of 22 words说明数组被完整消费；重新pack得到的数组与原始数组逐字相同（repacked identical: yes），证明压平/复原是无损可逆的。- 课程的
trees.c更进一步：它故意构造三种错误输入（数组过长、数组有剩余、结构非法），并检查程序是否正确地报错退出；对合法输入则diff sample out完全一致。
【底层机制透视】 压平的本质是遍历顺序即存储顺序：pack 写出的是”左-中-右-根”的后序序列，而 build 从尾部倒着读，恰好按”根-右-中-左”消费。之所以要倒着读，是因为根必须最先被创建，而根在数组末尾。 pack 用返回值把”下一个待写位置”传回上层（return pos + 1;），这与 insert 用返回值回填指针是同一种函数式风格：用返回值串起递归的状态。 这种”把指针结构序列化成整数数组”的技术在系统编程中极常见：网络协议要把对象树打包成字节流、编译器要把 AST 序列化到文件、pyr_tree.c 干脆就把整棵金字塔树存成一个 pyr_node_t 数组（struct pyr_tree_t { int32_t n_nodes; pyr_node_t* node; }），因为数组版本可以一次性 malloc、一次性 free、并且对缓存友好。
【内存布局图解】
树（指针式，堆上） 压平后的数组（连续内存）
1 下标: 0 1 2 3 4 ... 18 19 20 21
/ | \ +------+------+------+------+---+-----+----+----+----+----+
2 3 4 |ABSENT|ABSENT|ABSENT| 5 |...| ... | 7 |ABSENT| 4 | 1 |
/ \ | +------+------+------+------+---+-----+----+----+----+----+
5 6 7 ^ ^ ^
^ ^ ^ | | |
空子树写成 ABSENT，占用一个数组槽 每个 "孩子槽" 都有位置 中间结点在后 根在最后
build 从下标 21 开始倒着读：21->根1, 20->右孩子4, 19->ABSENT, ... 直到下标 0
【与汇编的对应】 pack 的”孩子先、自己后”决定了两条递归 JSR 必须写在 STR 之前：
; ---- pack(root, ar, pos)：root 在 R5+4，ar 在 R5+5，pos 在 R5+6 ----
; 局部：R5+0 = 当前 pos（因为递归调用会破坏 R0-R3，必须存回栈帧）
PACK LDR R0,R5,#4 ; R0 = root
LDR R1,R5,#5 ; R1 = ar
LDR R2,R5,#6 ; R2 = pos
STR R2,R5,#0 ; 把 pos 存进局部变量
BRnp P_NOT_NULL
; root == NULL：写 ABSENT，返回 pos + 1
LEA R3,ABSENT_VAL ; 以 LEA + LDR 取出 0x80000000
LDR R3,R3,#0
ADD R2,R2,R1 ; 若 ar 已换算为绝对地址，这里直接算出目标地址
STR R3,R2,#0
LDR R2,R5,#0
ADD R2,R2,#1
STR R2,R5,#3 ; 返回值槽 = pos + 1
BRnzp P_DONE
P_NOT_NULL
; 依次递归 left / mid / right，每次都用上一次的返回值更新 pos
LDR R0,R5,#4
LDR R0,R0,#0 ; left 在偏移 0（若结构为 value,left,mid,right 需相应调整）
; ... 压栈调用 PACK，读回返回值写回局部 pos ...
; ... 对 mid、right 重复 ...
LDR R2,R5,#0 ; 取出最终的 pos
LDR R3,R5,#4
LDR R3,R3,#3 ; 取 root->value
; ar[pos] = value; 返回值 = pos + 1
P_DONE LDR R7,R5,#2
LDR R5,R5,#1
ADD R6,R6,#3
RET
示例 3：把递归树函数翻译成 LC-3（本讲核心）
代码 (C) — 取自 /tmp/ece220_l18/bst.c 的 sum，为便于逐句翻译写成显式局部变量的形式：
int32_t tree_sum (node_t* root)
{
int32_t total;
if (NULL == root) {
return 0;
}
total = root->value;
total += tree_sum (root->left);
total += tree_sum (root->right);
return total;
}
验证到的真实输出：bst.c 中同一逻辑的 sum(root) 打印 sum = 350（对 7 个结点 20+30+40+50+60+70+80），与手算一致。
【代码做什么？】
- 若
root为空，直接返回 0（递归的基例 (base case)）。 - 否则把
root->value存入局部变量total。 - 递归求左子树之和，把返回值累加到
total。 - 递归求右子树之和，再次累加。
- 返回
total。
【底层机制透视】 这个函数是非叶函数 (non-leaf function)：它自己会调用子程序。这带来两个硬约束： ①JSR 会把返回地址写进 R7，覆盖本函数自己的返回地址，所以必须在序言里把 R7 存进栈帧（STR R7,R5,#2），否则第一次递归调用后本函数就无法 RET； ②R0–R3 是 caller-saved，两次递归调用之间的 total 必须放在栈帧里的局部变量（内存）而不是寄存器里。 第二个递归调用之前需要重新读取 root：它保存在本帧的参数槽 R5+4，而参数槽属于本帧，在整个函数执行期间保持有效——这正是”参数按值传递并存放在被调用者栈帧里”的工程价值。
栈帧布局（与课程讲义及 translate.asm 一致）：
高地址 ┌──────────────────────────┐
│ caller's stack frame │
├──────────────────────────┤
│ parameters: root │ <- R5+4 （由调用者压栈）
├──────────────────────────┤
│ previous frame pointer │ <- R5+3
├──────────────────────────┤
│ return address (R7) │ <- R5+2 （STR R7,R5,#2）
├──────────────────────────┤
│ return value │ <- R5+1 （STR R0,R5,#1）
├──────────────────────────┤
│ local variables │ <- R5+0, R5-1, ... （R5 指向局部变量底部）
低地址 └──────────────────────────┘ <- R6 指向栈顶（向低地址增长）
说明：上表偏移取自课程讲义与
translate.asm/ MT1 复习课的指令序列（STR R0,R5,#3 ; store -1 in return value location、LDR R5,R5,#1 ; restore caller's frame pointer）。个别资料把 linkage 三格的编号顺序写得不同，遇到冲突时以讲义中的指令为准（因为只有”返回值紧贴参数下方”这一顺序，调用者才能在不知道被调用者局部变量个数的情况下，用一条ADD R6,R6,#N同时弹出返回值与参数）。
【内存布局图解】（以 tree_sum(0x8A00) 在求左子树之和的瞬间为例）
R5+4 │ root = 0x8A00 │ 本帧参数（指向 50 号结点）
R5+3 │ prev frame = 0x7Fxx│ 调用者的 R5
R5+2 │ return addr │ 调用者中 tree_sum 之后的那条指令地址
R5+1 │ return value │ 尚未写入
R5+0 │ total = 50 │ 局部变量：root->value
R6 -> │ 子调用 tree_sum(0x8B40) 的栈帧（更深，地址更低）
└────────────────────┘
左子树返回后：total = 50 + 30；再调用 tree_sum(0x8C20) 求右子树
【与汇编的对应】 完整、逐句对照的 LC-3 翻译（结构偏移：left = 0、value = 1、right = 2）：
; ============================================================
; tree_sum (root)
; 参数：root 在 R5+4 返回：和写入 R5+1 槽
; 局部：R5+0 = total
; ============================================================
TREE_SUM
ADD R6,R6,#-4 ; 申请 4 个槽：3 个 linkage + 1 个局部变量
STR R5,R6,#1 ; 保存调用者的帧指针（R5 = R6，故写在 R5+1）
ADD R5,R6,#0 ; R5 = 局部变量底部
STR R7,R5,#2 ; *** 必须先存 R7：后面的 JSR 会覆盖它 ***
LDR R0,R5,#4 ; R0 = root
BRnp TS_NONZERO ; root != NULL ?
AND R0,R0,#0 ; 是：返回 0
STR R0,R5,#1 ; 写入返回值槽（R5+1）
BRnzp TS_TEARDOWN
TS_NONZERO
LDR R1,R0,#1 ; R1 = root->value （value 在偏移 1）
STR R1,R5,#0 ; total = root->value
; ---- total += tree_sum (root->left) ----
LDR R0,R0,#0 ; R0 = root->left （left 在偏移 0）
ADD R6,R6,#-1
STR R0,R6,#0 ; 压入参数 root->left
JSR TREE_SUM ; 调用（R7 被覆盖，但已在 R5+2 中有备份）
LDR R1,R6,#0 ; R1 = 返回值（返回后位于栈顶）
ADD R6,R6,#2 ; 弹出返回值与参数
LDR R2,R5,#0 ; R2 = total
ADD R2,R2,R1
STR R2,R5,#0 ; total += 左子树之和
; ---- total += tree_sum (root->right) ----
LDR R0,R5,#4 ; 重新取回 root（参数槽一直有效）
LDR R0,R0,#2 ; R0 = root->right （right 在偏移 2）
ADD R6,R6,#-1
STR R0,R6,#0
JSR TREE_SUM
LDR R1,R6,#0
ADD R6,R6,#2
LDR R2,R5,#0
ADD R2,R2,R1
STR R2,R5,#1 ; 返回值槽 = total
TS_TEARDOWN
LDR R7,R5,#2 ; 恢复返回地址（两次 JSR 已经改过 R7）
LDR R5,R5,#1 ; 恢复调用者的帧指针
ADD R6,R6,#3 ; 弹掉局部变量与 linkage，留下返回值在栈顶
RET
对照要点：p->value → LDR R1,R0,#1；p = p->left → LDR R0,R0,#0；递归调用 → “压参数 + JSR + 读栈顶返回值 + 弹栈”四步；函数结尾统一走 TS_TEARDOWN，保证多条 return 路径共享同一段收尾代码。
常见错误与调试技巧
- 释放顺序错误：写成
free(n); free_tree(n->left);会读已释放内存（UB），通常表现为崩溃或”释放了不存在的指针”。 调试：valgrind -q ./prog报 “Invalid read of size 8” 并把free_tree的行号指出来；正确顺序是左、右、自己。 - BST 不变量被破坏：只在直接孩子处比较大小（例如插入时写成与祖父比较），结果是
search找不到明明插入过的值。 调试：写一个check_bst(root)，用中序遍历检查输出严格递增；或gcc -fsanitize=address配合断言assert(prev < n->value)。 - 忘记
malloc失败检查：n = malloc(...); n->value = ...;在内存不足时对NULL解引用。 调试：gdb -tui --args ./prog在SIGSEGV处bt看调用栈；养成if (NULL == n) { return NULL; }并与上层错误路径配合（参考read_packed_tree的层层回滚写法）。 - 递归没有基例或基例写错：例如
inorder忘了if (NULL == root) return;，会立即解引用NULL崩溃；若基例写成return却漏了空指针检查，则表现为栈溢出。 调试：gdb中bt 20查看重复帧判断递归是否收敛；ulimit -s查看栈上限，用valgrind观察栈增长。 - 退化树导致栈溢出：按有序数据插入 10 万个元素，
height = 99999，递归遍历会耗尽 8 MB 栈。 调试：gdb捕获SIGSEGV后bt显示成千上万个同名帧；改用迭代遍历（显式栈）或使用平衡树。 - 释放后继续用
root：free_tree(root); printf("%d\n", root->value);是 UB。 调试：valgrind --leak-check=full ./prog同时报告泄漏与非法访问；释放后立即把指针置NULL并只通过一个包装函数访问。 - 忘记保存 R7 就递归（写 LC-3 时）：第一次
JSR后R7被覆盖，函数末尾RET跳回错误地址，程序”乱飞”。 调试：在 LC-3 模拟器中单步执行，观察RET前后PC是否落在调用点之后；规则是”只要函数体内有JSR，序言必须STR R7,R5,#2，收尾必须LDR R7,R5,#2“。
关键要点
- 树的形状由指针字段表达，地址毫无规律；”层级”是逻辑关系，不是物理位置。
- BST 的核心是整棵子树意义上的有序不变量
left < node < right；中序遍历输出升序是它最直接的验证手段。 - 递归与树天生匹配：遍历、计数、求和、求高度、释放都是”递归左右 + 合并结果”的同一模板；整树释放必须后序（先孩子后自己）。
- 树高决定一切代价：查找
O(h)、递归栈O(h)；有序插入会退化成链（实测n = 8时h = 7），平衡或随机化才能保住O(log n)。 - 在 LC-3 中，含递归的函数必须做完整帧管理：序言保存
R5与R7并设置R5，收尾用LDR R7,R5,#2、LDR R5,R5,#1、ADD R6,R6,#N三步恢复后RET；跨调用需要保留的值一律放进栈帧局部变量。
思考题（带答案）
问题 1：下面这个 size 函数能正确统计结点数吗？如果树是退化的（只有左孩子），会发生什么？
static int32_t size(node_t* root)
{
return 1 + size(root->left) + size(root->right);
}
答案：不能。它缺少基例 if (NULL == root) { return 0; }，一旦走到空子树就会解引用 NULL 而崩溃（在 LC-3 中则是 LDR 访问地址 0，读到的是系统区内容，行为不可预测）。补上基例后公式 1 + size(left) + size(right) 是正确的。退化树不会改变正确性，但会让递归深度等于 n，n 很大时导致栈溢出。
问题 2：给出一棵插入顺序，使 50, 30, 70, 20, 40, 60, 80 这七个值构成的 BST 高度达到 6，并说明为什么中序遍历仍然是升序。
答案：按升序插入 20, 30, 40, 50, 60, 70, 80（或降序）即可：每个新值都比上一个大，于是永远挂在右孩子位置，得到一条长为 7 的右链，高度 = 6（以边数计；本讲 bst.c 用 1..8 实测得到 height = 7, nodes = 8，规律一致）。中序仍然是升序，因为中序遍历只依赖”左子树 → 根 → 右子树”这一结构顺序，而链状树中每个结点的左子树都为空，访问顺序恰好就是插入时的升序。
问题 3：为什么下面这段 LC-3 序言是错的？
TREE_SUM
ADD R6,R6,#-4
STR R5,R6,#1
ADD R5,R6,#0
; 直接开始执行函数体，函数体中间有 JSR TREE_SUM
答案：缺少 STR R7,R5,#2。函数体会执行 JSR TREE_SUM，而 JSR 把返回地址写入 R7，覆盖了本函数进入时的返回地址；由于从未把它保存到栈帧，收尾处的 LDR R7,R5,#2 只会读到一个未初始化的槽，RET 于是跳到随机地址。规则是：只要函数是”非叶”的（体内有任何 JSR/JSRR），序言就必须保存 R7，收尾必须恢复 R7。