首页 文章

删除二进制搜索树的功能无法正常工作

提问于
浏览 次
0

这是用C编码的二叉搜索树的删除功能，但这不能正常工作 . 应该删除的节点被垃圾值替换 .

void delete(struct node* root,int data)
{
{
    struct node* t1;
    if(root==0) {
        printf("element not found\n");
    } else if(data>root->data) {
        delete(root->right,data);
    } else if(data<root->data) {
        delete(root->left,data);
    } else {
        if(root->right&&root->left) {
            t1=findmin(root->right);
            root->data=t1->data;
            free(t1);
        } else {
            t1=root;
            if(root->right) {
                root=root->right;
            } else if(root->left) {
                root=root->left;
            }
            free(t1);
        }
    }
}

它本身工作，但节点没有被删除，并被一些垃圾值取代 .

struct node* findmin(struct node* t) {
    if(t==NULL) {
        return NULL;
    } else if(t->left) {
        findmin(t->left);
    } else
        return t; 
}
c binary-search-tree

1 回答

  • 0

    您正在函数参数中传递root，然后在您重新分配代码的下一个块内 .

    else
        {
                t1=root;
                if(root->right)
                {
                        root=root->right;
                }
                else if(root->left)
                {
                        root=root->left;
                }
                free(t1);
        }

    这种重新分配对于当前函数调用是暂时的（因为它已经通过值传递） . 或者你也可以这样做，就是在删除指定节点后返回树的新根 .

    struct node* delete(struct node* root, int key)
{
    if (root == NULL) return root;

    if (key < root->key)
        root->left = delete(root->left, key);

    else if (key > root->key)
        root->right = delete(root->right, key);

    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        struct node* temp = findmin(root->right);

        root->key = temp->key;

        root->right = delete(root->right, temp->key);
    }
    return root;
}
    回复于

相关问题