内存中的栈与堆 - Shaw 的小屋

p29（13 分钟）

这一节没有新算法，全是程序运行时的内存模拟，但它是理解递归和指针的关键铺垫。

程序内存的四个区段#

区段	用途	大小
文本段	存储程序中所有指令（编译后的机器语言形式）	编译时确定，固定
全局变量区	存储所有全局变量（所有函数之外声明的变量）	编译时确定，固定
栈	函数调用执行的临时空间；所有局部变量都存在栈中	编译时确定，固定
堆	动态内存，可按需增长或收缩	运行时增长

核心区别就一条：

1
其他所有区段大小在编译时确定且固定
2
堆在运行时可以增长
3

4
运行期间我们无法控制其他区段的内存分配或释放
5
但可以控制堆中的分配和释放

这是理解「为什么链表/树的节点必须建在堆上」的根本原因。

栈帧#

每当调用一个函数，都会从栈中为其执行分配一定量的内存，这块内存称为该函数调用的栈帧。

1
所有局部变量和函数调用的执行状态都存储在该函数调用的栈帧里
2
每当一个函数调用结束，为其分配的栈帧都会被回收

栈中内存在函数调用结束时自动释放。

逐步模拟：插入 15、10、20、25#

前提：root 是 main 的局部变量。

main 开始执行#

1
为 main 分配栈帧
2
局部变量 root（指向 BST 节点的指针）未初始化 → 设为 NULL
3
（NULL 只是地址 0 的一个宏）

调用 insert(root, 15)#

1
main 的执行暂停
2
为 insert 分配新栈帧，局部变量 root、data 收集本次调用的参数
3
此调用中 root 为空 → 进入第一个 if → 调用 getNewNode
4
insert 再次暂停
5
为 getNewNode 分配栈帧，局部变量：data（收参数）和 node* newNode
6
new 在堆中创建节点，假设得到地址 200
7
  → 存入 newNode → 设置三字段：data = 15、左子 = NULL、右子 = NULL
8
getNewNode 返回 200 并结束 → 其栈帧被回收
9
insert 在这一行恢复：root（insert 的局部变量）= 200
10
  → insert 返回该 root 里的地址 200 并结束 → 栈帧回收
11
main 恢复，main 的 root 被设为 200

调用 insert(root, 10)#

1
main 暂停 → 新 insert 栈帧
2
此调用 root = 200 不为空 → 比较 10 < 15 → 走递归分支
3
此 insert 暂停 → 为另一次 insert 调用分配新栈帧
4
   传入 root = 0（200 的左孩子为空）、data = 10
5
新调用中 root == NULL → 进入第一个 if → 调用 getNewNode
6
   → 堆中创建节点，假设地址 150 → 返回 150 → 栈帧回收
7
上层 insert 恢复：200 节点的左孩子 = 150（链接建立）
8
   → 该 insert 结束，返回 200
9
main 恢复：root 被重写为 200（与之前相同，无变化）

调用 insert(root, 20)#

1
堆中有一个值为 20 的节点作为 200 节点的右孩子，假设地址 300
2
→ 200 节点的右孩子地址被设为 300

调用 insert(root, 25)#

1
main 暂停 → insert 调用，传入 root = 200、data = 25
2
25 > 15 → 进入最后的 else（右子树插入）
3
   → 发起递归调用：传入 root = 300、data = 25
4
该调用中 25 > 20 → 又一次进入最后 else
5
   → 再递归：传入 root = 0（右子树为空）
6
该调用 root == NULL → 进入第一个 if → getNewNode → 假设地址 100 → 返回 100
7
顶层调用恢复：把新节点地址 100 设为右孩子 → 该调用完成，返回 300
8
下层调用恢复：从最后 else 里那一行继续 → 300 节点的右孩子 = 100 → 返回 300
9
再下层：从最后 else 继续 → 200 节点的右孩子被设置为 300（覆盖后不变）
10
main 恢复：root 被设为本次 insert 调用的返回值，用相同的值 200 覆盖

递归的本质#

一个函数自己调用自己，跟一个函数 A 调用另一个函数 B 没什么不同。所以每次递归调用都会分配一个新的栈帧。

结论#

关键在最后一步：main 里的 root，以及节点中的所有链接，都必须得到恰当的更新。

很多 bug 就出在这儿——代码里丢了某些链接，或者多建了不必要的链接。这就是「必须接住返回值」的深层原因：root->left = insert(root->left, data) 这个赋值动作，就是「把链接更新回去」的那一步。漏了它，链接就丢了。

堆 vs 栈的生命周期对比#

	栈	堆
分配时机	函数调用时自动	运行时主动请求（malloc / new）
释放时机	函数调用结束时自动释放	必须显式 free / delete
可控性	无法控制	可以控制
不释放会怎样	自动回收	该内存一直处于已分配状态直到程序结束

堆中申请的任何内存都必须用 C 的 free 或 C++ 的 delete 显式解除分配，否则该内存一直处于已分配状态直到程序结束。这就是内存泄漏的定义。

收尾#

内存本身是一种线性结构。

树能适配进线性内存，靠的是节点随机分布在堆里、通过指针相互连接。这也解释了为什么树不需要连续内存，以及为什么链表、树、图这些非线性结构都能存在。

坑#

局部变量在栈上，函数返回就没了，所以不能返回指向局部变量的指针；节点必须建在堆上。
堆内存必须显式释放，不释放就是内存泄漏。
每次递归调用都会分配新的栈帧，递归深度过大就是栈溢出；递归调用的参数是副本，函数内改参数不影响调用方。
root->left = insert(...) 这个赋值不能漏，它就是「把链接接回去」的那一步。
栈的大小编译时固定，堆是运行时增长的。