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

Question

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

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

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

Answer 1

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

, поэтому перепишите его на

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

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

Answer 2

Поскольку вы не предоставляете 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;
}