如何在Java中创建二叉搜索树？插入方法遇空指针异常求助

代码中的核心错误 #

• 外部类insert方法无限递归：你写的public void insert(T newObject) { this.insert(newObject); }会持续调用自身，既无法执行插入逻辑，还会引发栈溢出，这是首要问题。
• Node类insert方法逻辑混乱：
  • Node类的insert错误操作外部类的root变量，而非当前Node实例的属性。比如应该用this.data比较，而非root.data，否则所有插入操作都在修改根节点，完全违背二叉搜索树的结构逻辑。
  • 当当前节点的左/右子节点为null时，直接调用root.left.insert(newObject)会触发NullPointerException——null对象无法调用方法，正确逻辑应该是在子节点为null时创建新Node，而非递归调用insert。

修复后的完整代码 #

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;
        }

        // Node类的insert仅处理当前节点的子树插入
        public void insert(T newObject) {
            if (newObject.compareTo(this.data) < 0) {
                if (this.left == null) {
                    this.left = new Node(newObject);
                } else {
                    this.left.insert(newObject);
                }
            } else if (newObject.compareTo(this.data) > 0) {
                if (this.right == null) {
                    this.right = new Node(newObject);
                } else {
                    this.right.insert(newObject);
                }
            }
            // 元素相等的情况可根据需求处理：忽略/抛出重复元素异常等
        }
    }

    private Node root;

    public BinarySearchTree() {
        this.root = null;
    }

    // 外部类insert处理根节点为null的边界情况
    public void insert(T newObject) {
        if (this.root == null) {
            this.root = new Node(newObject);
        } else {
            this.root.insert(newObject);
        }
    }
}

修复要点说明 #

1. 外部类insert方法不再递归调用自身，先判断根节点是否为null：为空则直接创建根节点，否则调用根节点的insert方法处理子树插入。
2. Node类的insert改为操作当前节点（this）：
   • 对比新元素与当前节点的data，决定插入左/右子树。
   • 当子节点为null时直接创建新Node，避免调用null对象的方法，彻底解决NullPointerException。
3. 新增构造函数初始化root为null，代码逻辑更清晰。

内容的提问来源于stack exchange，提问作者charlievans