c - 使用新方法删除二叉树

Question

实际上我在实现删除树时被卡住了。我使用 free() 删除了叶节点，现在父节点将成为叶节点，并使用递归删除这些节点。但问题是叶节点实际上并没有被删除，它仍然存在。而且我在删除树时遵循的方法如下

void deleteTree(struct node *root)
{
    if(root->left == NULL && root->right == NULL)
    {
       free(root);
    }
    else
    {
       if(root->left != NULL)
            deleteTree(root->left);
       if(root->right != NULL)
            deleteTree(root->right);
    }
}

该方法只删除了叶子节点，并没有删除相应的父节点。在 XCode 中调试后，我发现叶子节点没有被删除，它们仍然存在。

那么，为什么会发生这种情况？

Answer 1

void deleteTree(struct node *root)
{
   if (root) {
    deleteTree(root->left);
    deleteTree(root->right);
    free(root);
   }
}

Answer 2

您deleteTree()不适合删除树中的节点。您正在做的是递归地在二叉树中进行前序遍历。当函数返回时，您从树中删除/释放的节点将再次被引用，因此您正在访问一个空闲节点，这将在运行时导致未定义的行为。

不要访问释放的内存：

根据 C 标准，使用指向由调用 free() 或 realloc() 函数释放的空间的指针值的程序的行为是未定义的。

您应该选择Post-order以释放树的节点。因为在后序遍历中，您不会访问已处理（删除/释放）的节点。你的deleteTree()功能应该是这样的：

void deleteTree(struct node *root){
    if(root == NULL) return;
    deleteTree(root->left);
    deleteTree(root->right);
    free(root);  // node processed and return
}

Answer 3

由于您没有释放任何级别的父节点，因此除了叶子之外的所有级别都保留。您需要做的是free(root)在 if 语句之后，在 else 语句的末尾添加。