несортированный массив в двоичное дерево поиска

Поэтому я уверен, что это очень просто, и я просто упускаю его, но мне нужно сделать несортированный массив для BST. У меня есть массив int [] data = {50, 30, 60, 10, 80, 55, 40}; и мне нужно преобразовать его в несбалансированный BST с первым числом в качестве корня, независимо от того, на что я его изменяю, а остальные числа следуют правилам левого и правого. У меня есть этот код, который работает для этого массива, но не в том случае, если я изменил число на что-то не посередине.

 public Node arraytoBinary(int [] array, int start, int end) {
    if (start > end){
        return null;
    }
    int mid = (start + end) / 2;
    Node node = new Node(array[mid]);
   node.left = arraytoBinary(array, start, mid - 1);
   node.right = arraytoBinary(array, mid + 1, end);

    return node;
}

java arrays binary-search-tree
person Alexis Flanigan    schedule 10.05.2018    source источник
comment
Вы пытаетесь сделать сбалансированный BST? Если это так, этот подход требует, чтобы массив был отсортирован. Если нет, то почему бы не выполнить итерацию по массиву и последовательно добавить в дерево?   -  person kingkupps    schedule 10.05.2018
comment
@kingkupps Это не обязательно должен быть отсортированный массив, если вы вставляете элементы массива в bst, но массив должен быть отсортирован для выполнения бинарного поиска по массив. На самом деле, если он упорядочен и вы вставите их по порядку, bst превратится в список. Сбалансированный массив также не требует отсортированных массивов; балансировка решает проблему, о которой я упоминал выше.   -  person ChiefTwoPencils    schedule 10.05.2018
comment
У меня есть этот код, который работает для этого массива, но не в том случае, если я изменил число на что-то не посередине. Можете ли вы пояснить это на примере, пожалуйста?   -  person ChiefTwoPencils    schedule 10.05.2018
comment
@ChiefTwoPencils Верно, но для того, чтобы этот код создавал сбалансированный BST, массив должен быть отсортирован. В противном случае сбалансированность полученного дерева не гарантируется. Что вы подразумеваете под сбалансированным массивом?   -  person kingkupps    schedule 10.05.2018
comment
@king, согласно тому, что они написали, они переходят от массива к не-сбалансированному BST, и, извините, я не хотел сказать массив, я имел в виду дерево. Я полагаю, что меня заводит то, что я не видел, чтобы многие пытались создать сбалансированное дерево, гарантируя, что исходный массив находится в состоянии, которое облегчает это; кажется, что это побеждает суть; ничто не мешает нам реализовать деревья с массивами, поэтому я немного запутался.   -  person ChiefTwoPencils    schedule 10.05.2018
comment
@ChiefTwoPencils Ааа понял, я неправильно понял вопрос.   -  person kingkupps    schedule 10.05.2018
comment
@ChiefTwoPencils, поэтому, если бы я изменил число 50, которое является первым числом в массиве, на 80, вместо этого у меня не было бы bst, который брал первое число в качестве корня и создавал bst на основе этого числа. Мне не нужен сбалансированный бст   -  person Alexis Flanigan    schedule 10.05.2018

Ответы (1)


arrow_upward
3
arrow_downward

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

Мой подход к этому состоял бы в том, чтобы определить метод insert(Node node, int value) и позволить arrayToBinary просто перебирать массив и вызывать insert. Это даст вам чистое дерево с минимальным интерфейсом. Кроме того, он основан на определении и логике вставки BST, поэтому он должен быть интуитивно понятным.

(псевдо для вашего удовольствия)
Вставка

Node insert(node, value)
    if node is null
        // Create a leaf.
        // It might be the root...
        return new Node(value)

    // It's occupied, see which way to
    // go based on it's value

    // right? ...
    if value > node.value
        node.right = insert(node.right, value)

    // or left?
    else if value < node.value
        node.left = insert(node.left, value)

    // Code is not handling dups.
    return node

Конверсия

Node arrayToBinary(array, root)
    for e in array
        root = insert(root, e)
    return root

Это сохранит первый элемент в качестве корня и вставит остальную часть массива, как и ожидалось.

person ChiefTwoPencils    schedule 10.05.2018
comment
это то, что вы имеете в виду? - person Alexis Flanigan; 11.05.2018
comment
частный узел insertNode (узел currentParent, узел newNode) { if (currentParent == null) { return newNode; } else if (newNode.value › currentParent.value) { currentParent.right = insertNode(currentParent.right, newNode); } else if (newNode.value ‹ currentParent.value) { currentParent.left = insertNode(currentParent.left, newNode); } вернуть текущий родитель; }' - person Alexis Flanigan; 11.05.2018
comment
@Alexisdiaz, это выглядит правильно, но это трудно читать. Вы попробовали? - person ChiefTwoPencils; 11.05.2018
comment
мне просто нужно построить второй, который вы упомянули, да, я пытался сделать так, чтобы он читался как код, но по какой-то причине он не будет отступать для меня. - person Alexis Flanigan; 11.05.2018
comment
Для arraytoBinary что должно быть e? - person Alexis Flanigan; 11.05.2018
comment
@Alexisdiaz, вы не сможете сделать это в комментарии. e - это просто текущий элемент в вашем массиве. В Java вы должны либо использовать расширенный цикл for (for(int e : array), либо индексировать его с помощью традиционного цикла for (array[i], где i >=0 и < array.length). Вы должны иметь возможность соединить это вместе, запустить оба и увидеть, что это работает. Я могу чуть позже добавьте замените его на исполняемый код Python. - person ChiefTwoPencils; 11.05.2018
comment
Node arraytoBinary(int [] array, Node root){ for(int i= 0; i ‹ array.length; i++){ root = insertNode(root, i);} return root; - person Alexis Flanigan; 11.05.2018
comment
Это не работает и дало мне 123456789 в качестве моих номеров, но я почти уверен, что мне не хватает чего-то простого - person Alexis Flanigan; 11.05.2018
comment
Да, вы вставляете не i, а array[i]. @Alexisdiaz Если вы отлаживаете это, вы увидите, что ваше дерево - это просто список, который всегда идет правильно.\ - person ChiefTwoPencils; 11.05.2018