Примеры задач

Двоичные деревья

Составить программу вывода всех листьев дерева
Методика решения

Для начала в разделе типов описываем ссылку на звено ss=^zveno, а затем само звено дерева в виде записи, состоящей из трёх частей.
key:integer; - ключ записи;
left:ss; - ссылка на левую вершину;
right:ss; - ссылка на правую вершину.
Для реализации данной программы в разделе var описываем следующие переменные:
u – указатель на корень дерева (тип ss);
i – вспомогательная переменная типа integer для реализации циклов с параметром;
kl – ключ дерева (integer).
l – число, стоящее в информационной части листа дерева.

Формирование дерева

Для формирования дерева используем рекурсивную процедуру vstavka. Входными параметрами в этой процедуре будет ссылка на вершину дерева P и ключ вставляемого элемента k.
Сначала дерево пусто и ссылка Р = nil. В этом случае процедура создаёт новое звено с адресом P,
New(p);
вносит туда ключ К, ссылкам на соседние вершины присваивается nil.
P^.left:=nil; P^.right:=nil;

Если же дерево не пустое, то процедура вызывает сама себя для одной из соседних вершин (если ключ К меньше ключа текущей вершины, то для левой, если больше – для правой).
If k<p^.key then vstavka(p^.left,k);
If k>p^.key then vstavka(p^.right,k);
То есть, для размещения элемента дерева, в зависимости от сравнения ключей, идём влево или вправо, и продолжаем это перемещение до тех пор пока не найдём ту вершину, к которой можно прикрепить новую.
Например, сформировано следующее дерево:

и к нему необходимо присоединить элемент с ключом 7.
Вызываем процедуру vstavka. В качестве входного параметра Р пишется ссылка на корень дерева.

Так как 7<8 процедура вызывает сама себя для левой вершины.
vstavka(p^.left,k);

Так как 7>5 процедура вызывает сама себя для правой вершины.

Эта вершина пуста. Процедура создаёт новое звено New(p), вносит туда ключ 7, ссылкам на соседние вершины присваивается nil.

Вывод элементов дерева на экран

Для вывода ключей дерева на экран используем рекурсивную процедуру vivod. Входными параметрами в ней будет ссылка на вершину – Р и отступ от левого края экрана – h.
Для каждой вершины дерева будет выводиться сначала её правое поддерево, затем сама вершина и её левое поддерево.
Если ссылка на вершину не пустая, то процедура вызывает сама себя для вывода правого поддерева с отступом от края, увеличенным на 5.
Vivod(p^.right,h+5);
Затем от края делается отступ h и выводится ключ самой вершины Р.
For i:=1 to h do write(‘ ‘);
Writeln(p^.key);
После этого процедура вызывает сама себя для вывода левого поддерева.
Vivod(p^.left,h+5);

Рекурсивная процедура для нахождения листьев дерева list

Здесь будет использоваться входной параметр - ссылка на вершину – p. Проверяем, если ссылка на правое и на левое звено пусты, то это лист дерева. Мы выводим его. Иначе, если ссылка на правое поддерево не пуста, то вызываем для него процедуру list. Если ссылка на левое поддерево не пуста, то вызываем процедуру list для левого поддерева.
Раздел операторов

В основной части программы формируем дерево. Признаком конца формирования будет введение числа 0.
Считываем первый ключ с экрана k1. Далее в цикле пока считанное число не равно 0, с помощью процедуры vstavka присоединяем к дереву новое звено с соответствующим ключом и считываем следующее число.
Выводим полученное дерево на экран. print(u,0);
Затем, с помощью процедуры list находим все листья дерева и выводим их на экран.

Листинг программы

Uses crt;
Type ss=^zveno;
zveno=record
key:integer;
left,right:ss;
end;
Var p,u:ss; i,k1,l:integer;

Procedure vstavka(var p:ss; k:integer);
begin
If p=nil then
begin
new(p); p^.key:=k; p^.left:=nil; p^.right:=nil;
end else
If k
If k>p^.key then vstavka(p^.right,k);
end;

Procedure print(var p:ss; h:integer);
begin
If p<>nil then
begin
print(p^.right,h+3);
for i:=1 to h do write(' '); writeln(p^.key); print(p^.left,h+3);
end;
end;

Procedure list (var p:ss);
begin
If (p^.left=nil) and (p^.right=nil) then
Write(p^.key:2) else
begin
If p^.right<>nil then list(p^.right);
If p^.left<>nil then list(p^.left);
end;
end;

Begin Clrscr;
Writeln('Введите ключи дерева, конец ввода 0');
u:=nil;
read(k1);
While k1<>0 do
begin
vstavka(u,k1); read(k1);
end;
Writeln('Полученное дерево:');
print(u,0);
writeln;
Writeln('Листья данного дерева:');
list(u);
Readkey;
End.

Запустить программу

Назад