Сортировать массив в BST - PullRequest
Новая
       11

Сортировать массив в BST

0 голосов
/ 01 октября 2018

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

    public static <E> BTree<E> taulukostaPuu(ArrayList<E> L) {

     BTree<E> T = new BTree<E>();
     buildBST(L,T);
     return T;
}       
     private static <E> void buildBST(ArrayList<E> L,  BTree<E> T) {
         int n = L.size();
         if (n == 0)
             return;

         E x = L.get((L.size()/2) + (L.size() % 2));
         T.setRoot(new BTreeNode<E>(x));

     }
   }

Я хотел бы сохранить эту структуру во всем.Любые предложения, как поступить?

Я дошел до этого, но я работаю с элементами, поэтому не знаю, как сделать эту работу.

  public static <E> BTree<E> taulukostaPuu(ArrayList<E> L) {

     BTree<E> T = new BTree<E>();
     buildRecursively(L,L.get(0),L.get(L.size()-1),T);
     return T;
}       

private static <E> void buildRecursively(ArrayList<E> L,E start,E end,BTree<E> T){

if (start.compareTo(end) < 0)
    return;
E x = L.get((L.size()/2) + (L.size() % 2));
int mid = (L.size() / 2);
T.setRoot(new BTreeNode<E>(x)); 
T.setLeftChild(buildRecursively(L, start, mid - 1));
T.setRightChild(buildRecursively(L, mid + 1, end));
}

1 Ответ

0 голосов
/ 01 октября 2018

Вы можете написать метод для рекурсивного построения дерева.

Тип / аргументы, возвращаемые методом, будут выглядеть примерно так: BTreeNode<E> buildRecursively(ArrayList<E> list, int start, int end), и каждый вызов будет делать что-то вроде этого:

  • Рассчитать средний индекс
  • Создать средний узел
  • Построить левое поддерево, указав соответствующие start и end args
  • Построить правое поддерево аналогичнолевый (но, как вы знаете, на другой стороне)
  • Прикрепите левое и правое поддеревья к среднему узлу
  • Верните средний узел

Точныйпорядок не важен.

Тяжелая часть будет избегать ошибок "один за другим" .;)

...