C语言复用图节点时释放动态内存出现段错误的问题排查

我希望构建一个通过合并两个子节点生成新父节点的图，具体操作如下：先将节点a与节点b合并为父节点c，再将节点a与节点c合并为父节点d，结构示意图如下：

a   b
    |---|
      |
  a   c
  |---|
    |
    d

但当我从节点d开始释放整个图时出现了段错误，而当不复用同一个节点时该功能可以正常运行。我需要支持节点复用，请问我忽略了什么？以下是对应的C语言代码：

#include <stdlib.h>

struct Node {
    int data;
    struct Node *child1;
    struct Node *child2;
};

struct Node *NewNode(double data) {
    struct Node *node = NULL;
    node = malloc(sizeof(*node));

    if (node == NULL) {
        return node;
    }

    node->data = data;
    node->child1 = NULL;
    node->child2 = NULL;

    return node;
}

struct Node* merge(struct Node *self, struct Node *other) {
    struct Node *node = NewNode(-1);
    node->child1 = self;
    node->child2 = other;
    return node;
}

void free_graph(struct Node **node) {
    if (*node != NULL) {
        free_graph(&(*node)->child1);
        free_graph(&(*node)->child2);
        free(*node);
        *node = NULL;
    }
}

int main(void){
    struct Node *a = NewNode(1);
    struct Node *b = NewNode(2);
    struct Node *c = merge(a, b);
    struct Node *d = merge(a, c);
    free_graph(&d);
}

• 核心问题：重复释放同一内存块
  你的图里节点a被c和d同时引用，节点c又被d引用。当前的free_graph函数会递归释放所有子节点，流程是：

  1. 释放d时，先释放它的子节点a和c
  2. 释放c时，又会再次释放它的子节点a和b
  3. 这时a已经被释放过一次，再次调用free就会触发段错误——这属于重复释放内存的未定义行为。

• 解决方案：引入引用计数机制
  要支持节点复用，必须跟踪每个节点被引用的次数，只有当引用计数降到0时才真正释放内存：

  1. 修改Node结构体，增加引用计数字段：

     struct Node {
         int data;
         struct Node *child1;
         struct Node *child2;
         int ref_count; // 新增引用计数字段
     };
     

  2. 修改NewNode函数，初始化引用计数为1：

     struct Node *NewNode(double data) {
         struct Node *node = malloc(sizeof(*node));
         if (node == NULL) {
             return node;
         }
         node->data = data;
         node->child1 = NULL;
         node->child2 = NULL;
         node->ref_count = 1; // 新节点默认被引用1次
         return node;
     }
     

  3. 新增node_retain函数，用于增加节点的引用计数（当节点被新父节点引用时调用）：

     void node_retain(struct Node *node) {
         if (node != NULL) {
             node->ref_count++;
         }
     }
     

  4. 修改merge函数，引用子节点时增加它们的引用计数：

     struct Node* merge(struct Node *self, struct Node *other) {
         struct Node *node = NewNode(-1);
         node->child1 = self;
         node_retain(self); // 引用self，计数+1
         node->child2 = other;
         node_retain(other); // 引用other，计数+1
         return node;
     }
     

  5. 把free_graph改成node_release，只有引用计数为0时才释放节点：

     void node_release(struct Node **node) {
         if (*node == NULL) {
             return;
         }
         // 先减少引用计数
         (*node)->ref_count--;
         // 计数为0时才递归释放子节点并释放自身
         if ((*node)->ref_count == 0) {
             node_release(&(*node)->child1);
             node_release(&(*node)->child2);
             free(*node);
             *node = NULL;
         }
     }
     

  6. 修改main函数的释放逻辑：

     int main(void){
         struct Node *a = NewNode(1);
         struct Node *b = NewNode(2);
         struct Node *c = merge(a, b);
         struct Node *d = merge(a, c);
         node_release(&d);
         // 此时a、b、c、d的引用计数都已降为0，无需额外释放
     }
     

• 额外注意

  • 每次引用节点时必须调用node_retain，每次不再引用时调用node_release
  • 如果手动持有节点指针（比如main里的a、b），不再使用时也要调用node_release，避免内存泄漏
  • 引用计数能有效解决节点被多个父节点复用的场景，彻底避免重复释放问题

内容的提问来源于stack exchange，提问作者Gilfoyle