Бинарные деревья

Бинарные деревья являются наиболее используемой разновидностью деревьев.

Согласно представлению деревьев в памяти ЭВМ каждый элемент будет записью, содержащей 4 поля. Значения этих полей будут соответственно ключ записи, ссылка на элемент влево-вниз, на элемент вправо-вниз и на текст записи.

При построении необходимо помнить, что левый сын имеет ключ меньший, чем у отца, а значение ключа правого сына больше значения ключа отца. Например, построим бинарное дерево из следующих элементов: 50, 46, 61, 48, 29, 55, 79. Оно имеет следующий вид:

Получили упорядоченное бинарное дерево с одинаковым числом уровней в левом и правом поддеревьях. Это - идеально сбалансированное дерево, то есть дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не более чем на единицу.

Для создания бинарного дерева надо создавать в памяти элементы типа (рис. 4.5):

Операция V= MakeTree(Key, Rec) - создает элемент (узел дерева) с двумя указателями и двумя полями (ключевым и информационным).

Вид процедуры MakeTree:

p = getnode

r (p) = rec

k (p) = key

v = p

left (v)= nil

right (v) = nil

return

Сведение m-арного дерева к бинарному

Неформальный алгоритм:

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

2.Соединяется горизонтальными линиями все сыновья одного родителя;

З. Старшим сыном в любом узле полученной структуры будет узел, находящийся под данным узлом (если он есть).

Последовательность действий алгоритма приведена на рис. 4.6.