C / C++ / 系统课时

释放二叉树全部节点

释放二叉树全部节点

动态创建的二叉树如果只释放根节点,会直接失去对子树地址的访问,造成内存泄漏。正确做法是先释放左右子树,再释放当前节点,也就是按后序遍历的顺序销毁整棵树,确保每个地址在失效前都已完成后续访问。

学习目标

  • 理解为什么释放二叉树必须先处理子节点再处理父节点
  • 能用后序遍历实现完整的 freeTree 函数
  • 能识别重复释放、释放后继续访问等常见内存错误

为什么后序遍历适合释放

节点中保存着左右子节点的地址。如果先执行 free(root),当前节点占用的内存立即失效,之后再读取 root->left 或 root->right 都属于未定义行为。

后序遍历的顺序是“左子树 → 右子树 → 当前节点”。这正好满足释放依赖:先把当前节点能够到达的所有后代处理完,最后才销毁保存这些地址的父节点。

二叉树按后序遍历释放节点

实现完整的释放函数

freeTree 的递归出口是空指针。对于非空节点,先递归释放左子树和右子树,最后释放当前节点。下面的完整程序先构造一棵二叉搜索树,打印其中序遍历结果,再释放全部节点。

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

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

Node *createNode(int key) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        fprintf(stderr, "memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node *insert(Node *root, int key) {
    if (root == NULL) {
        return createNode(key);
    }

    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    }

    return root;
}

void inorder(const Node *root) {
    if (root == NULL) {
        return;
    }

    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

void freeTree(Node *root) {
    if (root == NULL) {
        return;
    }

    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main(void) {
    int values[] = {40, 20, 60, 10, 30, 50, 70};
    size_t count = sizeof(values) / sizeof(values[0]);
    Node *root = NULL;

    for (size_t i = 0; i < count; ++i) {
        root = insert(root, values[i]);
    }

    inorder(root);
    printf("\n");

    freeTree(root);
    root = NULL;
    printf("tree released\n");
    return 0;
}

预期输出:

text
10 20 30 40 50 60 70
tree released

程序输出只能说明控制流正常结束,不能单独证明“绝对没有内存泄漏”。真正做内存检查时,应再配合编译器 Sanitizer 或 Valgrind 等工具;本节先把正确的释放顺序和指针生命周期处理好。

释放后为什么常把根指针置空

freeTree(root) 接收到的是根指针值的副本,所以函数内部释放节点后,调用者变量 root 本身仍然保存着原地址。这个地址已经失效,如果继续解引用,就是悬空指针访问。

因此,在整棵树不再使用后,调用者通常继续执行 root = NULL。这不会“再次释放”内存,而是明确表示该变量已经不再指向有效节点,也能降低后续误用的风险。

常见错误与边界

最危险的错误是先释放父节点,再访问它的左右指针;另一个常见错误是同一棵树被重复调用释放函数。前者可能触发崩溃或静默数据破坏,后者会形成重复释放。

释放整棵树需要访问每个节点一次,因此时间复杂度为 O(n)O(n)。递归调用栈的额外空间为 O(h)O(h),其中 hh 是树高。树极度退化且节点很多时,递归深度可能过大;这时可改用显式栈实现迭代后序遍历,但普通规模的教学与业务树结构中,递归版本最直接也最不容易写错。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

释放二叉树全部节点

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通