Получение среднего значения массива для создания сбалансированного BST - PullRequest
Новая
       15

Получение среднего значения массива для создания сбалансированного BST

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

Я пытаюсь найти средний элемент или индекс массива, затем получить середину каждой половины, и так далее ... так скажем у нас есть [0,1,2,3,4,5,6,7,8,9,10,11,12,13]

что я ожидаю 7, 3, 1, 0, 2, 5, 4, 6 ...

Таким образом, когда я добавляю элементы из нового массива, я получаю сбалансированный BST

  • начало: начальный индекс (0)
  • конец: длина - 1
  • nums: список чисел для добавления
  • b: дерево, которое будет вставлено в

Код: 

 public static BST fillBST(BST b, List<Integer> nums, int start, int end) {
    int mid = (start + end) / 2;
    if (start > end)
        b.insertt(nums.get(mid));
    else {
        fillBST(b, nums, start, mid - 1);
        fillBST(b, nums, mid + 1, end);
     }
     return b;
 }

вывод Я получаю список использования [0,31]: 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31

1 Ответ

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

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

Итак, давайте сделаем так: 

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 });
    List<Integer> res =new ArrayList<>();
    fillBST(res, list, 0, list.size() - 1);
    System.out.println(res);
}

public static List<Integer> fillBST(List<Integer> b, List<Integer> nums, int start, int end) {
    int mid = (int)Math.round((1.0 * start + end) / 2);
    b.add(nums.get(mid));
    if (start <= mid - 1)
        fillBST(b, nums, start, mid - 1);
    if (end >= mid + 1)
        fillBST(b, nums, mid + 1, end);
    return b;
}

Это печатает [7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12]

Кроме условия рекурсии, вы можете увидеть другой способ, которым я вычисляю середину. Вычисляя его int mid = (start + end) / 2;, вы не округляете значение, а обрезаете его. Таким образом, средний элемент становится 6 в вашем случае вместо 7.

...