Java中BinarySearchTree插入方法后续调用为何能构建二叉搜索树？

在使用以下Java代码实现二叉搜索树插入节点时，首次调用insert方法会更新root，这很好理解。但后续调用时，root不为空，方法里只操作了赋值为root的currentNode变量，看起来没碰过root本身，可为什么新节点还是能被正确添加为root的子节点，进而构建出完整的二叉树？

public class BinarySearchTree {

    class BSTNode {

        public int value;
        public BSTNode left;
        public BSTNode right;
    }


    BSTNode root;

    BinarySearchTree () {
        root = null;
    }



    //Insert
    public void insert(int val) {

        BSTNode newNode = new BSTNode();
        newNode.value = val;

        if (root==null) {
            root = newNode;                //Root gets updated
            return;
        }

        BSTNode currentNode = root;        //currentNode will be worked upon

        while (true) {

            if (val <= currentNode.value) {

                if (currentNode.left==null) {
                    currentNode.left = newNode;
                    return;
                }

                currentNode = currentNode.left;
            }

            else {

                if (currentNode.right==null) {
                    currentNode.right = newNode;
                    return;
                }

                currentNode = currentNode.right;
            }
        }
    }
}

解答 #

核心原因是Java的对象引用特性：

• currentNode = root这行代码，不是复制root节点本身，而是把root指向的BSTNode对象的内存引用地址赋值给currentNode。也就是说，currentNode和root最初指向的是同一个节点对象。
• 循环过程中，currentNode会不断指向currentNode.left或currentNode.right，这只是让它切换到树里的下一个节点对象，但我们真正做的关键操作是修改这些节点对象的left或right属性——这些属性属于树结构的一部分，和root是间接关联的（比如是root的子节点、孙节点）。
• 举个例子：当执行currentNode.left = newNode时，我们修改的是当前currentNode指向的那个节点的left引用，让它指向新节点。而这个节点本身就在root的树结构里，所以新节点自然就被加入到整个树中了。

简单总结：我们不需要直接修改root变量，只要通过引用修改root关联的树节点的属性，就能完成新节点的插入。

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