C语言BST菜单驱动程序删除节点调用free时运行崩溃问题求解

• 删除叶子节点时仅执行free操作，未将父节点对应的左/右子节点指针置为NULL，导致后续访问野指针崩溃；若删除的是唯一根节点，还需要将root指针置空
• 所有判断父节点子节点的分支均错误使用赋值运算符=代替比较运算符==，直接篡改了父节点指针结构，触发内存访问异常
• 删除有两个子节点的节点时，仅替换了值、释放了后继节点，未修改后继节点父节点的对应指针，遗留野指针
• search函数未找到目标节点时缺少return语句，属于未定义行为；且查找根节点时全局变量temp2未初始化，访问时直接崩溃
• 待删除节点为根节点时没有特殊处理逻辑，会访问未初始化的temp2变量

#include <stdio.h>
#include <stdlib.h>

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

int found;
struct btNode *temp2;
struct btNode *create(int);
struct btNode *insert(struct btNode *, int);
void inorder(struct btNode *);
void preorder(struct btNode *);
void postorder(struct btNode *);
// 修改delete函数返回值，支持更新根节点
struct btNode* delete(struct btNode *, int);

int main()
{
    int choice, item;
    struct btNode *root = NULL;

    do
    {
        printf("\nChoose one of the options:\n");
        printf("1. Insert 2. Delete 3. Inorder 4. Postorder 5. Preorder 6. Exit\n");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            printf("\nEnter any number to insert:");
            scanf("%d", &item);
            root = insert(root, item);
            break;

        case 2:
            printf("\nEnter any number to delete:");
            scanf("%d", &item);
            // 接收返回值更新root
            root = delete(root, item);
            break;

        case 3:
            inorder(root);
            break;

        case 4:
            postorder(root);
            break;

        case 5:
            preorder(root);
            break;

        case 6:
            break;

        default:
            printf("\nWRONG INPUT");
        }
    } while (choice != 6);

    return 0;
}

struct btNode *create(int num)
{
    struct btNode *temp1 = (struct btNode *)malloc(sizeof(struct btNode));
    temp1->data = num;
    temp1->left = NULL;
    temp1->right = NULL;
    return temp1;
}

struct btNode *search(struct btNode *root, int num)
{
    struct btNode *temp1 = root;
    // 初始化temp2为NULL，标记待删节点是根节点
    temp2 = NULL;
    while (temp1 != NULL)
    {
        if (temp1->data == num)
        {
            found = 1;
            return temp1;
        }
        else
        {
            temp2 = temp1;
            if (temp1->data >= num)
            {
                temp1 = temp1->left;
            }
            else
            {
                temp1 = temp1->right;
            }
        }
    }
    found = 0;
    return NULL;
}

struct btNode *insert(struct btNode *root, int num)
{
    struct btNode *temp1 = create(num);
    if (root == NULL)
    {
        root = temp1;
        printf("%d inserted\n", root->data);
    }
    else
    {
        temp2 = root;
        while (temp2 != NULL)
        {
            if (temp2->data >= num)
            {
                if (temp2->left)
                {
                    temp2 = temp2->left;
                }
                else
                {
                    temp2->left = temp1;
                    printf("%d inserted\n", temp2->left->data);
                    break;
                }
            }
            else
            {
                if (temp2->right)
                {
                    temp2 = temp2->right;
                }
                else
                {
                    temp2->right = temp1;
                    printf("%d inserted\n", temp2->right->data);
                    break;
                }
            }
        }
    }
    return root;
}

struct btNode* delete(struct btNode *root, int num)
{
    struct btNode *temp1 = search(root, num);
    if (found == 0)
    {
        printf("element not found");
        return root;
    }
    // 处理叶子节点
    if (temp1->left == NULL && temp1->right == NULL)
    {
        // 待删节点是根节点
        if (temp2 == NULL)
        {
            free(temp1);
            return NULL;
        }
        // 修改父节点指针
        if (temp2->left == temp1)
            temp2->left = NULL;
        else
            temp2->right = NULL;
        free(temp1);
    }
    // 只有左孩子
    else if (temp1->left != NULL && temp1->right == NULL)
    {
        if (temp2 == NULL)
        {
            struct btNode *newRoot = temp1->left;
            free(temp1);
            return newRoot;
        }
        if (temp2->left == temp1)
            temp2->left = temp1->left;
        else
            temp2->right = temp1->left;
        free(temp1);
    }
    // 只有右孩子
    else if (temp1->left == NULL && temp1->right != NULL)
    {
        if (temp2 == NULL)
        {
            struct btNode *newRoot = temp1->right;
            free(temp1);
            return newRoot;
        }
        if (temp2->left == temp1)
            temp2->left = temp1->right;
        else
            temp2->right = temp1->right;
        free(temp1);
    }
    // 有两个孩子
    else
    {
        struct btNode *node1 = temp1;
        struct btNode *node2 = temp1->right;
        struct btNode *parentNode2 = temp1;
        // 找右子树最小节点
        while (node2->left != NULL)
        {
            parentNode2 = node2;
            node2 = node2->left;
        }
        temp1->data = node2->data;
        // 修改后继节点父节点的指针
        if (parentNode2->left == node2)
            parentNode2->left = node2->right;
        else
            parentNode2->right = node2->right;
        free(node2);
    }
    return root;
}

void inorder(struct btNode *r)
{
    if (r == NULL)
    {
        printf("Tree is empty");
        return;
    }
    if (r->left)
        inorder(r->left);
    printf("%d ", r->data);
    if (r->right)
        inorder(r->right);
}

void preorder(struct btNode *r)
{
    if (r == NULL)
    {
        printf("Tree is empty");
        return;
    }
    printf("%d ", r->data);
    if (r->left)
        preorder(r->left);
    if (r->right)
        preorder(r->right);
}

void postorder(struct btNode *r)
{
    if (r == NULL)
    {
        printf("Tree is empty");
        return;
    }
    if (r->left)
        postorder(r->left);
    if (r->right)
        postorder(r->right);
    printf("%d ", r->data);
}

内容的提问来源于stack exchange，提问作者SuperRv002