二叉搜索树（BST）插入异常：单次插入后程序终止问题

以下是我编写的二叉搜索树（BST）操作代码：

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

typedef struct node
{
    int data;
    struct node* rchild;
    struct node* lchild;
}node;

node *root = NULL;
node *ptr;
node *ptr1;
bool flag = false;

void insert(int item)
{
    ptr = root;
    ptr1 = NULL;
    
    while(ptr!=NULL && flag == false)
    {
        if(item < ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->lchild;
        }
        else if(item > ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->rchild;
        }
        else
            if(item == ptr->data)
            {
                flag = true;
                printf("item already exists\n");
                return;
            }
    }
    
    if(ptr==NULL)
    {
        node *newnode = (struct node*)malloc(sizeof(node));
        newnode->data = item;
        newnode->lchild = NULL;
        newnode->rchild = NULL;
        root = newnode;  // Assign the new node to root

        if(item < ptr1->data)
            ptr1->lchild = newnode;
        else  
            ptr1->rchild = newnode;
    }
}

void search(int item)
{
    ptr = root;
    
    while(ptr!=NULL && flag == false)
    {
        if(item < ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->lchild;
        }
        else if(item > ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->rchild;
        }
        else
            if(item == ptr->data)
                flag = true;
    }
    if(flag == true)
        printf("Item found at node %d\n",ptr->data);
    else
        printf("Item does not exists\n");
}

node* succ(node* ptr);


void delete(int item)
{
    //*ptr = root;
    ptr1 = NULL;
    while(ptr!=NULL && flag == false)
    {
        if(item < ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->lchild;
        }
        else if(item > ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->rchild;
        }
        else
            if(item == ptr->data)
                flag = true;
    }
    if(flag == false)
    {
        printf("Item does not exists\n");
        return;
    }
    
    /*Deciding deletion case*/
    int del_case;
    if(ptr->lchild == NULL && ptr->rchild == NULL)
        del_case = 1;
    else
    {
        if(ptr->lchild != NULL && ptr->rchild != NULL)  
            del_case = 2;
        else
            del_case = 3;
    }
    
    if(del_case == 1)  //no child
    {
        if(ptr1->lchild == ptr)
            ptr1->lchild = NULL;
        else
            ptr1->rchild = NULL; 
        free(ptr);    
    }
    if(del_case == 2) //both child
    {
        int item1;
        ptr1=succ(ptr);
        item1 = ptr1->data;
        delete(item1);
        ptr->data = item1;
    }
    
    if(del_case == 3) // one child
    {
        if(ptr1->lchild == ptr)
        {
            if(ptr->lchild == NULL)
                ptr1->lchild = ptr->rchild;
            else
                ptr1->rchild = ptr->lchild;
        }
        else
            if(ptr1->rchild == ptr)
            {
                if(ptr->lchild == NULL)
                    ptr1->lchild = ptr->rchild;
                else
                    ptr1->rchild = ptr->lchild;
            }
            
        free(ptr);    
    }
    
}

node* succ(node* ptr)
{
    ptr1 = ptr->rchild;
    if(ptr1 !=NULL)
        while(ptr1->lchild != NULL)
            ptr1 = ptr1->lchild;
    return ptr1;        
}

int main()
{
    int choice,data;
    printf("1.Insertion\n2.Deletion\n3.Search\n");
    while(1)
    {
        printf("enter ur choice:");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1: printf("enter the no. to be inserted: ");
                    scanf("%d",&data);
                    insert(data); break;
            case 2: printf("enter the no. to be deleted: ");
                    scanf("%d",&data);
                    delete(data); break;   
            case 3: printf("enter the no. to be searched: ");
                    scanf("%d",&data);
             
                    search(data); break; 
            default: printf("invalid choice\n");
                     break;
        }
    }
    return 0;
}

程序在完成单次插入操作后就会终止，尝试插入多个元素均失败，删除和搜索功能均返回“元素不存在”，因程序提前终止，无法验证这两个功能是否正常工作。

1. 插入第一个节点时的空指针访问 #

insert函数中，当插入第一个节点（root初始为NULL）时，ptr1保持为NULL，后续执行if(item < ptr1->data)会直接访问空指针，导致程序崩溃终止。

修复：在插入节点时先判断ptr1是否为NULL（即是否是第一个节点），仅在非空时才执行子节点挂载逻辑：

if(ptr==NULL)
{
    node *newnode = (struct node*)malloc(sizeof(node));
    newnode->data = item;
    newnode->lchild = NULL;
    newnode->rchild = NULL;

    if(ptr1 == NULL) {
        root = newnode; // 第一个节点直接赋值给root
    } else {
        if(item < ptr1->data)
            ptr1->lchild = newnode;
        else  
            ptr1->rchild = newnode;
    }
}

2. 全局变量状态未重置 #

