c - 将字符串插入二叉搜索树 C

Question

我需要将字符串插入到二叉搜索树中，但每次运行我的插入函数都会更新所有节点，而不仅仅是适当的节点。 它要求放置在二叉搜索树中的每个单词都有为其分配的确切内存量(+1 为 NULL 指针)。

这是正在使用的结构:

typedef struct node_t{
   char *word;
   struct node_t *left, *right;
} node_t;

下面是我传递这个词的方式:

for(i=0; i< original_words -1; i++)
{
    fscanf(ifp, "%s", y);
    head = insert(head, y);
}

这是我的插入函数:

node_t *insert(struct node_t *head, char *word)
{

if(strcmp(head->word, word) > 0)
{

    if(head->left == NULL)
    {
        head->left = create_node(word);
    }
    else
    {
        head->left = insert(head->left, word);
    }
}

else
{
    if(head->right == NULL)
    {
        head->right = create_node(word);
    }
    else
    {
        head->right = insert(head->right, word);
    }
}

return head;

}

编辑:这是输入文件的示例。

4
-------
bravo
-------
alpha
-------
gamma
-------
delta

Answer 1

您的答案(insert 函数)假设 head 已经在第一次调用时定义，它应该以以下行开头:

if (head == null) return create_node(word);

这也将使您无需在代码中使用空行。我不确定这是问题，但确实是一个问题。

也许更重要的是:create_node 是如何设置word 的？如果是这样的:

 new_node->word = word

然后你所做的就是创建一个指向从文件中提取的单词的指针集合。很可能每次从文件中读取一个单词都会将该单词读入同一 block 内存，因此您所做的只是收集一棵指向内存中同一位置的指针树。它应该是这样的:

 new_node->word = malloc(strlen(word)+1);
 if (new_note->word == null) {FAIL MEMORY LOSS}
 strcpy(new_node->word, word);