Итеративный алгоритм формирования бинарного дерева

1. Пока в последовательности неповторяющихся значений есть элементы, читать и включать их в дерево в соответствии с п.2 или п.3.

2. Если БД пустое, то создать корень, записать в него значение.

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

Применив рассмотренные алгоритмы к последовательности целых чисел 20, 15, 23, 10, 5, 12, 30, 18, 44, 25 получим БД на рис.27.

Рис.27. БД, построенное по итеративному алгоритму

Если последовательность будет упорядоченной, то БД вырождается в последовательность.

Пусть необходимо построить БД для последовательности из n элементов, имеющее минимальную высоту. Тогда все уровни дерева, кроме, может быть, последнего, будут заполнены. Для того чтобы построить такое БД, нужно элементы последовательности распределять поровну между левым и правым поддеревом. Такое распределение достаточно просто можно выполнить для упорядоченной по возрастанию последовательности.