C Academy · 课时

搜索与释放

Q: 「搜索与释放」这节课中我会学到什么？

查找节点并释放内存。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

查找节点并释放内存。

第 4 / 4 课13 个步骤

搜索与释放 是 CoddyKit 上的免费 C Academy 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

搜索 BST

搜索利用了节点的排序规则。在每个节点处，我们将目标值与节点值比较，然后只进入其中一个子树。

由于每一步都会舍弃剩余节点的一半，搜索开销取决于树的高度，而不是树的大小。

递归搜索

递归搜索有两种基准情况：空子树表示未找到，匹配的值表示找到。

否则，我们根据比较结果递归进入左子树或右子树。

Node *search(Node *root, int target) {
    if (root == NULL || root->value == target)
        return root;
    if (target < root->value)
        return search(root->left, target);
    return search(root->right, target);
}

迭代搜索

搜索也可以使用一个简单的循环，从而避免递归开销。

我们沿着树向下跟随指针，直到找到目标，或者在 NULL 处到达末端。

Node *search_iter(Node *root, int target) {
    while (root != NULL) {
        if (target == root->value) return root;
        root = (target < root->value)
             ? root->left : root->right;
    }
    return NULL;  /* not found */
}

搜索实践

此程序构建一个 BST，分别搜索一个存在的值和一个不存在的值，并输出每个值是否找到。

返回非 NULL 值表示找到；返回 NULL 表示该值不在树中。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
Node *search(Node *r,int t){
    if(!r||r->value==t) return r;
    return t<r->value ? search(r->left,t) : search(r->right,t);
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("7:%s 99:%s\n",
        search(root,7)?"found":"no",
        search(root,99)?"found":"no");
    return 0;
}

查找最小值

在 BST 中，最小值位于最左侧的节点：不断跟随 left，直到它为 NULL。

同理，最大值位于最右侧的节点。这些辅助函数对删除操作和范围查询很重要。

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

为什么释放很重要

每个节点都来自 malloc，因此每个节点都必须通过 free 归还。忘记释放会造成内存泄漏。

但是，您不能先释放节点，再读取它的子节点指针，因此释放的顺序至关重要。

按后序释放

释放树的安全方法是按后序进行：先释放两个子节点，再释放节点本身。

这样可以确保我们在节点内存被释放之前读取它的 left 和 right 指针。

void free_tree(Node *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

危险的错误顺序

如果在递归进入子节点之前释放节点，就会产生未定义行为：为了访问子树，您会解引用已释放的内存。

这是典型的释放后使用错误。请始终先释放子节点。

/* WRONG: use-after-free */
void bad_free(Node *root) {
    if (!root) return;
    free(root);                 /* freed here */
    bad_free(root->left);       /* reads freed memory! */
    bad_free(root->right);
}

避免悬空指针

free_tree 返回后，原始根指针仍然保存着旧地址，但那块内存已经不存在了。

在调用者中将它重新设置为 NULL，可以防止意外再次使用悬空指针。

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

统计已释放的节点

我们可以在后序遍历过程中统计节点数量，然后逐个释放节点，以确认释放操作正常工作。

此程序构建一棵树，释放它，并报告释放了多少个节点。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int free_count(Node *r){
    if(!r) return 0;
    int c = free_count(r->left) + free_count(r->right);
    free(r);
    return c + 1;
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("freed=%d\n", free_count(root));
    root = NULL;
    return 0;
}

同时进行搜索和释放

一个完整的生命周期是：构建树、搜索树，然后释放树。完成这三步可以让程序保持正确且没有内存泄漏。

Valgrind 等工具可以确认每次 malloc 都对应一次 free。

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

快速检查

思考如何安全地释放内存。

在交互式课程中回答

回顾

BST 搜索会进行比较，并在每一步进入一个子树，所需时间与树高成正比。最小值是最左侧的节点，最大值是最右侧的节点。

按后序释放树，使子节点先于父节点释放，然后将根设置为 NULL，以避免悬空指针。

免费开始

用 AI 导师学习 C — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 39
课程: 144

免费开始学习查看完整课程

常见问题解答

「搜索与释放」课时是免费的吗？

是的 — 「搜索与释放」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「搜索与释放」这节课中我会学到什么？

查找节点并释放内存。你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「搜索与释放」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy