关于二叉搜索树递归插入中root赋值语句的疑问

问题背景 #

我在实现二叉树的递归插入函数时，已经完成判断插入位置的核心逻辑，但存在几处困惑。现有代码如下：

public void insert(E data) {
    root = insert(root, data);
}

private Node<E> insert(Node<E> value, E data) {
    if(value == null) {
       return new Node<E>(data);
    }
    else if (data.compareTo(value.data) > 0 )  {
        value.right = insert(value.right, data); 
    }
    else if(data.compareTo(value.data) <= 0) {
        value.left = insert(value.left, data);
    }
    return value; 
}

我的疑问集中在public方法中的这行代码：

public void insert(E data) {
    root = insert(root, data);
}

具体疑问：

• 为什么需要这行代码？root是否会主动发生变化？
• 搭档说除了第一次插入外root不会改变，这个说法对吗？
• 私有递归函数是否总是返回最初的父节点作为root？

解答 #

1. 为什么需要root = insert(root, data)？root会不会主动变化？
   Java里对象引用是值传递，root作为二叉树的根节点引用，本身不会主动改变。第一次插入时，原root是null，私有insert函数会返回一个新创建的Node对象，这时候必须把这个新对象赋值给root——不然二叉树的根永远是null，后续所有操作都无效。如果删掉这行代码，第一次插入后你根本拿不到新生成的根节点，整个树等于没创建。

2. 除了第一次插入外root不会改变，这个说法正确吗？
   完全正确。二叉搜索树的插入逻辑是把新节点挂到某个叶子节点的空位置上，只有当树为空（也就是第一次插入）时，root才会被替换成新节点。只要树已经有根了，后续插入只会修改根节点的左/右子节点引用，或者更下层节点的子节点引用，根节点本身的引用指向不会变。这时候insert(root, data)返回的还是原来的根节点，赋值给root相当于没变化，但这行代码不能省——因为必须靠它处理第一次插入的情况。

3. 私有递归函数是否总是返回最初的父节点作为root？
   不是“最初的父节点”，而是每次递归调用都会返回当前处理的节点：

• 当传入的value是null时，返回新创建的节点（这是递归终止条件，用来生成新节点）。
• 当传入的value不为null时，处理完左/右子树的插入后，会把当前的value原封不动返回。
  所以整个递归结束后：如果是插入空树，返回的是新创建的根节点；如果是插入非空树，最终返回的就是原来的根节点。

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