在二进制搜索树中找到一个节点。

Question

我的findNode是在我的insert函数中被调用的，其中有树的地址，由于我插入的第一个词tree应该是NULL，但是当我调试时，它跳过了FindWords函数中的这个检查。因为我插入的第一个词tree应该是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，因为没有单词存在。但是当没有单词存在时，这个函数没有返回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.