c - 二叉搜索树的删除功能无法正常工作

Question

这是用 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; 
}

Answer 1

您在函数参数中传递 root，然后在代码的以下 block 中重新分配它。

            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;
}