c - 二叉搜索树中的搜索函数导致段错误

Question

过去几天我一直在努力让这个 BST 正常工作，但我在搜索功能上遇到了困难。逻辑似乎是正确的(除非我遗漏了非常重要的细节)但是代码仍然有问题。难道是因为我正在处理字符串？不管怎样，这里有一些代码:

编辑:我已经指出了似乎出错的地方。事实证明，我的根始终为空。我放置了一个 printf 来测试 NULL-case 是否为真，它总是打印为真。我在这个问题的底部添加了我的树初始化。

(更新的)搜索功能:

//Thank you, M Oehm
node* search(node * tree, char *key)
{
    /* char *key is user input */
    int cmp;

    if(tree == NULL) {
        return NULL;
    }

    cmp = strcmp(key, tree->key);   
    if(cmp < 0) return search(tree->left, key);   
    if(cmp > 0) return search(tree->right, key);
    return tree;
}

main函数中的实现:

printf("Enter a string to search the tree with: ");
fgets(findNode, MAX_WORD, stdin);
findString = malloc(sizeof(char)*strlen(findNode)+1);
strcpy(findString,findNode);
printf("findString: %s\n", findString);
searched = search(&root, findString);
if(searched == NULL) {
    printf("No_such_key\n");
    free(findString);
    }
else {
    printNode(searched);
    free(findString);
    }
break;

树初始化(通过文件解析):

 /* Loop through each line in the file*/
 while(fgets(buffer, sizeof(buffer), file) != NULL) {
     tempToken = strtok(buffer, " \n");
     while(tempToken != NULL) {
         /* Assign default values */
         curr = (node *)malloc(sizeof(node));
         curr->left = curr->right = NULL;
         curr->key = malloc(sizeof(char)*strlen(tempToken)+1); /* +1 for '\0' */
         strcpy(curr->key, tempToken);
         curr->frequency = 1;           
         /* Insert node into tree */
         insert(&root, curr);
         /* Get next token */
         tempToken = strtok(NULL, " \n");
     }
 }
 /* Test insertion worked; close file */
 print_inorder(root);
 fclose(file);

插入函数:

void insert(node ** tree, node * item)
{
    /* If no root, item is root */
    if(!(*tree)) {
        *tree = item;
        return;
    }
    /* If item value is less than node in tree, assign to left */
    if(strcmp(item->key,(*tree)->key) < 0) {
        insert(&(*tree)->left, item);
    }
    else if(strcmp(item->key,(*tree)->key) > 0) {
        insert(&(*tree)->right, item);
    }
    else if(strcmp(item->key,(*tree)->key) == 0) {
        (*tree)->frequency++;
    }
}

打印功能告诉我插入工作正常。

Answer 1

您的代码中有两个错误:您没有检查向其传递指针的根节点是否为空，并且您没有从递归函数返回结果。

您的函数不会修改树，因此您不必将指针传递给节点。该方法对于修改树的函数很有用，例如用于插入或删除节点。您的函数应该传递一个指向根节点的指针。这也向用户发出树不会被修改的信号。

所以这是一个更正后的版本:

node* search(node *tree, const char *key)
{
    int cmp;

    if (tree == NULL) return NULL;

    cmp = strcmp(key, tree->key);

    if (cmp < 0) return search(tree->left, key);
    if (cmp > 0) return search(tree->right, key);
    return tree;
}

那个版本必须这样调用:

node *hit = search(tree, "bingo!");

请注意，此函数只进行一次字符串比较并将结果保存在一个临时变量中。您的代码最多调用 strcmp 三次。

你不必在这里使用递归。这甚至有点浪费，因为您必须在第一个电话中过滤答案。当每个步骤都必须维护一个状态时，递归很有用，您可以将其表示为局部变量。在这里，您只需更改输入 node。

这是 search 函数的非递归变体:

node* search(node *tree, const char *key)
{
    while (tree) {
        int cmp = strcmp(key, tree->key);

        if (cmp == 0) return tree;
        tree = (cmp < 0) ? tree->left : tree->right;
    }
    return NULL;
}