Идеально сбалансированное дерево. Задание

Алгоритм построения идеально сбалансированного дерева
Взять одну вершину в качестве корня.
Построить тем же способом левое поддерево с nl = n /2 вершинами.
Построить тем же способом правое поддерево с nr = n-nl-1 вершинами.
Заполнение идеально сбалансированного дерева осуществляется согласно прямого метода прохождения.

Пример оформления домашней работы

РЕКУРСИВНЫЕ МЕТОДЫ ПРОХОЖДЕНИЯ ДЕРЕВЬЕВ
Прямой метод прохождения определяется посещением узла в первую очередь и последующим прохождением сначала левого, а потом правого поддеревьев.
Порядок операций дает так называемое NLR (node, left, right,) сканирование.
Посещение узла (N).
Прохождение левого поддерева (L).
Прохождение правого поддерева (R).
Cначала осуществлялось прохождение по левому поддереву, а уже потом по правому. Cуществует алгоритм, который выбирает сначала правое поддерево и потом левое.
Порядок операций дает так называемое NRL сканирование.
Порядок операций при симметричном методе следующий:
Прохождение левого поддерева (L).
Посещение узла (N).
Прохождение правого поддерева (R).
Назовем такое прохождение LNR. Второй алгоритм – RNL прохождение.
Порядок операций при обратном методе следующий:
Прохождение левого поддерева (L).
Прохождение правого поддерева (R).
Посещение узла (N).
Назовем такое прохождение LRN . Второй алгоритм – RLN прохождение.

Варианты прохождения дерева
NLR: 15, 19,21,13,11,65,70,81, 10,44,55,18
NRL: 15, 81,55, 18,10, 44, 19, 65,70, 21,11, 13
LNR: 13,21,11,19,70,65, 15, 44,10,81,18,55
RNL: 55,18,81,10,44, 15, 65,70,19,11,21,13
LRN: 13,11,21,70,65,19,44,10,18,55,81, 15
RLN: 18,55,44,10,81,70,65,11,13,21,19, 15

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

Пример построения поискового дерева
15 19 21 13 11 65 70 81 10 44 55 18
15
13 19
11 18 21
10 65
44 70
55 81

Пример поискового дерева