我一直在试图让这个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