Бинарное дерево (Java)

[fswl]

Здравствуйте,

помогите пожалуйста реализовать алгоритм формирования бинарного дерева из массива.

Правило формирования следующие, корнем дерева является элемент стоящий посередине массива. Если количество элементов четное, то берется элемент следующий после середины массива. К примеру у массива [1,2,3,4,5] корнем будет 3, у массива [1,2,3,4] корнем так же будет 3.

после того как мы нашли корень, наш массив получается делится на два "подмассива", корни соответствующих поддеревьев ищутся аналогично корню искомого дерева.

Элементы которые стоят в массиве слева, в дереве так же располагаются слева, аналогично с элементами стоящими справа от корня.

Пример дерева



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


Необходимо описать дерево в виде массива узлов, где у каждого узла указывается его значение и ссылки на левый и правый потомок

Спасибо.

[p51x]

А что не получается? Все ж описано...

[fswl]

Сообщение от p51x

А что не получается? Все ж описано...

не получается придумать как этот алгоритм "технически реализовать".

Пока схема в голове примерно такая.

Пишем функцию getmiddle которая будет возвращать индекс узла, на вход функции подается массив.

далее необходимо придумать цикл в котором сначала находим первый узел.
Потом разбиваем массив на 2 подмассива и находим их центры. В итоге у нас узел и его правый и левый потомок.

Вопрос, какое придумать условие цикла?
Как разбивать массив на подмассивы? через промежуточные переменные?
и т.д.

П.С. Сорри за возможно глупые вопросы, но в программировании я совсем новичок

[p51x]

Есть "магическое слово" рекурсия... Например, берете ноде функция(массив). В ней вы привязываете потомков и возвращаете узел для середины.