二叉搜索树 - 插入问题

Question

*这是我写的代码 *

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

*我面临的问题是，程序在一次插入后终止。应该是root的问题，但是不知道怎么解决 *.

我尝试插入多个元素，但程序在一次插入后终止。我不知道如何在代码中声明和初始化根变量。删除和搜索功能返回项目不存在，但由于程序在单次插入后终止，我不知道删除和搜索功能是否正常工作。

Answer 1

如果树中没有项目，则

ptr1 为 NULL。这是一个简单的修复：

void insert(int item) {
    ptr = root;
    ptr1 = NULL;
    while (ptr != NULL) {
         ptr1 = ptr;
         if (item < ptr->data)
             ptr = ptr->lchild;
         else if(item > ptr->data)
             ptr = ptr->rchild;
         else
             return;
    }
    node *newnode = (struct node*)malloc(sizeof(node));
    newnode->data = item;
    newnode->lchild = newnode->rchild = NULL;
    if (ptr1 == NULL) {
        // or you can check root == NULL
        root = newnode;
        return;
    }
    if(item < ptr1->data)
        ptr1->lchild = newnode;
    else
        ptr1->rchild = newnode;
}

顺便说一句，您的删除功能无法正常工作。如果您删除最后一项，则必须设置 root = NULL，否则下一个操作将会崩溃。