How to correctly deallocate structure from memory-CodePudding

I have a dynamic data structure which looks like this:

struct tree_node {
    int y;
    int x;
    struct tree_node *left;
    struct tree_node *right;
    struct tree_node *parent;
};

The structure is a node of a binary tree, with the addition that each node also points to its parent. Now, using the classical method of adding nodes to the binary tree using malloc() I can populate the binary tree easily. However, I am having trouble deallocating the binary tree from memory.

Usually, to remove nodes from the binary tree you perform a post-order traversal and then free each node like this:

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    printf("Deleting node with values [%d][%d]\n", node->y , node-> x);

    free(node -> left);
    free(node -> right);
    free(node -> parent);
    free(node);
    printf("\nNode deleted");
}

However, when I run the above function it does not deallocate the binary tree from memory. When I run the function, it deallocates one leaf and then when it tries to delete the next node it gets stuck in an endless loop and my computer either crashes or the program exits with a non-descriptive error.

The output in the terminal is the following:

Deleting node with values [11][4]
Node deleted
Deleting node with values [7739840][0]

So the terminal shows that it deletes the first leaf, and then it tries to fetch the values from the next node but it cannot (which is why it displays 7739840). Then it gets stuck in an endless loop since it does not print "Node deleted".

How can I correctly deallocate the memory? Does it have to do with the way my node is built?

CodePudding user response：

You're deallocating nodes multiple times.

When you delete a given node, after deleteTree(node->left) is called the left node has already been freed, so it doesn't need to be freed again. So remove free(node->left).

The current node has also been freed because free(node->parent) was called in that function, so any further reads of node access freed memory. So remove free(node->parent).

And similarly to the call to deleteTree(node->left), calling deleteTree(node->right) already frees the right node, so remove the call to free(node->right).

So now you're left with:

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    printf("Deleting node with values [%d][%d]\n", node->y , node-> x);

    free(node);
    printf("\nNode deleted");
}

In short, each node is responsible for cleaning itself up.

CodePudding user response：

The correct way of deallocating all the nodes from your tree structure looks like this:

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    free(node);
}