c - BST C语言如何删除子树？

Question

我想制作 pop 函数来删除节点和节点的子树。这是我的代码

void pop(struct data *node,int num)
{
    if(node)
    {
        if(node->num==num)
        {
            pop(node->left,num);
            pop(node->right,num);
            free(node);
            node=NULL;
        }
        else
        {
            if(num> node->num)
                pop(node->right,num);
            else if (num< node->num)
                pop(node->left,num);
        }
    }
}
void pre(struct data *node)
{
    if(node)
    {
        printf("%d ",node->num);
        pre(node->left);
        pre(node->right);
    }
}
void main()
{
    push(&root,37);
    push(&root,20);
    push(&root,45);
    push(&root,5);
    push(&root,15);
    push(&root,40);
    push(&root,50);
    pre(root);
    pop(root,5);
    pre(root);
    getchar();
}

Pre 函数在我使用 pop 之前运行良好。但是在我使用pop函数之后，它就坏了。谁能知道哪里出错了？

Answer 1

在 pop 中，您正在做:node=NULL; ——但这只会影响传递给函数的指针的副本，而不影响指针在原始树中。您的树保留指向您现在已释放的数据的指针。下次您对这棵树做很多事情时，您会尝试取消对该指针的引用，然后事情就会崩溃并开始繁荣(至少您希望他们这样做——更糟糕的是，有时他们似乎还可以工作)。

解决此问题的一种方法是将双指针传递给 pop:

void pop(struct data **node, int num) { 

    if ((*node)->num == num)
        // ...
        free(*node);
        *node = NULL;
    }
}

现在您正在更改树中的指针，而不是更改您的函数收到的它的副本。

虽然这仍然无法正常工作——您依赖于 pop(child, num); 来销毁当前节点的子树，但除非它们的 num 设置为相同的值，它们不会删除任何内容，只是沿着树向下移动寻找具有匹配 num 的节点。

您可能希望一个函数遍历树以找到您关心的节点，然后另一个函数从指定节点开始遍历树，并(无条件地)销毁该节点及其子树。