二叉搜索树插入值异常：插入第二个节点时出现h为空错误

核心错误原因 #

插入第二个节点时触发空指针异常，根源是insertT方法未处理传入null节点的情况，直接访问h.item.key()导致报错。同时代码还存在若干语法、类型一致性问题，具体如下：

具体问题点 #

• 参数类型与拼写错误：insertAsRoot方法的第二个参数声明为TreeNode h，但代码中统一使用Node类型，类型不匹配；参数Itemitem是拼写错误，应为Item item。
• insertT未处理空节点：递归调用insertT时，若当前节点的左/右子节点为null，方法接收的h参数即为null，直接访问h.item会触发空指针异常。
• 属性访问不一致：rotL方法中直接使用h.right = x.left赋值，其他地方却用setLeft/getLeft方法，破坏封装性且易出错。
• 未定义变量与缺失成员：insert方法中的look变量未声明；类中缺少根节点root的成员变量；insert方法未指定返回类型。

修复后的代码 #

public class Tree{
    private Node root; // 补充根节点成员变量

    public void insert(Item item) { // 补充返回类型void
        // 此处需补充item存在性检查逻辑，示例用临时占位
        // boolean exists = find(item) != null;
        if (false) {
            System.out.println("Number already exists");
            System.exit(0);
        } else {
            root = insertAsRoot(item, root);
        }
    }
    
    private Node insertAsRoot(Item item, Node h) { // 修正参数类型与拼写
        if (h == null) {
            Node node = new Node(item);
            node.N = 1; // 初始化子树节点数
            return node;
        } 
        if (Math.random()*(h.N+1) < 1.0) {
            h = insertT(item, h);
        }
            
        if (item.key() < h.item.key()) {
            h.setLeft(insertAsRoot(item, h.getLeft()));
        } else {
            h.setRight(insertAsRoot(item, h.getRight()));
        }
        h.N++;
        return h;
    }
    
    private Node insertT(Item item, Node h) {
        if (h == null) { // 添加空节点判断，直接创建新节点返回
            Node node = new Node(item);
            node.N = 1;
            return node;
        }
        if (item.key() < h.item.key()) {
            h.setLeft(insertT(item, h.getLeft())); 
            h = rotR(h);
        } else {
            h.setRight(insertT(item, h.getRight()));
            h = rotL(h); 
        }
        h.N++; // 更新子树节点数
        return h;
    }
    
    private Node rotR(Node h) {      
        Node x = h.getLeft();
        h.setLeft(x.getRight()); 
        x.setRight(h);
        // 旋转后更新子树节点数
        h.N = 1 + (h.getLeft() != null ? h.getLeft().N : 0) + (h.getRight() != null ? h.getRight().N : 0);
        x.N = 1 + (x.getLeft() != null ? x.getLeft().N : 0) + (x.getRight() != null ? x.getRight().N : 0);
        return x;
    }
    
    private Node rotL(Node h) {      
        Node x = h.getRight();
        h.setRight(x.getLeft()); // 统一使用set方法
        x.setLeft(h);
        // 旋转后更新子树节点数
        h.N = 1 + (h.getLeft() != null ? h.getLeft().N : 0) + (h.getRight() != null ? h.getRight().N : 0);
        x.N = 1 + (x.getLeft() != null ? x.getLeft().N : 0) + (x.getRight() != null ? x.getRight().N : 0);
        return x;
    }

    // 补充Node类的示例实现
    private class Node {
        Item item;
        Node left;
        Node right;
        int N; // 子树节点总数

        Node(Item item) {
            this.item = item;
        }

        Node getLeft() { return left; }
        void setLeft(Node left) { this.left = left; }
        Node getRight() { return right; }
        void setRight(Node right) { this.right = right; }
    }

    // 补充Item接口的示例定义
    private interface Item {
        int key(); // 根据实际业务调整key的类型
    }
}

关键修复说明 #

1. 在insertT方法开头添加空节点判断，直接创建新节点返回，避免空指针访问。
2. 修正参数类型与拼写错误，保证代码类型一致性。
3. 旋转操作后更新节点的N值（子树节点数），确保随机选择根节点的逻辑正确。
4. 统一属性访问方式，使用set/get方法替代直接赋值，维护封装性。
5. 补充缺失的成员变量与方法返回类型，修复编译错误。

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