使用字符串创建二叉搜索树

Question

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

struct node{
    char *name;
    struct node *lchild;
    struct node *rchild;
}*root;


void find(char *str,struct node **par,struct node **loc)
{
    struct node *ptr,*ptrsave;
    if(root==NULL)
    {
        *loc=NULL;
        *par=NULL;
        return;
    }
    if(!(strcmp(str,root->name)))
    {
        *loc=root;
        *par=NULL;
        return;
    }
    if(strcmp(str,root->name)<0)
        ptr=root->lchild;
    else
        ptr=root->rchild;
    ptrsave=root;
    while(ptr!=NULL)
    {
        if(!(strcmp(str,ptr->name)))
        {
            *loc=ptr;
            *par=ptrsave;
            return;
        }
        ptrsave=ptr;
        if(strcmp(str,ptr->name)<0)
            ptr=ptr->lchild;
        else
            ptr=ptr->rchild;
    }
    *loc=NULL;
    *par=ptrsave;
}


void insert(char *str)
{
    struct node *parent,*location,*temp;
    find(str,&parent,&location);
    if(location!=NULL)
    {
        printf("Name already present\n");
        return;
    }
    temp=(struct node*)malloc(sizeof(struct node));
    temp->name=str;
    temp->lchild=NULL;
    temp->rchild=NULL;
    if(parent==NULL)
        root=temp;
    else
        if(strcmp(str,parent->name)<0)
            parent->lchild=temp;
        else
            parent->rchild=temp;
}


void displayin(struct node *ptr)
{
    if(root==NULL)
    {
        printf("Tree is empty");
        return;
    }
    if(ptr!=NULL)
    {
        displayin(ptr->lchild);
        printf("%s -> ",ptr->name);
        displayin(ptr->rchild);
    }
}


int main()
{
    root=NULL;
    char str[20];
    while(1)
    {
        printf("Enter name: ");
        fflush(stdin);
        gets(str);
        insert(str);
        printf("Wants to insert more item: ");
        if(getchar()=='y')
        insert(str);
        else
        break;
    }
    displayin(root);
    getch();
    getchar();
    return 0;
 }

如果我使用以下输入运行这段代码

拉克什 拉杰什 双向

然后，它将输出显示为“bimal->”，这是错误的。我不知道逻辑哪里出了问题。我交叉检查但找不到错误。有人可以看看这个吗？

Answer 1

问题之一:

在您正在执行的insert() 函数中

temp=(struct node*)malloc(sizeof(struct node));
temp->name=str; //this is not correct, 

//do 
temp=malloc(sizeof(struct node)); // no type cast for malloc
temp->name = strdup(str);         //allocate memory too
//also check you NULL and free the allocated memory.

您只是在为要存储的字符串创建的节点中设置指针位置，但它指向 main() 中的 str 数组。因此所有节点都将指向同一位置，该位置将输入最后一个值。在您的情况下，它是 "bimal"。