我正在尝试删除二进制搜索树中的根节点。
bst.remove(1(给出了正确的输出，但它不会改变树本身。
因此，如果在调用bst.remove(1(之后检查bst，则输出是不同的。为什么会这样？
如果我运行bst=bst.left||bst.right;，我会得到正确的输出，这让我相信我的函数并没有改变原来的树。
remove(key) {
return this.removeImpl(key, this);
}
removeImpl(key, node){
if (node != null) {
if (key < node.value) {
// Key might be in the left subtree.
node.left = this.removeImpl(key, node.left);
} else if (key > node.value) {
node.right = this.removeImpl(key, node.right);
} else {
// Node found.
// Let's see if it has two children.
if (node.left && node.right) {
// Replace current node with
// predecessor data
node.value = this.minimum(node.right);
node.right = this.removeImpl(node.value, node.right);
} else {
// Only 1 child.
// Let's return the child that's valid.
node = node.left || node.right; //node to be removed becomes it's right or left child
}
}
}
return node;
}
var bst=new BST(1);
bst.insert(2);
bst.insert(3);
bst.insert(4);
bst.remove(1);
bst.remove(1)给出了正确的输出，但它不会改变树本身。
这是有意的。你称之为"；树本身"；，实际上是根节点。您的代码没有以单独类的形式存在树的概念——树(仅(由根节点暗示。由于节点的移除不是被移除节点的突变，而是其他引用的突变，并且对该根节点的唯一引用是bst变量，因此需要对bst进行赋值。在移除树的最后一个节点的极端情况下，您会期望bst变成null，因此再次需要对bst进行赋值。由于此bst变量不是某个类实例的属性，因此需要管理此赋值"；你自己"；在主代码中。
这里有另一种分析这种情况的方法：
removeImpl函数依赖调用方将返回的节点附加在正确的位置。您可以在removeImpl进行的每个递归调用中看到这种情况。。。例如：
node.left = this.removeImpl(key, node.left);
node.right = this.removeImpl(key, node.right);
所以我们可以说调用者使树发生了变异。如果removeImpl本身是(递归调用的(调用者，则它本身执行突变，但removeImpl的初始调用者(即remove(也执行突变：
return this.removeImpl(key, this);
在这里，我们看到对返回节点执行某些操作的责任级联到remove的调用方。调用方应该应用这个原则，而这正是您当前代码所缺乏的。我们在这里看到remove的调用：
bst.remove(1)
但该调用会忽略返回的节点。这不是remove应该被调用的方式。应该这样称呼：
bst = bst.remove(1)
对于该更改，代码始终使用remove和removeImpl方法返回的节点来捕获更改。
两级制
以上内容可能看起来过于冗长。如果您希望bst.remove(1)在不需要为bst分配任何东西的情况下完成这项工作，那么您应该考虑两类系统，而不是当前的一类实现。
然后，您可以将当前的BST类重命名为Node，并创建第二个类，即容器类，可以命名为BST。当您将BST重命名为Node时，不要忘记在创建节点时也使用该名称(就像在insert方法中一样，new BST应该变成new Node(。
然后添加：
class BST {
constructor() {
self.root = null; // Now the root is a property, not a global variable
}
insert(key) {
if (self.root == null) self.root = new Node(key);
else self.root.insert(key);
}
remove(key) {
if (self.root) {
// Now we mutate the container instance:
self.root = self.root.remove(key);
}
}
}
var bst = new BST();
for (let value of [1, 2, 3, 4]) bst.insert(value);
bst.remove(1);