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

问题描述 投票:0回答:1

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

当我在驱动程序函数中创建 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;
            }
        }
    }
reference insert binary-search-tree pass-by-reference
1个回答
0
投票

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

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 │
                       └─────────────┘   └─────────────┘

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

希望这能澄清这一点。

© www.soinside.com 2019 - 2024. All rights reserved.