在二進制搜索樹中的搜索功能會導致段錯誤

我一直在試圖讓這個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++; 
    } 
}

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

來源

2014-11-23 Plaidypus

您應該測試'如果（*樹== 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; 
}

來源

2014-11-23 07:59:50

感謝您澄清通過指針混淆。這樣做更有意義。現在，我修復了我的搜索功能，並且沒有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);

同爲正確的情況下。

來源

2014-11-23 07:50:51 JS1

嘗試改變你的功能到這樣的東西。

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; 

}

一個簡單的節點*就可以滿足您的問題。不需要雙指針。

來源

2014-11-23 07:50:52

在二進制搜索樹中的搜索功能會導致段錯誤

回答

相關問題