несортированный массив в дерево двоичного поиска - PullRequest
Новая
       6

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

0 голосов
/ 10 мая 2018

Так что я уверен, что это очень просто, и я просто скучаю по нему, но мне нужно сделать несортированный массив в 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;
}

1 Ответ

0 голосов
/ 10 мая 2018

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

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

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

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

Conversion 

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

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

...