下面的代码在二叉搜索树中插入新节点。
当我在驱动程序函数中创建 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;
}
}
}
它可能有助于可视化插入第二个值时会发生什么——因此在一棵当前只有一个节点(即根)的树中。假设我们有这个驱动程序代码:
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 │
└─────────────┘ └─────────────┘
请注意,对变量(而不是字段)的赋值永远不会改变对象。它只会影响该变量本身。
希望这能澄清这一点。