全局变量flag、ptr、ptr1会保留上一次操作的状态，导致后续操作逻辑混乱（比如搜索找到元素后flag设为true，后续插入会误判元素已存在）。

修复：

• 每次调用insert、search、delete时，重置flag为false；
• 将ptr、ptr1改为函数内的局部变量，避免全局状态污染。

3. delete函数未初始化ptr #

delete函数中注释掉了ptr = root;，导致ptr使用全局残留值，无法正确查找待删除元素。

修复：在delete函数开头添加ptr = root;。

4. delete函数单节点删除逻辑错误 #

单节点删除时的子节点挂载逻辑混乱，错误地修改了非目标父节点的子指针。

修复：根据待删除节点是父节点的左/右孩子，直接将对应位置替换为待删除节点的非空子节点：

if(del_case == 3) // one child
{
    if(ptr1->lchild == ptr) {
        ptr1->lchild = (ptr->lchild != NULL) ? ptr->lchild : ptr->rchild;
    } else {
        ptr1->rchild = (ptr->lchild != NULL) ? ptr->lchild : ptr->rchild;
    }
    free(ptr);    
}

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

typedef struct node
{
    int data;
    struct node* rchild;
    struct node* lchild;
}node;

node *root = NULL;

void insert(int item)
{
    node *ptr = root;
    node *ptr1 = NULL;
    bool flag = false;
    
    while(ptr!=NULL && flag == false)
    {
        if(item < ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->lchild;
        }
        else if(item > ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->rchild;
        }
        else
        {
            flag = true;
            printf("item already exists\n");
            return;
        }
    }
    
    if(ptr==NULL)
    {
        node *newnode = (struct node*)malloc(sizeof(node));
        newnode->data = item;
        newnode->lchild = NULL;
        newnode->rchild = NULL;

        if(ptr1 == NULL) {
            root = newnode;
        } else {
            if(item < ptr1->data)
                ptr1->lchild = newnode;
            else  
                ptr1->rchild = newnode;
        }
    }
}

void search(int item)
{
    node *ptr = root;
    bool flag = false;
    
    while(ptr!=NULL && flag == false)
    {
        if(item < ptr->data)
        {
            ptr=ptr->lchild;
        }
        else if(item > ptr->data)
        {
            ptr=ptr->rchild;
        }
        else
        {
            flag = true;
        }
    }
    if(flag == true)
        printf("Item found at node %d\n",ptr->data);
    else
        printf("Item does not exists\n");
}

node* succ(node* ptr);

void delete(int item)
{
    node *ptr = root;
    node *ptr1 = NULL;
    bool flag = false;
    
    while(ptr!=NULL && flag == false)
    {
        if(item < ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->lchild;
        }
        else if(item > ptr->data)
        {
            ptr1 = ptr;
            ptr=ptr->rchild;
        }
        else
        {
            flag = true;
        }
    }
    if(flag == false)
    {
        printf("Item does not exists\n");
        return;
    }
    
    /*Deciding deletion case*/
    int del_case;
    if(ptr->lchild == NULL && ptr->rchild == NULL)
        del_case = 1;
    else if(ptr->lchild != NULL && ptr->rchild != NULL)  
        del_case = 2;
    else
        del_case = 3;
    
    if(del_case == 1)  //no child
    {
        if(ptr1->lchild == ptr)
            ptr1->lchild = NULL;
        else
            ptr1->rchild = NULL; 
        free(ptr);    
    }
    if(del_case == 2) //both child
    {
        node* succ_node = succ(ptr);
        int item1 = succ_node->data;
        delete(item1);
        ptr->data = item1;
    }
    
    if(del_case == 3) // one child
    {
        if(ptr1->lchild == ptr) {
            ptr1->lchild = (ptr->lchild != NULL) ? ptr->lchild : ptr->rchild;
        } else {
            ptr1->rchild = (ptr->lchild != NULL) ? ptr->lchild : ptr->rchild;
        }
        free(ptr);    
    }
    
}

node* succ(node* ptr)
{
    node *ptr1 = ptr->rchild;
    if(ptr1 !=NULL)
        while(ptr1->lchild != NULL)
            ptr1 = ptr1->lchild;
    return ptr1;        
}

int main()
{
    int choice,data;
    printf("1.Insertion\n2.Deletion\n3.Search\n");
    while(1)
    {
        printf("enter ur choice:");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1: printf("enter the no. to be inserted: ");
                    scanf("%d",&data);
                    insert(data); break;
            case 2: printf("enter the no. to be deleted: ");
                    scanf("%d",&data);
                    delete(data); break;   
            case 3: printf("enter the no. to be searched: ");
                    scanf("%d",&data);
                    search(data); break; 
            default: printf("invalid choice\n");
                     break;
        }
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Manika Elizabeth Roy