Количество узлов в BST, которые больше заданного KEY

Я написал код ниже, чтобы подсчитать количество узлов в BST, которые больше заданного KEY:

int Tree::findNumbersThatBiggerThanKey(int key){
    return PrivateFindNumbersThatBiggerThanKey(key, this->rootNode);
}

int Tree::PrivateFindNumbersThatBiggerThanKey(int key, Node* start) {
    if (!start)
        return 0;

    if (start->key > key)
        return 1 + this->PrivateFindNumbersThatBiggerThanKey(key, start->leftNode) +
        this->PrivateFindNumbersThatBiggerThanKey(key, start->rightNode);

    else if (start->key < key)
        return this->PrivateFindNumbersThatBiggerThanKey(key, start->rightNode);

    else /*start->key > key*/
        return this->PrivateFindNumbersThatBiggerThanKey(key, start->leftNode);
}

это мой основной:

int main() {

    int TreeKeys[16] = { 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80 };
    Tree myBst;

    cout << "Printing the three Inorder before adding numbers: \n";
    myBst.printInorder();


    for (int i = 0; i < 16; i++) {
        myBst.AddLeaf(TreeKeys[i]);
    }

    cout << "Printing the three Inorder after adding numbers: \n";
    myBst.printInorder();

    int key = 2;
    cout << "\n\nNumber of nodes that are bigger than "<<key<<" : " <<
         myBst.findNumbersThatBiggerThanKey(key);
    return 0;
}

Печать Inroder работает отлично:

Printing the three Inorder after adding numbers:
2 3 4 14 15 21 32 50 52 64 70 76 80 83 87 100

но когда я ищу количество узлов больше «2», я получаю 14, что неверно (вместо 15):

Number of nodes that are bigger than 2 : 14

Когда я ищу количество узлов, превышающее «1», я получаю 16, что является правильным результатом (я также получаю правильный результат для любых других чисел):

Number of nodes that are bigger than 1 : 16

Я студент и новичок в рекурсии, буду рад объяснениям, почему это произошло и как это исправить.


c++ binary-search-tree
person benjamin    schedule 20.12.2018    source источник
comment
Отступ вашего кода. И предоставить MCVE.   -  person gsamaras    schedule 20.12.2018
comment
Хорошие новости! Это отличная возможность научиться пользоваться отладчиком, который позволит вам запускать программу построчно, проверять значения всех переменных на каждом шаге и наблюдать за логическим ходом программы. Знание того, как эффективно использовать отладчик, является обязательным навыком для каждого разработчика C++. Никто не получает исключения из этого требования. Как только вы научитесь пользоваться отладчиком, вы сможете отлаживать, находить и исправлять подобные ошибки в своем собственном коде, не заходя на stackoverflow.com и не надеясь, что кто-то другой сделает это за вас.   -  person Sam Varshavchik    schedule 20.12.2018
comment
Менее произвольные и меньшие по размеру тестовые данные значительно облегчают поиск проблем.   -  person molbdnilo    schedule 20.12.2018
comment
@BenjaminYakobi готово! Это не минимально воспроизводимый пример. Можем ли мы скопировать и вставить предоставленный вами код, чтобы воспроизвести проблему?   -  person Algirdas Preidžius    schedule 20.12.2018
comment
Нет, вы ошибаетесь. Вы еще не закончили. Показанный код по-прежнему не соответствует всем требованиям минимально воспроизводимого примера, как объяснено в справочный центр. Если кто-либо не может скопировать и вставить то, что вы показали, скомпилировать, запустить и воспроизвести вашу проблему, это, очевидно, не соответствует требованию Complete.   -  person Sam Varshavchik    schedule 20.12.2018
comment
AddLeaf — странное название для функции, которая не добавляет лист.   -  person molbdnilo    schedule 20.12.2018
comment
@SamVarshavchik Я отладил его до того, как пришел к stackoverflow. если я спрашиваю здесь, то только потому, что не нашел, в чем проблема. Извините, что я не упомянул об этом. Я действительно не понимал, почему это произошло. Я не могу скопировать и вставить всю домашнюю работу (более 400+) строк. Я показываю проблемную функцию. Бессмысленно все копипастить. Если вы можете помочь, я действительно буду рад, и спасибо вам за это. а если нет, то тоже хорошо, но у меня сейчас нет другого способа описать свой вопрос.   -  person benjamin    schedule 20.12.2018
comment
@BenjaminYakobi 1) Я не могу скопировать и вставить всю домашнюю работу (более 400+) строк. Я показываю проблемную функцию. Бессмысленно копировать все подряд. Никто не просил вас копировать все подряд. Мы попросили вас создать минимальный воспроизводимый пример (подробности вы читали по ссылке?). 2) Я показываю проблемную функцию. Вы будете поражены количеством раз, когда мы видим, как люди предоставляют только соответствующую функцию только для того, чтобы найти проблему в коде за пределами такой важной функции. (не говорю, что это так, но это одна из причин требования минимального воспроизводимого примера).   -  person Algirdas Preidžius    schedule 20.12.2018

Ответы (2)


arrow_upward
3
arrow_downward

ваш else неверен, это состояние start->key == key, которое следует рассматривать так же, как start->key < key

так перепиши его на

else 
   return this->PrivateFindNumbersThatBiggerThanKey(key, start->rightNode);

или просто объедините его с start->key < key

person apple apple    schedule 20.12.2018
comment
Спасибо, теперь работает нормально. извините, что не предоставили MCVE. - person benjamin; 20.12.2018

arrow_upward
1
arrow_downward

Поскольку вы не предоставляете MCVE, я не могу работать с вашим кодом. Общий способ сделать это таков:

int Tree::PrivateFindNumbersThatBiggerThanKey(int key, Node* node)
{
  if (node == null)
  {
    return 0;
  }
  int countLeft = PrivateFindNumbersThatBiggerThanKey(node->leftNode, key);
  int countRight = PrivateFindNumbersThatBiggerThanKey(node->rightNode, key);

  return (node->key > k ? 1 : 0) + countLeft + countRight;
}
person gsamaras    schedule 20.12.2018