c - 在二叉搜索树中插入一个元素会停止工作

Question

当我调用 insert(element) 函数并添加元素时，它会出现错误，因为程序已停止工作。当我在根左侧添加第三个元素或在根右侧添加一个元素时，它会出错。

请帮忙解决。

 void insert(int iElement){
        if(sRoot==NULL){         //Initially sRoot is NULL
            sRoot=(struct Node*)malloc(sizeof(struct Node));
            sRoot->iData=iElement;
            sRoot->sLeft=NULL;
            sRoot->sRight=NULL;
        }
        else{
            struct Node *current=(struct Node*)malloc(sizeof(struct Node));
            current->iData=iElement;
            current->sLeft=NULL;
            current->sRight=NULL;
            struct Node *parent;
            struct Node *temp;
            parent=sRoot;
            while(parent!=NULL){
                temp=parent;
                if(iElement>parent->iData){
                    parent=parent->sRight;
                }
                if(iElement<parent->iData){
                    parent=parent->sLeft;
                }
            }
            if(iElement<temp->iData)
                temp->sLeft=current;
            else
                temp->sRight=current;
        }
    }

Answer 1

该函数有两个bug，第一个是循环中使用了两个if语句，而不是if-else if语句。

    while(parent!=NULL){
        temp=parent;
        if(iElement>parent->iData){
            parent=parent->sRight;
        }
        if(iElement<parent->iData){
            parent=parent->sLeft;
        }
    }

因此，如果执行第一个 if 语句，则可以将 parent 设置为 NULL。然而，在第二条语句中，您尝试访问此类 NULL 指针的数据成员 iData。

所以至少必须有

    while(parent!=NULL){
        temp=parent;
        if(iElement>parent->iData){
            parent=parent->sRight;
        }
        else if(iElement<parent->iData){
            parent=parent->sLeft;
        }
    }

此循环的第二个问题是，如果使用的将提供重复值，则此循环将是无限的，因为指针 parent 未更改。

此外，还会出现内存泄漏，因为已经为指针 current 分配了内存，但在出现重复值的情况下，不应附加任何一个节点。

因此，您需要处理用户提供重复值的情况。

该功能可以按照演示程序中所示的方式实现。

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

struct Node
{
    int iData;
    struct Node *sLeft;
    struct Node *sRight;
};

struct Node *sRoot = NULL;

int insert( int iElement )
{
    int success = 1;
    struct Node **current = &sRoot;

    while ( success && *current != NULL )
    {
        if ( iElement < ( *current )->iData )
        {
            current = &( *current )->sLeft;
        }
        else if ( ( *current )->iData < iElement )
        {
            current = &( *current )->sRight;
        }
        else
        {
            success = 0;
        }
    }

    if ( success )
    {
        *current = malloc( sizeof( struct Node ) );
        success = *current != NULL;

        if ( success )
        {
            ( *current )->iData = iElement;
            ( *current )->sLeft = NULL;
            ( *current )->sRight = NULL;
        }
    }

    return success;
}

int main(void) 
{

    insert( 10 );
    insert( 9 );
    insert( 11 );
    insert( 12 );
    insert( 8 );
    insert( 7 );

    return 0;
}

请考虑到，当函数依赖于全局变量时，这是一个坏主意。

所以最好像多一个参数一样声明它

int insert( struct Node **sRoot, int iElement );