Ошибка сбоя сегментации в BST

Question

Я продолжаю получать ошибку ошибки сегментации, когда я вызываю функцию find_word в своей основной. Когда добавлено слово Я хочу вернуть 1, и когда он найдет это слово, я хочу, чтобы оно вернулось 1. Так что я также не уверен, что мой метод вставки тоже правильный.

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

struct node { 
    char *word; 
    struct node *left; 
    struct node *right; 
}; 
static struct node *root; 


int init(void) 
{ 
    struct node *new_node = malloc (sizeof(struct node)); 
    if(new_node==NULL){ 
     return 0; 
    } 

    else{ 
     root = new_node; 
     new_node->left = NULL; 
     new_node->right = NULL; 
     return 1; 
    } 
} 

static int insert(struct node *newnode, char *word) 
{ 
    struct node *temp = NULL; 
    if(!(newnode)) 
     { 
      temp = (struct node *)malloc(sizeof(struct node)); 
      temp->left =NULL; 
      temp->right = NULL; 
      temp->word = word; 
      newnode = temp; 
      return 0; 
     } 

    if(word < (newnode)->word) 
     { 
      insert((newnode)->left, word); 
     } 
    else if(word > (newnode)->word) 
     { 
      insert((newnode)->right, word); 
     } 
    return 1; 
} 

int add_word(char *word) 
{ 
    return insert(root,word); 

} 
static int find(char *word, struct node *newnode){ 
    if(newnode==NULL){ 
     return 0; 
    } 
    else if(strcmp(word,newnode->word)>0){ 
     find(word,newnode->left); 
    } 

    else if(strcmp(newnode->word,word)<0){ 
     find(word,newnode->right); 
    } 
    else{ 

     return 1; 

    } 
    return 0; 
} 


int find_word(char *word) 
{ 
    return find(word,root); 
} 




int main(int argc,char *argv[]) 
{ 
    int k; 
    char l[5]; 


    k = init(); 
    printf("init: %d\n",k); 

    strcpy(l,"x"); 
    k = add_word(l); 
    printf("add_word(%s): %d\n",l,k); 

    strcpy(l,"x"); 
    k = find_word(l); 
    printf("find_word(%s): %d\n",l,k); 



    return 0; 
} 

Answer 1

исправить, как это

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

struct node { 
    char *word; 
    struct node *left; 
    struct node *right; 
}; 

static struct node *root = NULL; 

static int insert(struct node **newnode, char *word){ 
    struct node *temp = NULL; 
    int cmp; 

    if(!*newnode){ 
     temp = (struct node *)malloc(sizeof(struct node)); 
     temp->left =NULL; 
     temp->right = NULL; 
     temp->word = strdup(word); 
     *newnode = temp; 
     return 0; 
    } 

    if((cmp=strcmp(word, (*newnode)->word)) < 0) 
     return insert(&(*newnode)->left, word); 
    if(cmp > 0) 
     return insert(&(*newnode)->right, word); 
    return 1; 
} 

int add_word(char *word){ 
    return insert(&root, word); 
} 

static int find(char *word, struct node *newnode){ 
    int cmp; 
    if(newnode==NULL) 
     return 0; 
    if((cmp=strcmp(word, newnode->word)) == 0) 
     return 1; 
    if(cmp < 0) 
     return find(word, newnode->left); 
    return find(word, newnode->right); 
} 

int find_word(char *word){ 
    return find(word, root); 
} 

int main(int argc,char *argv[]){ 
    int k; 
    char *w; 

    k = add_word(w="x"); 
    printf("add_word(%s): %d\n", w, k); 

    k = find_word(w); 
    printf("find_word(%s): %d\n", w, k); 

    return 0; 
} 

Answer 2

Если newnode->word является NULL, вы должны вставить слово в текущем узле, для обработки пустого корневого узла.

static int insert(struct node *newnode, char *word) 
{ 
    struct node *temp = NULL; 
    if(!(newnode)) 
     { 
      temp = (struct node *)malloc(sizeof(struct node)); 
      temp->left =NULL; 
      temp->right = NULL; 
      temp->word = malloc(strlen(word)+1); 
      strcpy(temp->word, word); 
      newnode = temp; 
      return 0; 
     } 

    if (newnode->word == NULL) { 
     newnode->word = malloc(strlen(word)+1); 
     strcpy(newnode->word, word); 
     return 1; 
    } 

    if(strcmp(word,(newnode)->word) < 0) 
     { 
      insert((newnode)->left, word); 
     } 
    else if(strcmp(word,(newnode)->word) > 0) 
     { 
      insert((newnode)->right, word); 
     } 
    return 1; 
} 

В вашей find функции, вы звоните strcmp дважды. Вы меняете порядок аргументов, но также меняете > 0 на < 0. Они отменяют друг друга, поэтому оба тестируют одно и то же. Вам нужно изменить тот или иной, но не тот и другой. Вы также должны проверить наличие newnode->word == NULL.

static int find(char *word, struct node *newnode){ 
    if(newnode==NULL || newnode->word == NULL){ 
     return 0; 
    } 
    else if(strcmp(word,newnode->word)>0){ 
     find(word,newnode->left); 
    } 

    else if(strcmp(word,newnode->word)<0){ 
     find(word,newnode->right); 
    } 
    else{ 

     return 1; 

    } 
    return 0; 
}