бинарное дерево, как удалить узел (уровень новичка) - PullRequest
Новая
       4

бинарное дерево, как удалить узел (уровень новичка)

0 голосов
/ 28 января 2020

Я работал над классом дерева двоичного поиска в Javascript и добавляю функцию удаления. Это кажется очень простым (за исключением случаев, когда у него есть 2 дочерних элемента), но я хочу наиболее элегантное из возможных решений, которое означает, что нужно работать с удаленным узлом, а не с родителем. Так, например, скажем, я хочу удалить узел без дочерних элементов, я бы хотел установить узел на нуль. Я могу сделать это при работе с родителем (он же node.left = null), но когда я пытаюсь "node = null", я только устанавливаю переменную в null и не влияю на мое дерево.

Я нашел много учебники, где они используют код, подобный этому - 

if (root.left === null && root.right === null) {
         root = null; 
         return root;
      }

, но когда я делаю это, я только устанавливаю переменную в null, не влияя на мой BST. В любом случае, из того, что я могу сказать, в моем коде есть все, что есть в любом из этих руководств, и все же, очевидно, я что-то упускаю. Вот мой (Изменить) обновленный код 

        remove(val){
                var runner = this.root
                runner = this.find(val, runner) 
                return this 
            }

        find(val, runner){
                if (runner){
                    if (val == runner.value){
                        console.log("We got it", runner)
                        return this.delete(val, runner)
                    }
                    if (val < runner.value)
                        return this.find(val, runner.left)
                    if (val > runner.value) 
                        return this.find(val, runner.right)
                }
                console.log("No one here Bob")
                return false
        }
        delete(val, runner){
                console.log("Sunshine", runner)
                if (runner.left == null && runner.right == null){
                    runner = null
                    console.log("SUcesS")
                    return this.runner
                }
                else if (runner.left == null){
                    runner == runner.right
                    console.log("sucesS")                   
                    return this.runner
                }
                else if (runner.right == null){
                    runner = runner.left
                    console.log("sucess")
                    return this.runner
                }
                else {
                    var node = this.findMin(runner.right)
                    node.left = runner.left
                    node.right = runner.right
                    runner = node
                    console.log("it is finished", node)
                    return this.delete(val, node.right) 
                }   

            }

. Он идет во все нужные места и работает точно так же, как и должен, за исключением того, что никаких изменений не производится. Единственное различие, которое я видел между моим и множеством учебных пособий, заключается в том, что все они возвращают узел, а не дерево, поэтому я попробовал это, не понимая, почему это будет иметь значение, но без изменений.

...