遞歸搜索bst非鍵值

Question

我遇到了這個問題的邏輯問題。我如何搜索整個樹（因爲我不能依賴任何順序搜索）並只返回一個匹配值（如果存在）？如果我返回遞歸調用，一旦它遇到第一片葉子並且沒有找到匹配，它會不會失敗？

使用下面的函數時，會進行調用，直到找到匹配項或到達樹的末尾，並且無論匹配項是否返回最左邊的節點。

我的遞歸函數，在序遍歷：

tnode *find(tnode *ptr, const char *str) 
{ 
    if (ptr == NULL) return ; 

    if(strcmp (str,ptr->str) == 0) 
     return ptr; 


    else 
    { 
     //search left subtree 
     if (ptr->left != NULL) 
      find(ptr->left, str) ; 


     // search right subtree 
     if (ptr->right != NULL) 
      find(ptr->right, str) ; 
    } 

    return; 

} 

Answer 1

如果左子樹找到返回非空，您有一個比賽，應該歸還。目前，你甚至不希望看到它是否發現任何東西。

如果它沒有找到任何東西，你可以返回右子樹查找的結果（如果它是NULL，你到處找，沒有找到任何東西）。

tnode *find(tnode *ptr, const char *str) 
{ 
    ptr *found; 

    if (ptr == NULL) return NULL; /* nothing to see here */ 

    if(strcmp (str,ptr->str) == 0) 
     return ptr; /* it is here! */ 

    /* try left subtree */ 
    found = find(ptr->left, str); 
    if (found) return found; /* it was on the left */ 

    /* try right subtree */ 
    return find(ptr->right, str); 
} 

Answer 2

第一：

if (ptr == NULL) return ; 

您應該根據函數原型（tnode *find(tnode *ptr, const char *str)）返回一個值。

第二：

find(ptr->right, str); 

你不使用返回值，所以反正結果將是不正確的。

第三種：

return; 

同爲第一個。

如果你將解決所有問題，它應該工作。

BTW if (ptr->left != NULL)沒有必要，因爲您在函數的開頭檢查ptr == 0。

最後一個請注意編譯器警告。