在Java中使用类内的方法修改类变量

Question

下面的代码在二叉搜索树中插入新节点。

当我在驱动程序函数中创建 BinarySearchTree 类的对象并首次使用其 insert 函数时，root 会更新。这也应该是这样，因为我们将 root 设置为 newNode。

但是，如果我们此后使用同一对象的插入函数，则root不再是null，并且在设置为等于root后，仅对函数中的currentNode变量进行处理。对象的变量 root 根本没有被更改或处理。

那么为什么 insert 函数在第一次使用后能够通过添加节点作为对象的 root 变量的子节点来构建 BST？

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;
            }
        }
    }

Answer 1

它可能有助于可视化插入第二个值时会发生什么——因此在一棵当前只有一个节点（即根）的树中。假设我们有这个驱动程序代码：

BinarySearchTree tree = new BinarySearchTree();
tree.insert(5);
tree.insert(2);

在第二次

insert

执行开始时，我们有这样的情况：

tree
  ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │
│ root: ──────────────►│ left: null  │
└──────────────────┘   │ right: null │ 
                       └─────────────┘

首先，创建

newNode

并为其赋予一个值——它与树还没有依赖关系——并且为

currentNode

分配与root相同的

引用

：

tree                    currentNode       newNode
  ↓                       ↓                 ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │   │ val: 2      │
│ root: ──────────────►│ left: null  │   │ left: null  │
└──────────────────┘   │ right: null │   │ right: null │
                       └─────────────┘   └─────────────┘

请注意

root

和

currentNode

如何引用相同的

BSTNode

实例，而且这些变量（

root

是一个字段）具有自己的引用内存。

在循环的第一次迭代中，该语句将在第一个

if

块中执行：

currentNode.left = newNode;

这会改变

currentNode

和

root

引用的单个节点。我们得到：

tree                    currentNode       newNode
  ↓                       ↓                 ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │   │ val: 2      │
│ root: ──────────────►│ left: ────────► │ left: null  │
└──────────────────┘   │ right: null │   │ right: null │
                       └─────────────┘   └─────────────┘

在下一条语句中，

currentNode

将被重新分配一个新的引用——在分配给

left

字段的引用之后，所以我们得到：

tree                                  currentNode  newNode
  ↓                                        ↓         ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │   │ val: 2      │
│ root: ──────────────►│ left: ────────► │ left: null  │
└──────────────────┘   │ right: null │   │ right: null │
                       └─────────────┘   └─────────────┘

请注意，对变量（而不是字段）的赋值永远不会改变对象。它只会影响该变量本身。

希望这能澄清这一点。