Javascript BST recursion.如何删除带有"this"引用的节点类？

Question

我的问题真的很简单。我正在尝试从树中删除一个具有以下结构的节点。如何删除符合条件的节点？基本上，我只想把它设置为null，这样它的父对象就指向null。

这不是实际的代码，但解释了概念。基本上，树中的每个节点都是一个新的BST.

class BST{
constructor(val){
this.val = val;
this.right;
this.left;
}
insert(val){
// find correct node insert in appropriate child
this.left = new BST(val) // or this.right
}
someRecursiveFn(){
if(this.val === 'removeMe') {
// REMOVE NODE
// this = null // illegal
// this.val = null // same problem...I still have the class prototype & it's right & left children
return
}
this.left.someRecursiveFn();
}
}

Answer 1

解决"优雅"问题的一种方法是引入一个特殊的终端对象，该对象将代替null来指定缺少值。

class Zero {
insert(val) {
return new Node(val)
}
remove(val) {
return null
}
}
let zero = () => new Zero()
class Node {
constructor(val) {
this.val = val
this.L = zero()
this.R = zero()
}
insert(val) {
if(val < this.val) this.L = this.L.insert(val)
if(val > this.val) this.R = this.R.insert(val)
return this
}
remove(val) {
if(val === this.val)
return zero()
if(val < this.val) this.L = this.L.remove(val)
if(val > this.val) this.R = this.R.remove(val)
return this
}
}
//
tree = new Node(5)
tree.insert(2)
tree.insert(6)
tree.insert(3)
tree.insert(8)
tree.insert(4)
tree.insert(7)
document.write('<xmp>' + JSON.stringify(tree, 0, 4) + '</xmp>')
tree.remove(4)
document.write('<xmp>' + JSON.stringify(tree, 0, 4) + '</xmp>')
tree.remove(8)
document.write('<xmp>' + JSON.stringify(tree, 0, 4) + '</xmp>')

Answer 2

感谢georg提出这个想法。这真的很简单。只需在递归调用上使用赋值操作。

class BST{
constructor(val){
this.val = val;
this.right;
this.left;
}
insert(val){
// find correct node insert in appropriate child
this.left = new BST(val) // or this.right
}
someRecursiveFn(){
if(this.val === 'removeMe') {
// REMOVE NODE
// this = null // illegal
// this.val = null // same problem...I still have the class prototype & it's right & left children
return null;
}
this.left = this.left.someRecursiveFn();
return this
}
}