如何在 Java 中创建二叉搜索树？

Question

我正在 OOP 课上做作业，但我发现自己哪里出错了。即使我没有对任何节点执行任何操作，我仍然会收到 NullPointerExceptions，这让我感到困惑。 我正在尝试创建一个插入方法，该方法采用通用对象参数并且不返回任何内容 - 这就是我目前所拥有的：

public class BinarySearchTree<T extends Comparable <T>> implements BinaryTree<T> {
    class Node {
       public T data;
       public Node left;
       public Node right;
       
       public Node(T newObject) {
          this.data = newObject;
          this.left = null;
          this.right = null;
       }
       
       public void insert(T newObject) {
          if (root == null) {
             root = new Node(newObject);
          } else if (newObject.compareTo(root.data) < 0) {
             root.left.insert(newObject);
          } else if (newObject.compareTo(root.data) > 0) {
             root.right.insert(newObject);
          }
       }
    }
    
    private Node root;
    
    public void insert(T newObject) {
       this.insert(newObject);
    }
}

但是，通过运行以下命令，我不断抛出 NullPointerExceptions：

bstExample.insert(5);

我看了一堆 YouTube 视频，重读了教科书中有关二叉（搜索）树的部分，并向同学寻求支持，但还没有任何结果。

Answer 1

将

insert

作为

Node

的实例方法时，插入到空树中会出现问题，因为

this.root

将是

null

并且您无法在

null

上调用任何方法。同样，当

root.left.insert(newObject);

为

root.left

时，调用

null

也不起作用。您需要先构造新的

Node

以设置为

root.left

。

在

insert

类本身中实现辅助

BinarySearchTree

方法要简单得多。

public void insert(T newObject) {
   this.root = insert(this.root, newObject);
}

private Node insert(Node curr, T obj) {
    if (curr == null)
        return new Node(obj);
    else {
        final int comp = obj.compareTo(curr.data);
        if (comp < 0)
            curr.left = insert(curr.left, obj);
        else if (comp > 0) 
            curr.right = insert(curr.right, obj);
        return curr;
    }
}