java - 为什么我的 Java Binary Search Tree 类在我告诉它时实际上没有删除节点？

Question

我正在用 Java 构建二叉搜索树以更好地理解它们的工作原理，并且我正在研究删除具有特定值的节点的函数。

我基本上遍历树，直到找到具有正确值的节点，然后根据它有多少个 child 采取相应的行动。

如果它没有 child ，我将其设置为空。如果它有一个，我将自己设置为等于 child 。如果它有两个，我遍历左边的树，跟随左边直到到达左边，然后删除它并将我所在的节点的值设置为已删除节点的值。

class BTree {
    public int data;
    public BTree leftTree;
    public BTree rightTree;

    public BTree(int data) {
        this.data = data;
    }

    public BTree(int data, BTree leftTree, BTree rightTree) {
        this.data = data;
        this.leftTree = leftTree;
        this.rightTree = rightTree;
    }

    public void insert(int data) {
        if (data < this.data) {
            if (this.leftTree == null) {
                BTree newTree = new BTree(data);
                this.leftTree = newTree;
            } else {
                insert(this.leftTree, data);
            }
        } else {
            if (this.rightTree == null) {
                BTree newTree = new BTree(data);
                this.rightTree = newTree;
            } else {
                insert(this.rightTree, data);
            }
        }
    }

    private void insert(BTree tree, int data) {
        if (tree.data == data) {
            return;
        }

        if (data < tree.data) {
            if (tree.leftTree == null) {
                BTree newTree = new BTree(data);
                tree.leftTree = newTree;
            } else {
                insert(tree.leftTree, data);
            }
        } else {
            if (tree.rightTree == null) {
                BTree newTree = new BTree(data);
                tree.rightTree = newTree;
            } else {
                insert(tree.rightTree, data);
            }
        }
    }

    public void inorderTraversal(BTree tree) {
        if (tree.leftTree != null) {
            inorderTraversal(tree.leftTree);
        }

        System.out.print(tree.data + ", ");

        if (tree.rightTree != null) {
            inorderTraversal(tree.rightTree);
        }
    }

    public void remove(int data, BTree tree) {
        if (tree == null) {
            return;
        }

        if (data == tree.data) {
            if (tree.leftTree != null && tree.rightTree != null) {
                int minimumValue = getMinimumValue(tree.leftTree);
                remove(minimumValue, tree);

                tree.data = minimumValue;
            } else if (tree.leftTree != null) {
                tree = tree.leftTree;
            } else if (tree.rightTree != null) {
                tree = tree.rightTree;
            } else {
                tree = null;
            }
        } else if (data < tree.data) {
            remove(data, tree.leftTree);
        } else {
            remove(data, tree.rightTree);
        }
    }

    public int getMinimumValue(BTree tree) {
        if (tree.leftTree == null) {
            return tree.data;
        } else {
            return getMinimumValue(tree.leftTree);
        }
    }

    public static void main(String[] args) {
        BTree myTree = new BTree(5);
        myTree.insert(6);
        myTree.insert(12);
        myTree.insert(4);
        myTree.insert(3);
        myTree.insert(6);
        myTree.insert(15);
        myTree.insert(1);
        myTree.insert(9);
        myTree.insert(-2);

        myTree.remove(3, myTree);

        myTree.inorderTraversal(myTree);
    }
}

尽管如此，3仍然出现在中序遍历中。我做错了什么？

Answer 1

以这一行为例:

tree = tree.leftTree;

您正在尝试通过为 tree 分配新值来重写树。

但是tree是一个方法参数。通过在方法内部重新分配它，您不会在方法调用点重新分配方法参数:方法参数始终按值传递。这意味着引用类型参数按值传递，作为引用的值。在方法中对该值(引用)的更改对原始调用站点没有影响。对该引用类型的内容的更改将产生影响。

值得引用 The Java Tutorials > Passing Information to a Method or a Constructor > Passing Reference Data Type Arguments

Reference data type parameters, such as objects, are also passed into methods by value. This means that when the method returns, the passed-in reference still references the same object as before. However, the values of the object's fields can be changed in the method

看这个简单的例子:

public static void main(String[] args) {
  A a1 = new A();
  System.out.println("before the method                 : " + a1);
  reassignFail(a1);
  System.out.println("after the method                  : " + a1);
}
static void reassignFail(A a1) {
  A a2 = new A();
  System.out.println("inside the method a2              : " + a2);
  a1 = a2;
  System.out.println("inside the method for parameter a1: " + a1);
}
static class A{
  int id;
  private static int iid;
  public A() { id = ++iid; }
  public String toString() { return "this is instance " + id; }
}

这打印:

before the method                 : this is instance 1
inside the method a2              : this is instance 2
inside the method for parameter a1: this is instance 2
after the method                  : this is instance 1

所以你的重新分配对树结构没有影响。