Java实现二叉搜索树（BST）时根节点无法赋值问题求助

Java 所有参数传递都是值传递，不存在按引用传参的机制：当把对象引用作为参数传入方法时，传递的是引用值的拷贝，并非引用本身的内存地址。在方法内部给形参重新赋值时，只会修改这份拷贝的指向，完全不会影响原引用变量的值——这是你插入元素后root始终为null、节点无法挂载到树上的根本原因。
结合你的代码走一遍执行链路，问题会更直观：

1. 初始状态下类的this.root为null，调用addElementNotSeen(x, this.root)时，会把this.root的值（也就是null）拷贝一份，传给私有方法的形参curent
2. 进入方法后判断curent == null为真，执行curent = new node(x , null , null)——这行只是让刚才拷贝生成的形参curent指向新创建的节点，原this.root的值没有任何修改，还是null
3. 递归分支的逻辑完全一样：比如走到某个非空节点的右子树时，传递的是curent.right的值（要么是null，要么是子节点的内存地址）的拷贝，就算在空位置新建了节点，也只是修改了那份拷贝的指向，没有给当前节点的right属性赋值，整个树的结构从始至终没有被改动。

Java没有指针引用语法，等价的递归插入逻辑需要用方法返回值把新建的节点引用逐层传回上一层，由上一层完成子节点指针的赋值，具体调整点：

• 把私有递归方法的返回值从void改为node类型
• 公共addElement方法接住递归返回的根节点，直接赋值给类的root属性
• 递归过程中，把左右子树递归返回的节点，分别赋值给当前节点的left/right属性

修正后的核心代码：

public void addElement(int x) {
    // 接住递归返回的根节点，完成对root的正确赋值
    this.root = addElementNotSeen(x, this.root);
}

private node addElementNotSeen(int x, node current) {
    // 遍历到空的插入位置，直接返回新建节点给上层调用方
    if (current == null) {
        return new node(x, null, null);
    }
    // 按BST的规则递归查找插入位置
    if (x > current.data) {
        // 将递归返回的右子节点，挂到当前节点的right指针上
        current.right = addElementNotSeen(x, current.right);
    } else {
        // 将递归返回的左子节点，挂到当前节点的left指针上
        current.left = addElementNotSeen(x, current.left);
    }
    // 遍历完成后，将当前节点本身返回给上层
    return current;
}

如果用C实现同样的递归插入，通常会把形参写为node*& cur（指针的引用）——在函数内部给cur赋值时，会直接修改原指针变量的指向。Java没有这种语法，上面的返回值写法，本质就是替代了C里指针引用的效果：不靠修改传入的形参本身，而是把新节点作为返回值，由调用方完成指针的赋值，最终的树结构构建逻辑和C++版本完全一致。

小细节优化：你代码里的形参curent是拼写疏漏，正确拼写是current，不影响运行但会降低代码可读性。

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