c - 我的 bst 插入继续覆盖最近在 C 中添加的值

Question

在我看来，我可能忽略了代码中的某些内容，但请帮助我查看它。每当我调用此函数来插入新节点时，它都会继续覆盖最近的节点。

node_t *node_insert(node_t *cur, char name[]){
    int diff = -1;
    if(cur == NULL) {                 
        node_t *new_node = (node_t*)malloc(sizeof(node_t)); 
        strcpy(new_node->name, name);          // copy data
        new_node->right = new_node->left = NULL;                    
        return new_node;                          `
    } else {
       diff = strcmp(name, cur->name); 
       if(diff<0){
          return node_insert(cur->left,name );}
       else if(diff>0){
         return node_insert (cur->right,name );}
       else if (diff ==0) {               
           return NULL;
        }
    }
}

然后在下面调用上面的函数:

int bst_insert(bst_t *tree, char name[]){
    node_t *result = node_insert(tree->root, name); // update node
    if(result == NULL) {            // duplicate found, ignore
        return 0;                   // 0 indicates not modified
    } else {       
        tree->root = result;       
        tree->size++;               // size now larger
        return 1;                   // 1 indicates modifed
    }
}

Answer 1

就像我在评论中所说，tree->root = result; 仅当 tree->root 为 NULL 时才是正确的，即表示树为空时。之后，您不断用新节点更新根节点，从而忘记了旧树。

您的node_insert函数创建了一个新的node_t对象，没关系。然后你就做递归，你找到必须插入新节点的位置，但你只是返回新节点而不添加。信息去向添加新节点丢失。

您只需稍微修改一下 node_insert:

int node_insert(node_t **cur, char name[]) {
    int diff = -1;
    if(*cur == NULL) {                 
        node_t *new_node = calloc(1, sizeof *new_node);
        if(new_node == NULL)
            return 0;

        strcpy(new_node->name, name);
        *cur = new_node;
        return 1;
    } else {
       diff = strcmp(name, (*cur)->name); 
       if(diff<0){
          return node_insert2(&((*cur)->left),name);}
       else if(diff>0){
         return node_insert2(&((*cur)->right),name);}
       else if (diff ==0) {               
           return 0;
        }
    }
}

现在您必须将双指针传递给 node_t 对象。如果*cur为NULL，然后创建一个新的 node_t 对象并将其分配给 *cur，从而更改原始指针指向的位置(到新创建的对象)。

在递归中，只需将指针传递给left指针和right指针即可。如果递归找到右节点和left(或right，具体取决于diff)，然后传递一个指向下一个递归的指针，其中 *cur将为 NULL 并且新节点将被附加到。

请记住，创建新 bst_t 树的方式很重要，tree->root 必须用NULL初始化，否则node_insert函数在执行递归时将因未定义的行为而失败。

注意我如何创建一个新节点。我使用 calloc 因为它初始化了新的内存为 0，因此 new_node->left 和 new_node->right 将指向 NULL。不过，我不喜欢您创建新节点的一件事:

strcpy(new_node->name, name);

由于我们还没有看到您如何声明结构，因此很难知道是否这是正确的。如果 node_t->name 是 char*，那么您需要分配内存，然后执行 strcpy:

new_node->name = calloc(strlen(name) + 1, 1);
if(new_node->name == NULL)
{
    free(new_node);
    return 0;
}

strcpy(new_node->name, name);

或者如果您的系统有strdup

new_node->name = strdup(name);
if(new_node->name == NULL)
{
    free(new_node);
    return 0;
}

但是如果node_t->name是char[SOME_LENGTH]，则strcpy不正确选择，因为您不能保证 name 中的字符串短于SOME_LENGTH - 1。在这种情况下，您必须使用 strncpy 并确保你最终得到一个有效的字符串:

strncpy(new_node->name, name, sizeof new_node->name);
new_node->name[sizeof(new_node->name) - 1] = 0;

当然，您不必忘记释放已分配的内存。

现在您可以将 bst_insert 更新为:

int bst_insert(bst_t *tree, char name[]){

    int ret = node_insert(tree->root, name);

    if(ret)
        tree->size++;

    return ret;
}