Freeing dynamically allocated graph nodes in C-CodePudding

I want to build a graph that creates a new parent node by merging two child nodes. The code below is supposed to merge node a and b into a parent node c. Then, nodes a and c to create a parent node d:

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

When I try to free the graph starting at node d I get a segmentation fault and I don't know why. Somehow it works if I don't use the same node twice in the graph. However, I want to be able to use the same node more than once. Can someone please tell me what am I missing here?

#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);

}

CodePudding user response：

You put a into the intended tree twice, so free_graph attempts to free it twice. Calling free twice on the same address from the same original allocation is improper.

If you want to have a true tree, do not put any node into it twice. If you want to have a data structure that can have the same node in it twice, either use separate copies of the node (e.g., two different allocations for struct Node with the same value for data) or make provisions in the data structure to avoid freeing it twice (for example, add a reference count to struct node to count how many times it is currently in the tree, and free the node only when its reference count reaches zero).

CodePudding user response：

It does not work because your "tree" does not match your illustration, and is in fact technically not a tree. What you have looks like this:

You need to make a copy instead of reusing a node if you want a tree.

In order to free everything in a graph like this, I'd suggest having a separate linked list to keep track of everything you need to free.