我有一个如下所示的动态数据结构:

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

该结构是二叉树的一个节点，此外每个节点还指向其父节点。现在，使用使用 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 的原因)。然后它陷入无限循环，因为它不打印“节点已删除”。

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

最佳答案

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

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

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

    free(node);
}

https://stackoverflow.com/questions/72349696/