Может кто-нибудь объяснить, что делает мой код / ​​как это исправить (поиск узла в BST)?

Question

Цель этой функции заключалась в том, чтобы искать узел и возвращать 0, если не найден, и 1, если найден.Из некоторого тестирования, похоже, что даже если он найден, он все равно возвращает 0 каждый раз, если узел не является корневым.Может кто-нибудь объяснить, почему мой код неправильный?

В основном я устанавливаю переменную = search, а если переменная = 1, печатать присутствует, а если переменная = 0, печатать отсутствует.

Что я проверялс bst 3 и 4. Я протестировал bst и знаю, что он настроен правильно

, если я ищу 3, счетчик возвращает 1 и присутствуют основные отпечатки.если я ищу 4, то, что я думаю, происходит, когда он все еще переходит к оператору if (root-> data == value), устанавливает счетчик в 1 и возвращает его.Однако вместо того, чтобы вернуться к основному, он затем идет к счетчику возврата внизу (который равен 0) и возвращает это к главному, что приводит к отсутствию печати, даже если он там есть.Может ли кто-нибудь шаг за шагом рассказать мне, что происходит в этом коде и почему, и как я могу заставить его вернуть 1 обратно в main?

  int search(struct Node* root, int value){
    int counter = 0;
    if (root->data == value){
            counter = 1;
            return counter;
}       if (root == NULL){
            return counter;
}
    if (value < root-> data){
             search(root->left, value);
}
    else if (value > root->data){
            search(root->right, value);
}

    return counter;
}

РЕДАКТИРОВАТЬ: я также пытался превратить его в функцию void ивместо возврата он печатает «присутствует», если узел найден.Есть ли способ сделать так, чтобы он печатался только один раз, используя этот способ?

Answer 1

Общая форма алгоритма поиска BST:

boolean search (node, value) {
    if node == null return false
    if value == node.data return true
    if (value < node.data)
        return search(root.left, value)
    return search(root.right, value)
}

Answer 2

Когда вы вызываете search() на корневом узле, если нужное значение не находится в корне, но находится в правильном поддереве, тогда search(root->right, value) должно вернуть 1. Но даже если это так, ваша функция все равно вернет0. (Проверьте это: начиная со строки, где вызывается search(root->right, value), предположите, что возвращает 1, и проследите через остальную часть вашей функции, и вы увидите, что она возвращает 0.)

Для того, чтобыисправить это, вам нужно проверить возвращаемое значение из search(root->right, value), и если оно равно 1 (что указывает на то, что значение было найдено в правом поддереве), ваша функция должна будет вести себя соответствующим образом.Аналогично с возвращаемым значением из search(root->left, value).