Примеры задач
Двоичные деревья
Составить программу вычисления суммы максимального и минимального ключей дерева. Методика решения
Для начала в разделе типов описываем ссылку на звено ss=^zveno, а затем само звено дерева в виде записи, состоящей из трёх частей. Key:integer; - ключ записи; Left:ss; - ссылка на левую вершину; Right:ss; - ссылка на правую вершину. Для реализации данной программы в разделе var описываем следующие переменные:
N – указатель на корень дерева (тип ss); I – вспомогательная переменная типа integer для реализации циклов с параметром; Kl – ключ дерева (integer).
Формирование дерева
Для формирования дерева используем рекурсивную процедуру 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);
Поиск максимального и минимального ключа
Поиск максимального и минимального ключа дерева осуществляется с помощью функций min и max, входными параметрами в которых является ссылка первую вершину (корень) дерева. Минимальным является ключ самого левого элемента дерева, а максимальным – самого правого. Функция min в цикле осуществляет переход по ссылке P^.left, пока эта ссылка не окажется пустой. While p^.left<>nil do
P:=p^.left;
Функции min возвращается ключ звена Р. Это звено будет самым левым, а его ключ минимальным. Аналогично работает функция max, переходя по ссылке p^.right.
Основная часть
В основной части программы формируем дерево. Признаком конца формирования будет введение числа 0. Считываем первый ключ с экрана. Далее в цикле пока считанное число не равно 0, с помощью процедуры vstavka присоединяем к дереву новое звено с соответствующим ключом и считываем следующее число. Выводим полученное дерево на экран. Vivod(u,1); Затем, используя функции min и max находим сумму минимального и максимального ключа и выводим её на экран.
uses crt; type ss=^zveno; zveno=record key:integer; left:ss; right:ss; end; var u:ss; i,kl: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 < p^.key then vstavka(p^.left, k); {процедура вызывает себя для левой вершины} If k > p^.key then vstavka(p^.right, k); { процедура вызывает себя для правой вершины } End;
procedure vivod(var p:ss; h:integer); {процедура для вывода дерева на экран} begin if p<>nil then begin vivod(p^.right,h+5); {вывод правого поддерева} for i:=1 to h do write(' '); writeln(p^.key); vivod(p^.left,h+5); {вывод левого поддерева} end; end;
function min(p:ss):integer; {поиск минимального ключа} begin while p^.left<>nil do p:=p^.left; min:=p^.key; end;
function max(p:ss):integer; {поиск максимального ключа} begin while p^.right<>nil do p:=p^.right; max:=p^.key; end;
begin clrscr; writeln('vvedite kluchi dereva (konec vvoda - 0)'); u:=nil; read(kl); while kl<>0 do {пока не введён 0 считываем ключи и вставляем в дерево} begin vstavka(u,kl); read(kl); end; vivod(u,1); writeln; writeln('Symma minimalnogo i maksimalnogo kluchei: ',min(u)+max(u)); readkey end.