java - 插入二叉搜索树的两种相似算法

Question

我问了一个similar question上一次关于下面的第二种算法，被称为 Is Java “pass-by-reference” or “pass-by-value”?线。

我知道，当您将变量传递给方法时，Java 会创建它的影子副本，因此您无法修改原始变量，但这正是让我感到困惑的地方。

下面是我最初传入根节点的两个有点相似的算法——第一个有效，但第二个无效。

首先

public void insert(int element) {
    Node temp = new Node(element);

    if(root == null) {
        root = temp;
        root.parent = null;
        size++;
    } else {
        insert(root, temp); 
        size++;
    }
}

private void insert(Node current, Node temp) {
    if(temp.element < current.element) {
        if(current.leftChild == null) {
            current.leftChild = temp;
        } else {
            insert(current.leftChild, temp);
        }
    } 
    else if(temp.element >= current.element) {
        if(current.rightChild == null) {
            current.rightChild = temp;
        } else {
            insert(current.rightChild, temp);
        }
    }
}

输出:

第二个(不起作用)

public void insert(int data) {
    Node temp = new Node(data);

    if(root == null) {
        root = temp;
        size++;
    } else {
        insert(root, temp);
        size++;
    }
}

private void insert(Node current, Node temp) {
    if(current == null)
        current = temp;
    else if(temp.element < current.element)
        insert(current.leftChild, temp);
    else if(temp.element >= current.element)
        insert(current.rightChild, temp);
}

输出:

第一个是我自己写的，第二个是从Wikipedia得到的.为什么第一个有效而第二个无效？

Answer 1

让我们看看引用是什么。 (Java 引用，不要与 C++ 引用混淆)

假设我们有一些带有地址的内存，在这种情况下数据是一些字符串对象

[ address ][ data ]
[       0 ][  abc ]
[       1 ][   de ]
[       2 ][    y ]
[       3 ][  foo ]
[       4 ][ baar ]

如果我们有一个引用，那么这个引用只是一个地址，而不是数据本身!

int i = 15; // this is a primitive type, the variable i holds the data directly
            // 15 in this case

Number x = new StringObject(foo); // this is a reference, the reference only 
                                  // contains the address.
                                  // so x is actually '3'

现在，如果我们调用一个方法会发生什么？传递给方法的每个值都将被复制。

void call(int x) {
    x = 4;
}

int i = 15;
call(i);
System.out.println(i);

此输出将为 15。因为 i 的值被复制到调用方法。并且该方法只改变副本，不改变原来的i。

引用也是如此:

void call(StringObject x) {
    x = new StringObject("baz"); // this creates a new address in x!
}

StringObject i = new StringObject("foo"); // remember, i is only an address!
                                          // the address is '3'
                                          // the actual value can be looked up
                                          // in our memory table above
                                          // '3' -> 'foo'

call(i);
System.out.println(i);

此处的输出将是 foo。与基元一样，i 将被复制。不过不用担心，只会复制地址。结果是，调用方法对 i 的副本起作用，即 3。但是原始i的值没有改变。

那么，您的问题与什么有关？看这个方法:

private void insert(Node current, Node temp) {
    if(current == null)
        current = temp;
    else if(temp.element < current.element)
        insert(current.leftChild, temp);
    else if(temp.element >= current.element)
        insert(current.rightChild, temp);
}

很明显，您可以看到，您的代码在 current 引用的副本上运行!您正在更改将在该方法之后丢弃的副本。基本上，第二个代码问题的解决方案是使用第一个代码片段。您可以使用一些包装器对象，例如 C++ 引用，但这很复杂并且容易出错。