在二进制搜索树中的搜索功能会导致段错误

问题描述：

我一直在试图让这个BST在过去的几天工作，我陷入了搜索功能。逻辑似乎是正确的（除非我错过了非常重要的细节），但代码仍然有问题。难道是因为我在处理字符串？无论如何，这里是一些代码：在二进制搜索树中的搜索功能会导致段错误

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

的（更新）搜索功能：

//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; 
}

实现在主要功能：

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++; 
    } 
}

打印功能显示插入功能正常。

您应该测试'如果（*树== NULL）'开头搭上了空子树的情况。为什么你在这里使用双指针呢？你的函数不修改树。 – 2014-11-23 07:40:32

我认为你应该确保树的构建是正确的 - 单元测试？ – 2014-11-23 07:41:42

我不是在搜索整棵树吗？或者我只需要使用一个节点：根。从那里我可以遍历到根的孩子，等等？ – Plaidypus 2014-11-23 07:42:26

答

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

您的函数不会修改树，所以您不必将指针传递给节点。该方法对修改树的函数很有用，例如用于插入或删除节点。你的功能通过一个指向根节点的指针。这也向用户表明该树不会被修改。

所以这里有一个修正版本：

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功能的非递归variant：

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; 
}

感谢您澄清通过指针混淆。这样做更有意义。现在，我修复了我的搜索功能，并且没有seg故障，但我一直得到一个“No_such_key”，这是我返回的节点为NULL时的消息。 ** char *键**是用户输入;这可能是问题吗？我是否忘记添加空终止符，或忘记删除此字符串中多余的不需要的字符？ – Plaidypus 2014-11-23 08:18:07

您可以在插入字符串的代码中使用'strtok'删除一个可能的后续换行符，但是您不会为使用该字符串的字符串执行此操作。 – 2014-11-23 09:00:09

啊啊，这是那些脸掌的时刻之一。它现在有效！谢谢大家！谢谢！ – Plaidypus 2014-11-23 16:22:31

答

search(&(*tree)->left, key);

应该是：

return search(&(*tree)->left, key);

同为正确的情况下。

答

尝试改变你的功能到这样的东西。

node* search(node * tree, char * key) 
{ 
    if(tree == NULL) { 
     return NULL; 
    } 

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

    else if(strcmp(key,tree->key) > 0) { 
     return search(tree->right, key); 
    } 


    printf("Success!\n"); 
    return tree; 

}

一个简单的节点*就可以满足您的问题。不需要双指针。

在二进制搜索树中的搜索功能会导致段错误

相关推荐