Проблема с получением предшественника в BinarySearchTree - PullRequest
Новая
       1

Проблема с получением предшественника в BinarySearchTree

0 голосов
/ 28 сентября 2018

Это мой метод getBefore 

 public Node getBefore() {
    return getBeforeHelper(root, this.data);
}

public Node getBeforeHelper(Node node, K key) {
    Node current = null;
    if(node != null) {
        if(node.data == key) {
            if(node.left != null) {
                current = node.left;
                while(current.right != null) {
                    current = current.right;
                }
                System.out.println(current.get());
                return current;
            }
        }
        else if(lessThan.test(key, node.data)) {
            return getBeforeHelper(node.left, key);
        }
        else if(lessThan.test(node.data, key)) {
            return getBeforeHelper(node.right, key);
        }
    }
    else {
        return null;
    }
    return current;
}

и это тест Junit, который он не может пройти 

@Test
public void beforeBST() {
BinarySearchTree<Integer> bst = new BinarySearchTree<>((Integer x, Integer y) -> x < y);
assertTrue(bst.isEmpty());
int[] a = new int[] { 12, 4, 18, 5, 11, 8, 15, 9, 17, 20, 3, 13, 19, 2, 14, 7, 6, 10, 1, 16 };
int n = a.length;
for (Integer key : a) 
  bst.insert(key);
assertNull(bst.search(1).getBefore());
for (int i = 2; i <= n; i++) {
    System.out.println(bst.search(2).getBefore());
    assertTrue(i - 1 == bst.search(i).getBefore().get());
}

}

Он попадает в assertTrueв последнем цикле for, а затем завершается с ошибкой нулевого указателя.Почему он выбрасывает нулевой указатель?

Ответы [ 2 ]

0 голосов
/ 28 сентября 2018

Похоже, вы оказались в случае, когда: 

//                             this yields null
//                               v          v
assertTrue(i - 1 == bst.search(i).getBefore().get());
//                                           ^    ^
//                   attempt to access a method belonging to a null reference

Рассмотрим случай, когда в getBeforeHelper у вас есть:

  • node != null (всегда true в тесте, который вызывает проблемы)
  • node.data == key (true когда вы достигли Node, который вы искали)
  • node.left == null (просто подумайте: когда это произойдет?)

В этом случае вы получите практически следующее тело для метода getBeforeHelper (отбрасывая все блоки else, в которых вы это делалиПройдите тест if и отбросьте все содержимое блока if, тест которого не прошел): 

public Node getBeforeHelper(Node node, K key) {
    Node current = null;
    if(node != null) { // true
        if(node.data == key) { // true
            if(node.left != null) { // false
            }
        }
    }

    return current;
}

Ну, вот, вы возвращаете null.
А потом внизлиния, пытающаяся оценить null.get() в вашем утверждении.

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

0 голосов
/ 28 сентября 2018

Когда метод getBeforeHelper находит элемент с вашим ключом, он пытается получить левый элемент.Это не сработает, если ваш левый элемент не существует.В этом случае getBeforeHelper возвращает значение current, равное null.В этом случае вы вызываете get () для этого нулевого элемента и получаете исключение нулевого указателя.

...