二进制搜索树-迭代插入方法使树为空

Question

我试图为二进制搜索树创建insert方法，但'this.root'仍然是null。

我的逻辑是：

只要current(一开始是this.root(不是null，就继续更新current变量，方法是将其与我们要插入的值进行比较(如果大于或小于(。当current是null时，我们为其分配新的节点：

class Node {
constructor(value){
this.value = value
this.left = null
this.right = null
}
}
class BST {
constructor(){
this.root = null
this.count = 0
}
insert(value){
this.count++
let current = this.root;
while(current){
if(value<current){
current=current.left
}
if(value>current){
current=current.right
}
}
current = new Node(value);
}    
}
let Binst = new BST(10);
Binst.insert(22)
Binst.insert(12)
Binst.insert(4)
console.log(Binst)

Answer 1

存在以下问题：

• 将value与current进行比较是不对的：这就是将数字与对象进行比较。您需要与current.value进行比较

• 在主程序中，您使用参数调用BST构造函数，但该构造函数不需要参数。尽管您可以调整构造函数以接受该参数，但最好是而不是将参数传递给构造函数，并在主程序中额外调用insert。

• current = new Node(value)不会更改树。它只为局部变量指定一个新节点。为了扩展树，需要将新节点分配给现有节点的left或right属性(或BST实例的root属性(。分配给变量永远不会改变对象结构。

• CCD_ 18在用CCD_。同样，分配给current永远不会改变this.root。

• 由于前面的点，您需要提前一次迭代停止循环——当current指向即将获得新子节点时。您还需要单独处理新节点必须成为树的根的情况。

以下只是建议，而不是问题：

• 最好用分号分隔语句。有自动分号插入算法，但如果它有陷阱，你不会是第一个陷入其中的人。最好自己控制。

• 当变量是类(构造函数(时，通常使用首字母大写来命名变量，但对于实例，通常使用小写首字母。所以用binst或bIntst代替Binst。我甚至建议使用一个可读性更强的名称，比如tree。

这是更正后的代码：

class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
this.count = 0;
}
insert(value) {
this.count++;
let current = this.root;
if (!current) {
this.root = new Node(value);
return;
}
while (true) {
if (value < current.value){
if (current.left) {
current = current.left;
} else {
current.left = new Node(value);
return;
}
}
if (value > current.value) {
if (current.right) {
current = current.right;
} else {
current.right = new Node(value);
return;
}
}
}
}
}
let tree = new BST();
tree.insert(10);
tree.insert(22);
tree.insert(12);
tree.insert(4);
console.log(tree);