如何正确地从内存中释放结构

Question

我有一个动态数据结构，如下所示：

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

该结构是二叉树的一个节点，此外每个节点还指向其父节点。现在，使用 I 向二叉树添加节点的经典方法malloc()可以轻松填充二叉树。但是，我在从内存中释放二叉树时遇到问题。

通常，要从二叉树中删除节点，您需要执行后序遍历，然后释放每个节点，如下所示：

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");
}

但是，当我运行上述函数时，它不会从内存中释放二叉树。当我运行该函数时，它会释放一个叶子，然后当它尝试删除下一个节点时，它会陷入无限循环，我的计算机要么崩溃，要么程序因非描述性错误退出。

终端中的输出如下：

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

因此，终端显示它删除了第一个叶子节点，然后尝试从下一个节点获取值，但无法获取（这就是它显示 7739840 的原因）。然后它陷入无限循环，因为它不打印“节点已删除”。

如何正确释放内存？这与我的节点构建方式有关吗？

Answer 1

从树结构中释放所有节点的正确方法如下所示：

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

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

    free(node);
}

Answer 2

您多次释放节点。

当您删除给定节点时，deleteTree(node->left)调用 after ，左侧节点已经被释放，因此不需要再次释放。所以删除free(node->left).

当前节点也已被释放，因为free(node->parent)在该函数中被调用，因此任何进一步的node访问读取都会释放内存。所以删除free(node->parent).

与对 的调用类似deleteTree(node->left)，调用deleteTree(node->right)已经释放了正确的节点，因此删除对 的调用free(node->right)。

所以现在你只剩下：

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");
}

简而言之，每个节点都有责任清理自己。