c - 二叉搜索树的 DeleteElement 会出现运行时错误？

Question

我正在尝试编写一个名为“DeleteElement”的函数来删除二叉搜索树中的一个元素。它可以正确编译，但会出现运行时错误。请帮我调试错误。提前致谢。

C Code:

#include <stdio.h>
#include <malloc.h>


struct BinaryTree
{
         int data;
         struct BinaryTree *left;
         struct BinaryTree *right;
};


int FindMin(struct BinaryTree *root)
{
    if(root == NULL)
    {
        return NULL;
    }
    while(root->left)
    {
        root = root->left;
    }
return root->data;

}


int FindMax(struct BinaryTree *root)
{
    if(root == NULL)
    {
        return NULL;
    }
    while(root->right)
    {
        root = root->right;
    }
return root->data;
}



struct BinaryTree *DeleteElement(struct BinaryTree *root,int element)
{
    struct BinaryTree *temp;
    if(root == NULL)
    {
        printf("Element Not found");
        //return NULL;
    }
    else if(element > root->data)
    {
        root->right = DeleteElement(root->right,element);
    }
    else if(element < root->data)
    {
        root->left = DeleteElement(root->left,element);
    }
    else
    {
        if(root->left && root->right)
        {
            int temp1 = FindMax(root->left);
            root->data = temp1; 
            root->left = DeleteElement(root->left,root->data);
        }
        else 
        {
            temp = root;
            if(root->left == NULL)
            {
                root = root->right;
            }
            if(root->right == NULL)
            {
                root = root->left;
            }
            free(temp);
        }
    }
    return root;
}

int main()
{
    struct BinaryTree * root = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    root-> data = 7;
    struct BinaryTree * l = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    l -> data = 4;
    struct BinaryTree * ll = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    ll -> data = 2;
    ll -> left = ll -> right = NULL;
    struct BinaryTree * lr = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    lr -> data = 5;
    lr -> left = lr -> right = NULL;
    l -> left = ll;
    l -> right = lr;
    struct BinaryTree * r = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    r -> data = 9;
    struct BinaryTree * rl = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    rl -> data = 8;
    rl -> left = rl -> right = NULL;
    struct BinaryTree * rr = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    rr -> data = 11;
    rr -> left = rr -> right = NULL;
    r -> left = rl;
    r -> right = rr;
    root -> left = l;
    root -> right = r;


    printf("Max %d\n",FindMax(root));
    printf("Min %d\n",FindMin(root));
    DeleteElement(root,2);
    printf("Max %d\n",FindMax(root));
    printf("Min %d\n",FindMin(root));
    return 0;
}

Answer 1

问题:

问题出在以下几行:

if(root->left == NULL)
{
  root = root->right;
}
if(root->right == NULL)
{
  root = root->left;
}

第一个条件可能为真，程序将更改 root 的值。但是第二个 if 语句仍将被计算，并且由于 root 可能在前一个语句中已更改为 NULL ，因此可能会出现运行时错误. (尝试访问 NULL 字段从来都不是一件好事)

修复:

你应该将第二个 if 更改为 else if ，如下所示:

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