Найти узел в бинарном дереве поиска

Question

Мой findNode вызывается в моей функции вставки с адресом дерева. Поскольку я вставляю первое дерево слов, оно должно быть NULL, но когда я отлаживаюсь, он пропускает эту проверку в моей функции FindWords.

Я не совсем уверен, каково значение дерева здесь, если оно не NULL, пожалуйста, сообщите.

struct TREENODE {
    struct TREENODE *parent; // point to parent node of this node
    struct TREENODE *left; // point to left child of this node
    struct TREENODE *right; // point to right child of this node

    char *word; // store a unique word in the text file
    int count; // num of times this word appears in the file
};

typedef struct TREENODE NODE;
#define MAXWORDLEN  1000

когда я вставляю первое слово, дерево должно быть здесь пустым, потому что нет слов. Но вместо этой функции, возвращающей NULL, когда нет слов, она пропускает оператор if (strcmp (word, tree-> word == 0)) и вызывает ошибку сегментации.

NODE* findNode(char *word, NODE* tree) {
  // return node storing word if exists
    if (tree == NULL){return NULL;}

    if (strcmp(word, tree->word)==0)
      return tree;
    if (strcmp(word, tree->word) <0)
          return findNode(word, tree->left);
    return findNode(word, tree->right);
 }


 void insertNode(char *word, NODE** address_of_tree ) {


    NODE *tree = *address_of_tree;
    NODE *node;
     node = findNode(word, tree); 
    if (node == NULL) {

    NODE *new_node = malloc(sizeof(NODE));
    new_node->word = word;
    new_node->parent = *address_of_tree;
    new_node->left = NULL;
    new_node->right = NULL;

    if (tree == NULL) {
        *address_of_tree = new_node;
        return;
    }
    if (strcmp(word, tree->word) < 0) {
        // word must be added to left subtree
        if (tree->left !=NULL) insertNode(word, &tree->left);
        else {
            new_node->parent = tree;
            tree->left = new_node;
        }
    }
    else {
        if (tree->right != NULL) insertNode(word, &(tree->right));
        else {
            new_node->parent = tree;
            tree->right = new_node;
        }
      }
    }
     else {
        // update the count for the word
        node->count += 1;
    }

 }

void printTree(NODE* tree) {
    // print each word and its count in alphabetical order
    if (tree == NULL) return;
     printTree(tree->left);
     printf("word: %s\ncount: %d", tree->word, tree->count);
     printTree(tree->right);
}


int main() {
      // read text from stdin
      // each time we read a word
     // insert this word into the tree

     NODE *tree; // the tree we are using to store the words

     char word[MAXWORDLEN];
      while(scanf("%s", word) != EOF) {
        // insert this word into the tree
        insertNode(word, &tree);
     }

    printTree(tree);

    return 0;
 }

Answer 1

Вы берете ввод в буфер word и передаете его insertNode(). В insertNode() вы делаете

new_node->word = word;

, что заставит весь новый узел new_node->word указатель указывать на один и тот же буфер word. Любые изменения в содержимом буфера word будут отражаться во всех узлах nodes->word. Вместо этого вы должны

new_node->word = strdup(word);

strdup() продублировать данную строку. Он использует malloc для получения памяти для новой строки. Обязательно освободите его, как только закончите.

Вы также должны инициализировать tree с NULL перед созданием дерева

NODE *tree = NULL;

, поскольку вы передаете указатель tree на insertNode() и в insertNode() вы проверяете, указатель tree равен NULL или нет. Таким образом, вы должны явно инициализировать указатель tree с NULL.