Подсчет количества узлов меньше X в BST

Question

У меня есть код, который дает мне эти проблемы.Можете ли вы дать мне какой-нибудь намек или руководство относительно ошибки, которую я совершаю, или любых изменений, которые я должен сделать?Ошибки:

BSTNode '<' Golfer '>' не может быть преобразован в BinarySearchTree '<' Golfer '>'.

public int countLess (BinarySearchTree <Golfer> tree, int value) {
BSTNode<Golfer> node = tree.node;

if (node == null) 
return 0;

int left = countLess(node.getLeft(), value);
int right  = countRight(node.getRight(), value);
return (node.getInfo() > maxValue ? 1:0) + countLeft + countRight;
}

Answer 1

Я думаю, вы должны выполнить обход по порядку BST.Обход по порядку BST всегда дает вам элемент в порядке возрастания.Просто сохраняйте переменную count во время обхода inorder (и продолжайте увеличивать ее для каждого посещенного узла), и как только значение любого узла станет больше X, просто 'break'.

Окончательное значение вВаша переменная count будет ответом.

BST: дерево двоичного поиска

Answer 2

Я думаю, что это должно быть примерно так, как я предполагаю, node.getLeft() на самом деле дает вам узел в BST, а не полное левое поддерево.

public int countLess (BSTNode <Golfer> node, int value) {
    if (node == null) 
         return 0;
    int left = countLess(node.getLeft(), value);
    int right  = countLess(node.getRight(), value);
    return (node.getInfo() > maxValue ? 1:0) + left + right;
}

Надеюсь, это решит вашу проблему.Я могу предоставить более правильное решение, если вы сможете поделиться реализацией классов BinarySearchTree и BSTNode.