实现BST的add插入方法时插入首个元素后root仍为null的问题求助

DevOps 小满

2026-9-25

BST插入方法问题分析与修复

核心问题

你的代码问题本质是Java的值传递机制：引用类型的参数传递的是引用的副本，你在私有add方法中对形参n的赋值操作仅作用于局部变量副本，不会修改方法外的实际节点引用（包括类的root属性、父节点的left/right属性）。

首次插入元素时的执行逻辑验证了这个问题：

调用公共add方法时root为null，将null值传递给私有方法的形参n
方法内给局部变量n赋值新节点，但类的root属性没有被任何赋值操作修改，调用结束后root仍然是null

修复方案

将私有add方法的返回值改为当前处理后的节点，递归过程中把返回值赋值给对应父节点的子节点引用，同时用布尔数组存储插入成功/失败的状态：

修改后的公共add方法

/**
 * Inserts the specified element in the tree if no duplicate exists.
 * @param x element to be inserted
 * @return true if the the element was inserted
 */
public boolean add(E x) {
    boolean[] insertResult = new boolean[1];
    root = add(root, x, insertResult);
    return insertResult[0];
}

修改后的私有add方法

private BinaryNode<E> add(BinaryNode<E> n, E x, boolean[] insertResult) {
    if(n == null) {
        insertResult[0] = true;
        size++;
        return new BinaryNode<E>(x);
    }
    int compResult = comparator.compare(x, n.element);
    if(compResult < 0) {
        n.left = add(n.left, x, insertResult);
    } else if(compResult > 0) {
        n.right = add(n.right, x, insertResult);
    } else {
        // 存在重复元素，插入失败
        insertResult[0] = false;
    }
    return n;
}