Метод добавления бинарного дерева поиска, не сортирующий каждый вход - JavaScript - PullRequest
Новая
       15

Метод добавления бинарного дерева поиска, не сортирующий каждый вход - JavaScript

0 голосов
/ 22 сентября 2018

Я работаю над деревом двоичного поиска и у меня возникла проблема при добавлении значений в дерево.Когда я добавляю значения (числа) по порядку (по убыванию или по возрастанию), они добавляются в правильных позициях, но если я добавлю значение, которое должно идти где-то между значениями, которые уже есть в дереве, они не сортируются.Вы можете видеть, что на рисунке число [3] добавлено после 1, но оно должно быть между [4] и [1]. Поэтому вопрос в том, что именно я делаю неправильно и как это исправить

Я добавляю свой код для функции добавления под картинкой

enter image description here

Объект Node 

function Node(data){
this.data=data;
this.left=null;
this.right=null;}

function BinarySearchTree(){
this.root = null;
var current=null;
var newNode=null;

this.add = function(data){
    var root = this.root;
        if(!root){
            this.root= new Node(data);
            return;
        }else{
            if(this.ifExists(data)){
            }else{
                current=root;
                newNode= new Node(data);

                while(current){
                    if(data<current.data){
                        if(!current.left){
                                current.left=newNode;
                            break;
                        }else{
                                current= current.left;
                             }
                    }else{
                        if(!current.right){
                                current.right=newNode;
                            break;
                        }else{
                                current=current.right;
                            }
                        }
                    }
                }
            }
        }
}
this.ifExists=function(data){
         var current = this.root;
//       console.log(current);
         while(current){
             if(data==current.data){
                 return true;
             }
             current = data < current.value ? current.left : current.right;
         }
         return false;
     }
}

Как я вызываюфункция добавления 

var bst= new BinarySearchTree();
bst.add(7);
bst.add(8);
bst.add(4);
bst.add(1);
bst.add(15);
bst.add(67);
bst.add(9);
bst.add(3);
console.log(bst);

выход console.log (bst);

enter image description here

1 Ответ

0 голосов
/ 22 сентября 2018

3 должно быть справа, потому что оно больше 1.В вашем выводе это правда.На твоей картинке ты допустил ошибку там.

Кроме того, с твоим деревом все в порядке.Тот факт, что 1 меньше 3, является правильным, но BST гарантирует только то, что обход дерева по порядку дает отсортированный список данных деревьев, а не то, что каждое меньшее значение в дереве ниже, чем большее значение.Если вы выполните обход дерева заказов, ваш BST даст вам 1, 3, 4, 7, 8, 15

Если вы не знаете, как выполнить обход дерева заказов, посмотрите на это: BST In-Order-Walk from Википедия

Просто отметьте все данные, когда точка в нижней части узла не коснулась.

...