Quartz 4

树与动态内存管理

typedef struct TreeNode {
    int weight;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *BiTree; // <--- 注意这个 *BiTree！

TreeNode：代表 struct TreeNode 这个实体结构体。 BiTree：代表 struct TreeNode* 这个指针类型（把星号隐藏在了 BiTree 这个名字里）。

BiTree root;   等价于   struct TreeNode *root;

当你写 root->left->weight 时： 这就变成了连续两趟跑腿：

root->left  等价于 (*root).left   注：.的优先级比*高所以加括号
  1. ==root->left：先进 root 房子，拿到 left 房间里的门牌号（比如 0x2000）。==
  2. ==->weight：再拿着 0x2000 这个新门牌号跑到第二座房子，把里面的 weight 数字拿出来！== TreeNode类型的结构体指针root的内部结构（成员）和left的内部成员完全一样。 *在结构体里面写struct TreeNode left; 相当于嵌套，叫做结构体的自引用
// 错误写法！编译器直接报错！
struct TreeNode {
    int weight;
    struct TreeNode left; // 企图在套房里再塞一套一模一样的套房
};

如果这么写，编译器会直接崩溃掉：因为定义 TreeNode 需要知道它占多大内存，而它里面又包含一个自己，大小就变成了无穷大（死循环），编译器算不出它到底需要开辟多大的 SRAM 内存。

在 C 语言中，无论指向什么类型的指针，它在内存里占用的空间大小都是固定死的（32位系统下占 4 字节，64位系统下占 8 字节）。编译器一看到星号 *，立刻就知道：“哦！这只是个指针，我知道给它分配多大内存了！” 所以语法完全成立。

只要是动态数据结构（链表、二叉树、图）：必须把指针定义在结构体内部（自引用），因为只有这样，每个节点才能拥有动态连接下一个节点的能力。

指针、结构体自引用与动态内存管理

一、 核心概念：结构体自引用（Self-reference）

1. 什么是自引用？

在结构体内部定义指向同种结构体类型的指针成员。

C

typedef struct TreeNode {
    int weight;                 // 数据域：存储具体数据
    struct TreeNode *left;      // 指针域：存放左孩子的内存地址（门牌号）
    struct TreeNode *right;     // 指针域：存放右孩子的内存地址（门牌号）
} TreeNode, *BiTree;

🔑 避坑指南：

  • 为什么不能写 struct TreeNode left;？

    这是非法嵌套！套房里不能再包含一套完整的实体套房，这会导致结构体大小变为无穷大，编译器无法分配空间。

  • 为什么必须写 struct TreeNode *left;？

    加了星号 * 代表它只是一个指针（门牌号）。指针在内存中占用的空间是固定死的大小（32位系统占 4 字节，64位系统占 8 字节），编译器能精准计算出结构体尺寸。

  • 为什么内部不能直接写 TreeNode *left;？

    因为在编译阶段读到第 3 行时，末尾的别名 TreeNode 还没有正式生效，所以内部必须写完整的原始结构体类型名 struct TreeNode *。

2. 自引用 vs 外部指针的区别

对比维度结构体内部自引用（root→left）外部定义独立的指针（BiTree p;）
物理本质每个节点自己长出了手，自带存放下个节点地址的卡槽。只有程序员手里握着几张孤立的纸条（地址）。
扩展能力无限生长：新节点生成时自带指针，可以像套娃/长链一样一直挂载下去。极度受限：手里的纸条用完就无法再挂载新节点，树的生长被直接切断。

二、 动态内存申请：malloc 拆解

在堆区开辟一个节点的标准写法：

C

BiTree node = (BiTree)malloc(sizeof(TreeNode));

逐字物理拆解：

  1. sizeof(TreeNode) —— 计算真实房子尺寸

    • 作用：询问系统“造一个 TreeNode 实体需要多少字节（Byte）”。

    • 注意：必须填实体类型 TreeNode（约 12 字节），绝对不能填指针类型 BiTree（只有 4 字节，否则会引发严重内存溢出）。

  2. malloc(...) —— 在堆区（Heap）批地皮

    • 作用：向系统申请对应大小的连续内存空间。

    • 返回值：返回新开辟内存的首地址，类型为通用未定型指针 void*。

  3. (BiTree) —— 强制类型转换（贴标签）

    • 作用：告诉编译器“把 malloc 返回的通用 void* 地址，强制翻译为二叉树节点指针类型 BiTree”。

  4. BiTree node = ... —— 保管地址

    • 把转换后的门牌号正式赋值给指针变量 node。

三、 动态内存释放：free

在 C 语言中，栈区变量由系统自动回收，但通过 malloc 在堆区（Heap）申请的内存系统绝不会自动清空。如果不手动清理，就会造成严重的内存泄漏（Memory Leak）。

1. free() 的基本语法

C

free(node);  // 告诉操作系统：这块内存我用完了，可以回收给别人用了
node = NULL; // 【防死针】极其重要！手动把指针置为空

2. free() 的物理过程与致命误区

  • 误区：以为执行 free(node) 后，node 这个指针变量本身被销毁了。

  • 真相：free(node) 销毁的是指针指向的那栋房子（堆内存），指针变量 node 本身（纸条）还完好无损地留在栈里！

  • 悬挂指针（野指针）危局：

    执行 free(node) 后，node 里依然写着之前的门牌号 0x1000。但那栋房子已经被系统拆迁/租给别人了。如果你之后不小心又写了一句 node->weight = 5;，程序就会直接非法访问内存崩溃（Segment Fault）！

🛡️ 黄金法则：free 完必须跟着置空！

C

free(node);
node = NULL; // 让指针指向 NULL（0x00000000），后续再误用它时编译器会立刻报错，便于排查

四、 树/链表结构的销毁原则（先子后父）

当你要销毁一棵二叉树时，绝对不能先 free(root)！

❌ 错误示范：

C

free(root);
free(root->left); // 致命错误！root 已经被删了，你根本找不到 root->left 在哪了！

✅ 正确销毁顺序（后序遍历思想）：

必须“先拆子节点，再拆父节点”！ 先把孩子们的内存销毁掉，最后才能销毁父节点。

C

void destroyTree(BiTree root) {
    if (root == NULL) return;
    
    destroyTree(root->left);  // 1. 先递归销毁左子树
    destroyTree(root->right); // 2. 再递归销毁右子树
    
    free(root);               // 3. 最后释放自己
}

💡 极简记忆口诀：

  • 结构自引：实体不能套实体，指针才能挂自己；

  • 内存申请：sizeof 算实体，强转用指针，malloc 批地皮；

  • 内存释放：free 释放房子不干掉纸条，必须手动 node = NULL 擦纸条；

  • 销毁结构：先断子孙后路，再砍根节点树。

Graph View

Backlinks