javascript - Javascript BST 递归。如何使用“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();
  }
}

标签： javascriptbinary-search-tree

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>')