БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра программного обеспечения информационных технологий
Факультет ФКСиС Специальность ПОИТ
Индивидуальная практическая работа №2
по дисциплине «Дискретная математика»
тема: «Графы»
Вариант 4
Выполнил студент: Бордон Е.С. группа 991051 Зачетная книжка № 99105004
Минск 2020
Задание:
Написать программу, которая решает предложенную задачу.
4. Вывести номера вершин, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве.
Программа написана на языке pascal в программной среде Lazarus.
Рис 1. Общая схема работы программы
Процедура добавления вершин в дерево:
type
TData = Integer; //Тип ключа (тип основных данных) узла дерева. TPNode = ^TNode; //Тип указателя на узел.
TNode = record //Тип узла дерева.
Data : TData; //Ключ (основные данные) узла дерева. PLeft, PRight : TPNode; //Указатели на левый и правый узел.
end;
{Добавление узла с ключом aData в двоичное дерево поиска.} procedure AddNode(var aPNode : TPNode; const aData : TData);
begin |
|
if aPNode = nil then |
//Вставка узла. |
begin |
|
New(aPNode); |
//Выделяем память для узла. |
aPNode^.Data := aData; //Записываем в узел значение ключа. aPNode^.PLeft := nil; //Обнуление указателя на левого потомка. aPNode^.PRight := nil; //Обнуление указателя на правого потомка.
end
else if aData <= aPNode^.Data then //Поиск места вставки в левом поддереве.
AddNode(aPNode^.PLeft, aData)
else if aData > aPNode^.Data then //Поиск места вставки в правом поддереве.
AddNode(aPNode^.PRight, aData); end;
Процедура выполнения условия задания. Выводит номера вершин у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве.
aH - количество узлов в самой длинной ветви с корнем aPNode; aC - количество узлов в дереве (поддереве) с корнем aPNode; Процедура изменяет:
aCnt - добавляет количество узлов, для которых выполянется заданное условие.
В теле процедуры для узла aPNode выполняется проверка на истинность условия: высоты левого и правого поддерева равны, но количество потомков слева и справа - разное.
Распечатка результатов записывается (добавляется) в список aSL.
procedure TreeCalc(const aPNode : TPNode; const aName : String; out aH, aC : Integer; var aCnt : Integer; aSL : TStrings);
var
HL, HR, CL, CR : Integer; begin
if aPNode = nil then //Если узел отсутствует.
begin |
|
aH := 0; |
|
aC := 0; |
|
end |
|
else |
//Если узел существует. |
begin |
|
//Подсчёт высоты и количества потомков для текущего узла.
TreeCalc(aPNode^.PLeft, aName + '-1', HL, CL, aCnt, aSL); //Для левого поддерева. TreeCalc(aPNode^.PRight, aName + '-2', HR, CR, aCnt, aSL); //Для правого поддерева. //Если условие выполняется, то учитываем текущий узел в подсчёте и распечатываем
сведения о нём.
if (HL = HR) and (CL <> CR) then begin
Inc(aCnt);
aSL.Add(aName + ' (' + IntToStr(aPNode^.Data) + '): HL = HR = ' + IntToStr(HL) + ', CL = ' + IntToStr(CL) + ' <> CR = ' + IntToStr(CR));
end;
//Высота и количество потомков для соответствующего поддерева родительского узла. aH := 1 + Max(HL, HR);
aC := 1 + CL + CR; end;
end;
Результаты работы программы:
Рис 2. Главное меню программы
Рис 3. Результат работы программы
Рис 4. Результат работы программы
Рис 5. Результат работы программы