Рекурсивный поиск в бинарном дереве возвращение и истинного и ложного

Question

Для присвоения я должен придумать рекурсивную функцию под названием all_less, которая принимает в указателе на любой произвольного дерева (TN<T>*) и параметр T. Он возвращает true, если все значения меньше, чем параметр T, иначе он возвращает false.

Переменные экземпляра для моего Tree класса это:

T  value; 
TN<T>* left; 
TN<T>* right; 

И прототип функции для all_less выглядит следующим образом:

template<class T> 
bool all_less(TN<T>* t, T v) 

Поскольку я должен считать несортированный бинарное дерево, я понял, рекурсивный переход вниз по каждому поддереву и проверка каждого значения будет работать нормально. После тестирования этой функции:

template<class T> 
bool all_less(TN<T>* t, T v) 
{ 
    if(v <= t->value) { 
     return false; 
    } else if(v > t->value) { 
     if(t->right != nullptr && t->left != nullptr) { 
      all_less(t->right, v); 
      all_less(t->left, v); 
     } 
    } 
    return true; 
} 

После того, некоторые проблемы с функцией почти всегда возвращает истину, я ставлю некоторые заявления печати перед return true и return false, чтобы посмотреть, что происходит.

В качестве примера предположим, что в двоичном дереве мы имеем значения 12, 15, 14, 5. Запуск моей функции с помощью:

TN<int>* t; 
std::cout << all_less(t, 15); 

в качестве входных данных, вывод будет таким:

true 
false 
true 
true 

Конечный результат будет в конечном итоге верно, даже если ложно был возвращен один раз. Как я могу получить его так, чтобы, если он возвращает false, функция возвращает false и немедленно останавливается? Также есть ли лучший способ реализовать эту функцию? Вначале у меня было несколько дополнительных команд if-else, чтобы проверить, были ли правые/левые поддеревья пустыми и продолжались оттуда, но на самом деле они ничего не делали.

Answer 1

Вы игнорируете возвращаемые значения рекурсивных вызовов.

Конечный результат будет верным, даже если ложь была возвращена один раз.

Это false было возвращено из другого вызова функции и исчезло в большой битбакет в небе.

Рекурсивные функции работают точно так же, как и любые другие функции - если у вас есть

int f() { return 0:} 
int g(int x) { 
    if (x == 0) 
     f(); 
    return 1; 
} 

g(0) возвращает 1, даже если 0 был «возвращен после».
Если g(0) должен возвращать значение f() «s, он должен сделать это явно:

int g(int x) { 
    if (x == 0) 
     return f(); 
    return 1; 
} 

Вы также предполагая, что все узлы имеют либо ноль или двух детей.

Если принять соглашение, что все элементы в пустом дереве меньше, чем значение, вы можете написать

template<class T> 
bool all_less(TN<T>* t, T v) 
{ 
    return !t 
     || ( t->value < v 
      && all_less(t->right, v) 
      && all_less(t->left, v)); 
} 

Answer 2

Ваша функция:

template<class T> 
bool all_less(TN<T>* t, T v) 
{ 
    if(v <= t->value) { 
     return false; 
    } else if(v > t->value) { // Why do you need this check? 
     if(t->right != nullptr && t->left != nullptr) { 
      // This is wrong because it's possible for one them to 
      // nullptr while the other is not. 

      all_less(t->right, v); 
      all_less(t->left, v); 
      // The above function calls are no op. You are calling 
      // the function recursively but are ignoring the return 
      // values. 
     } 
    } 
    return true; 
} 

Это должно работать:

template<class T> 
bool all_less(TN<T>* t, T v) 
{ 
    if(v <= t->value) { 
     return false; 
    } 

    if(t->right != nullptr) 
    { 
     if (!all_less(t->right, v)) 
     { 
     return false; 
     } 
    } 

    if (t->left != nullptr) 
    { 
     if (!all_less(t->left, v)) 
     { 
     return false; 
     } 
    } 
    return true; 
} 

P.S. Неиспользованный код.