在 BinarySearchTree 中获取前任的问题

Question

这是我的 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 测试@Testpublic 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());}}它在最后一个 for 循环中到达 assertTrue，然后因空指针异常而失败。为什么会抛出空指针？

Answer 1

当 getBeforeHelper 方法找到带有您的键的元素时，它会尝试获取左边的元素。如果您的左元素不存在，那将不起作用。在这种情况下，getBeforeHelper 返回为 null 的“current”。在这种情况下，您对该空元素调用 get() 并获得空指针异常。

Answer 2

看起来您最终会遇到以下情况：

//                             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()在您的断言中进行评估。

剩下要做的就是了解这种情况究竟何时发生并找到另一种非失败的方法来处理它！我在上面给出了一些提示，但既然你真的在学习，我会让你弄清楚细节:)。