ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 5

Тема: «Сортировка с помощью дерева»

Цель: исследовать и изучить методы сортировки с помощью дерева,  овладеть навыками написания программ для сортировки с помощью бинарного дерева на языке программирования Паскаль.

Ход работы

Теоретические обоснования

Схематичное представление двоичного дерева: имеется набор вершин, соединенных стрелками. Из каждой вершины выходит не более двух стрелок (ветвей), направленных влево - вниз или вправо - вниз. Должна существовать единственная вершина, в которую не входит ни одна стрелка - эта вершина называется корнем дерева. В каждую из оставшихся вершин входит одна стрелка.

Существует множество способов упорядочивания дерева. Рассмотрим один из них :

"Левый" сын имеет ключ меньше, чем ключ " Отца "

"Правый" сын имеет ключ больше, чем ключ " Отца "

Получили бинарное упорядоченное дерево с минимальным числом уровней.

Строго сбалансированное дерево: дерево, в котором левое и правое поддерево имеют уровни, отличающиеся не более, чем на единицу.

Рассмотрим принцип построения дерева при занесении элементов в массив: пусть в первоначально пустой массив заносятся последовательно поступающие элементы : 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86 ; Так как это еще пустое дерево, то ссылки left и right равны nil (left - указатель на левого сына (элемент), right - указатель на правого сына (элемент)). Четвертый из поступающих элементов 87. Так как этот ключ больше ключа 70 (корень), то новая вершина должна размещаться на правой ветви дерева. Чтобы определить ее место, спускаемся по правой стрелке к очередной вершине (с ключом 85), и если поступивший ключ больше 85, то новую вершину делаем правым сыном вершины с ключом 85.

В рассмотренном примере ПРИНЦИП ПОСТРОЕНИЯ ДЕРЕВА имеет следующий вид: если поступает очередной элемент массива, то начиная с корня дерева (в зависимости от сравнения текущего элемента с очередной вершиной) идем влево или вправо от нее до тех пор, пока не найдем подходящую вершину, к которой можно подключить новую вершину с текущим ключом. В зависимости от результата сравнения ключей, новую вершину делаем левой или правой для найденной вершины.

Алгоритм

Для создания дерева необходимо создать в памяти элемент следующего типа:

Описание типа: 

type pelem = ^elem;

elem = record

left : pointer;

right : pointer;

K : integer;

end;

K - элемент массива, V - указатель на созданный элемент.

В процедуре создания дерева бинарного поиска будут использованы следующие указатели:

tree - указатель на корень дерева;

p - рабочий указатель;

q - указатель отстающий на шаг от p;

key - новый элемент массива;

Создание дерева бинарного поиска:

writeln(' Введите элемент массива ');

readln(key);

tree:=maketree(key);

p:=tree;

while not eof do

begin

readln(key);

v:=maketree(key);

while p<>nil do

begin

q:=p;

if key  else p:=right(p);

end;

if p=nil then 

begin

writeln('Это корень');

tree:=v;

end

else  if key  else right(p):=v;

end;

При обходе дерева слева - направо получаем отсортированный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).

Обход дерева слева - направо

procedure InTree(tree);

begin

if Tree = nil then write('Дерево пусто')

else 

with Tree^ do

begin

if left<>nil then InTree(left);

if right<>nil then InTree(right); 

end;

end;

Решить самостоятельно:

На заводе выпустили детали со следующими серийными номерами : 45, 56, 13, 75, 14, 18, 43, 11, 52, 12, 10, 36, 47, 9. Детали с четными номерами поступают на склад №1, а с нечетными на слад №2. Требуется отсортировать детали на складе №1.