рекурсивно поиск 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, то есть матч и должен вернуть его. В настоящее время вы даже не смотрите, не нашел ли что-нибудь.

Если это не найти что-нибудь, вы можете вернуть результат поиска поддерева (если он 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 в начале функции.

Последний номер обратите внимание на предупреждения компилятора.