我从 javascript 中的数据结构和算法中找到了这个算法。对于插入方法,有两个对根的引用(当前和父)。我的问题是,为什么我不能将当前和父级都更改为 this.root?它们都指向 this.root。但是,当我这样做时,代码无法正常工作
'use strict';
var BST = function() {
this.root = null;
//embed _Node inside BST so it comes with when BST is created
this._Node = function(data, left, right) {
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
};
this._Node.prototype.show = function() {
return this.data;
};
this._Node.prototype.showCount = function() {
return this.count;
}
};
BST.prototype.insert = function(data) {
//use this data for a new node
var n = new this._Node(data, null, null);
//if root is null, put this new node and its data into root
if (this.root === null) {
this.root = n;
}
else {
//find a child position for this node
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current === null) {
parent.left = n;
break;
}
}
else {
current = current.right;
if (current === null) {
parent.right = n;
break;
}
}
}
}
};
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
最佳答案
current
在整个算法中没有引用 this.root
。
它被初始化为 this.root
,但随后它很快被重新分配给 current = current.left;
或 current = current.right;
。从那一刻起,current
不再是 this.root
。它是 this.root.left
或 this.root.right
。
在 while 循环的下一次迭代中,它将再次被重新分配,但它永远不会再次成为 this.root
,因为它总是被重新分配给 current< 的子节点
。
parent
类似,仅在第一次迭代时为 this.root
。在每个后续迭代中,它由 parent = current;
重新分配,并且由于 current 不再是
this.root,
parent不会要么是
this.root。
关于javascript - BST 在 javascript 中使用引用对象,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40613885/