BST 递归简单插入

Question

我正在尝试编写一个小函数来将节点插入 BST。 "insert" 函数工作正常。我把它改成"insert2"，但它不起作用。我不知道为什么它不起作用。 "insert" 和 "insert2" 在运行时有什么区别？

插入方法

public void insert(Node node, int x) {
    if (x < node.val) {
        if (node.left == null) node.left = new Node(x);
        else insert(node.left, x);
    } else {
        if (node.right == null) node.right = new Node(x);
        else insert(node.right, x);
    }
}

insert2 方法

public void insert2(Node node, int x) {
        if (node == null) {
            node = new Node(x);
            return;
        }
        if (x < node.val) insert2(node.left, x);
        else insert2(node.right, x);
    }

节点定义

public class Node {
    int val;
    Node left, right;
    public Node (int _val) {
        this.val = _val;
    }
}

提前致谢。

Answer 1

Java 是一个 pass by value language。这意味着当您将变量传递给方法时，无论是原始变量还是对象，该方法都无法更改该变量，因为它不知道该变量的任何信息。该方法有自己的变量，并且将任何新内容分配给参数变量只会在该范围内持续存在，不会改变其他绑定或对象。

当你有：

public static void update(String str) {
  str = "changed";
}

然后做：

String s = "hello";
update(s);
System.out.println(s);

它会打印"hello"，因为虽然"hello"的地址被传递给update，更新只更新局部变量到新字符串的地址。赋值永远不会改变用于应用方法的变量或两个变量指向的对象。

String h = "hello";
String w = "world";
String x = h; // x points to the same string as h
x = w;        // x got it's value changed to point to w
System.out.println(h + " " + w);

最后一条语句打印 "hello world"，而不是 "world world"，就好像赋值改变了前一个对象。

那么在您的 insert 方法中发生了什么？

insert2 覆盖了一个局部变量 恰好是null 到一个新的Node，但它与传递的原始参数无关。新创建的节点只能从该范围访问，因此当它 returns 时，新节点已准备好进行垃圾收集。传递给原始方法的树从未发生变化，因此它永远不会获得新值。

如果您查看 insert，它需要一个非空节点并在该节点或其后代之一上向右或向左属性改变。因此，当您检查原始参数时，树发生了变化，因为它没有改变参数，而是改变了对象本身。

改变对象与改变变量不同。

BST 递归简单插入

BST simple insertion with recursion

java

tree

recursion

binary-tree

binary-search-tree