时间戳

首页 > 解决方案 > 对结构指针的 N​​ULL 分配无法通过函数进行。该怎么办？

c - 对结构指针的 N​​ULL 分配无法通过函数进行。该怎么办？

问题描述

我正在尝试实施 BST 删除。根据算法，我们可以直接删除一片叶子。现在我直接将 NULL 分配给叶子，但这个节点仍然保持原样。

在我给出的测试用例中，我试图删除叶子，但它不起作用。

请帮忙！

struct node * delet(long data, struct node* root)
{
    int i=1;
    struct node *temp = root,*t;

    while(temp != 0)
    {
        if(data < temp->data)
        {
            i=2*i;
            temp = temp->l;
        }
        else if(data > temp->data)
        {
            i = (2*i)+1;
            temp = temp->r ;
        }
        else
        {
            printf("%d\n",i);
            break;
        }
    }
    if(temp->l == 0 && temp->r == 0)
    {
        temp = 0;
        return root;
    }
    else if(temp->l == 0)
    {
        temp->data = temp->l->data;
        temp->l = 0;
    }
    else if(temp->r == 0)
    {
        temp->data = temp->r->data;
        temp->r = 0;
    }
    else
    {
        t = temp;
        t = t->r;
        while(t->l != 0)
        {
            t = t->l;
        }
        temp->data = t->data;
        if(t->r != 0)
        {
            t->data = t->r->data;
            t->r = 0;
            return root;
        }
        else
        {
            t = 0;
            return root;
        }
    }
}

标签： cpointers

解决方案

temp = 0;不会从树中删除叶子，只是将局部变量归零。您想要使某些节点为空，l或者r为了从树中删除一个节点。尝试保留父级，一旦 temp 指向叶子，就取消 temp 的父级r或l.

以后也一样t = 0;。

请注意大卫关于首先释放此内存的评论..

例如（假设不删除根）：

...
        if(data < temp->data)
        {
            i=2*i;
            parent = temp;
            temp = temp->l;
        }
        else if(data > temp->data)
        {
            i = (2*i)+1;
            parent = temp;
            temp = temp->r ;
        }
        else
        {
            printf("%d\n",i);
            break;
        }
...
    if(temp->l == 0 && temp->r == 0)
    {
        if (parent->l == temp)
             parent->l = 0;
        else
             parent->r = 0;
        // Free temp if needed
        return root;
    }
...

另请注意，您有：

    else if(temp->l == 0)
    {
        temp->data = temp->l->data;

这是对空指针（temp->l为 NULL）的取消引用，对于temp->r == 0大小写也是如此。

然后你有

         temp->l = 0;

但你已经temp->l == 0在案子里了，所以我认为这不是你的意思。

推荐阅读