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

Question

Я работал над этим часами, и я все еще не могу найти рабочее решение.

11.13 Управляемый поток двоичных данных X279: Упражнение по малому количеству дерева двоичного поиска

Answer 1

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

Мой первый ответ не сработал. Этот новый делает.

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

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

Моя рабочая реализация:

public int BSTsmallcount(BinNode root, int key)
{
    int count = 0;

    if (root == null) {
        return 0;
    }
    else if (root.value() < key) {
        count++;
        count += BSTsmallcount(root.left(), key);
        count += BSTsmallcount(root.right(), key);
    }
    else {
        count += BSTsmallcount(root.left(), key);
    }

    return count;
}