Javascript BST рекурсия.Как удалить класс узла с ссылкой "this"? - PullRequest
Новая
       7

Javascript BST рекурсия.Как удалить класс узла с ссылкой "this"?

0 голосов
/ 14 декабря 2018

Моя проблема действительно проста.Я пытаюсь удалить узел из моего дерева со следующей структурой.Как я могу удалить узел, который соответствует моему условию?По сути, я просто хочу установить для него значение 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();
  }
}

Ответы [ 2 ]

0 голосов
/ 14 декабря 2018

Спасибо Георгу за то, что пришли с идеей.Это довольно просто на самом деле.Просто используйте операцию присваивания при рекурсивном вызове. 

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
  }
}
0 голосов
/ 14 декабря 2018

Один из способов решить это «элегантно» - ввести специальный конечный объект, который будет использоваться вместо 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>')
...