Java-программа для вычисления количества красных узлов в красно-черном дереве

#java #counting #red-black-tree

#java #подсчет #red-black-tree

Вопрос:

Я создаю программу для определения количества красных узлов в красно-черном дереве. Я уже реализовал RED BLACK BST, который строит дерево после считывания введенного текста. Я застрял на том, как подсчитать количество красных узлов? Я знаю, что красные узлы могут быть только левосторонними, а у красного родительского узла не может быть красного дочернего узла. Какой метод был бы подходящим для решения этой проблемы?

1. Пожалуйста, поделитесь кодом, который у вас есть на данный момент (построение дерева и подсчет узлов)!

2. Я добавил то, что у меня есть

3. Вы бы передали корневой узел своему методу countRed, чем рекурсивно вызывать его снова с помощью left amp; right node (при вызове isRed). Вы должны попробовать!

4. @Alex Я обновил свой код! Однако в настоящее время я получаю исключение с нулевым указателем

5. на самом деле сейчас я получаю эту ошибку: на нестатическую переменную root нельзя ссылаться из статического контекста, когда я запускаю ее в моем основном методе

Ответ №1:

Рекурсивное решение будет выглядеть следующим образом:

 public static int countRed(Node node) {
    int nbRed = 0;
    if (node == null) {
        return 0;
    }
    nbRed  = countRed(node.left);
    nbRed  = countRed(node.right);

    if(node.isRed()){
        nbRed  ;
    }
    return nbRed;
}

Протестировано

Я тестировал ваш код с помощью простого цикла:

 RedBlackBST tree = new RedBlackBST();
tree.root = tree.put(null, 0, 0);

for (int i = 1; i < 10; i  ) {
    tree.root = tree.put(tree.root, i, i);
}
int redTotal = tree.countRed(tree.root);

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

1. Спасибо! Однако я все еще получаю ошибку: на нестатическую переменную root нельзя ссылаться из статического контекста, когда я запускаю ее в своем основном методе … и когда я меняю свой корневой узел на статический, тогда он говорит, что на узел нестатического метода нельзя ссылаться из статического контекста, когда я запускаю его в своем основном методе?

2. Измените ‘tree.countRed(дерево);’ на ‘tree.countRed(дерево.корень);’ И ‘if (root.isRed(корень))’ на ‘if (isRed (корень))’

3. Вашему коду был бы полезен небольшой рефакторинг. например, метод ‘isRed’ => это должен / может быть метод в Node, поэтому вы должны вызывать ‘node.isRed()’ вместо ‘isRed (узел)’

4. спасибо за всю вашу помощь! Он компилируется и запускается сейчас, однако он неправильно подсчитывает узлы, поэтому, я думаю, я начну сначала.

5. код для других методов был предоставлен в учебнике, так что, вы думаете, проблема в моем методе подсчета?