c - 当数据变大时在c中搜索二叉树

Question

void *node_search(node_t *root, void *key) {
    node_t** curr = &root;
    int outcome;
    static int comparison = 0;
    while (*curr){
        outcome = strcmp(key, (*curr)->name);
        comparison++;
        printf("%d", outcome);
        if(outcome<0) {
            curr = &(*curr)->left;
        } else {
            if(outcome == 0){
               printf("%s---> ", key);
               printf("%d number of comparisions\n", comparison);   
               comparison=0;
               return (*curr)->movie;
            }
            curr = &(*curr)->right;
        } 

    }

           printf("%s---> ", key);
           printf("%d number of comparisions but NOT FOUND\n", comparison);
           comparison = 0;


    return (*curr);
}

当数据量较小时，它可以完美地找到我需要找到的内容

但是当使用相同的数据集但尺寸更大时，它会打印出未找到

这是为什么？

这是我插入树的内容

node_t *insert_node(node_t *root, node_t *new)
{
    node_t** curr = &root;
    while (*curr)
    {
        if (strcmp(new->name, (*curr)->name) < 0) {
            curr = &(*curr)->left;
        } else {
            curr = &(*curr)->right;
        }
    }

    *curr = new;

    return root;
}

Answer 1

在insert_node中，您应该将root作为node_t **而不是node_t *传递。否则，如果您有一个空树，则不会创建根节点。另外，请务必在 main 中将 root 初始化为 NULL。

由于您将传递根指针的地址，因此 insert_node 不需要返回任何内容。

void insert_node(node_t **root, node_t *new)
{
    node_t** curr = root;
    while (*curr)
    {
        if (strcmp(new->name, (*curr)->name) < 0) {
            curr = &(*curr)->left;
        } else {
            curr = &(*curr)->right;
        }
    }

    *curr = new;
}

int main()
{
    node_t *root = NULL;
    ...
    insert_node(&root, node1);
    insert_node(&root, node2);
    ...
}