program Project1;
uses
SysUtils, Windows;
type
//Основные данные узла дерева.
TData = Integer;
//Указатель на узел.
TPNode = ^TNode;
//Узел дерева.
TNode = record
Data : TData; //Основные данные узла дерева.
PLeft, PRight : TPNode; //Указатель на левый и правый узел.
end;
//Рекурсивная процедура для построения дерева через пользовательский ввод.
//Процедура добавляет дочерний узел к узлу aPNode.
//aPNode - указатель на родительский узел. Если родительского узла нет (при
//создании корня дерева), то aPNode = nil.
//aLr = 1 - создать левый узел, иначе (если aLr <> 1) - создать правый узел.
//aCode - код узла. Этот параметр предназначен для удобства ввода.
//aCode = '0' - корневой узел дерева;
//aCode = '0-1' - левый узел, связанный с корневым узлом.
//aCode = '0-2' - правый узел, связанный с корневым узлом.
//И т. д.
// 0
// / \
// 0-1 0-2
// / \ / \
// 0-1-1 0-1-2 0-2-1 0-2-2
// / \ / \
// 0-1-1-1 0-1-1-2 0-2-2-1 0-2-2-2
procedure ReadNode(var aPNode : TPNode; const aLr : Integer; aCode : String);
var
PNode : TPNode;
Data : TData;
Code : Integer;
S : String;
begin
//Определяем код узла.
if aPNode = nil then
aCode := '0'
else
aCode := aCode + '-' + IntToStr(aLr);
//Ввод основных данных узла.
Data := 0;
repeat
Write('Yzel ', aCode, '. Znach: ');
Readln(S);
Code := 0;
if S <> '' then begin
Val(S, Data, Code);
if Code <> 0 then
Writeln('Ne verii vvod.');
end;
until Code = 0;
//Если пользователь выбрал отмену при создании узла, то выходим.
if S = '' then begin
Writeln('Otmena.');
Exit;
end;
//Создаём узел, записываем в него данные и в зависимости от флага aLr
//прикрепляем его к левой или к правой ветви родительского узла aPNode.
New(PNode);
PNode^.Data := Data;
PNode^.PLeft := nil;
PNode^.PRight := nil;
if aPNode <> nil then begin
if aLr = 1 then
aPNode^.PLeft := PNode
else
aPNode^.PRight := PNode;
end else
aPNode := PNode;
Writeln('Yzel sozdan');
//Рекурсивный вызов для создания левого узла.
ReadNode(PNode, 1, aCode);
//Рекурсивный вызов для создания правого узла.
ReadNode(PNode, 2, aCode);
end;
//Освобождение памяти, занятой деревом. (Удаление дерева).
procedure TreeFree(var aPNode : TPNode);
begin
if aPNode = nil then Exit;
if aPNode^.PLeft <> nil then TreeFree(aPNode^.PLeft);
if aPNode^.PRight <> nil then TreeFree(aPNode^.PRight);
Dispose(aPNode);
aPNode := nil;
end;
//Рекурсивная функция для подсчёта узлов с заданным значением ключа.
function NumberOfLeaves(p: TPNode): integer;
var total: integer;
begin
NumberOfLeaves := 1;
total := 0;
if (p^.PLeft= nil) and (p^.PRight = nil) then exit; { узел является "листом" }
{ считаем число листьев в левом поддереве }
if p^.PLeft <> nil then inc(total, NumberOfLeaves(p^.PLeft));
{ считаем число листьев в правом поддереве }
if p^.PRight <> nil then inc(total, NumberOfLeaves(p^.PRight));
NumberOfLeaves := total;
{ и возвращаем общее количество листьев в дереве }
end;
var
PTree : TPNode;
Data : TData;
Cmd, Code : Integer;
S : String;
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли и выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
//Начальная инициализация дерева.
PTree := nil;
repeat
//Меню
Writeln('Viberete deistvee:');
Writeln('1: Sozdanie dereva.');
Writeln('2: Proverka na pystoty.');
Writeln('3: Ydalit derevo.');
Writeln('4: Kol-vo listev.');
Writeln('5: Vixod.');
Write('Vvedite komandy: ');
Readln(Cmd);
case Cmd of
1:
begin
Writeln('Vvjd dereva.');
Writeln('chtoi otmenit nasmite Enter.');
TreeFree(PTree);
ReadNode(PTree, -1, '');
Writeln('Derevo sozdano.')
end;
2:
if PTree = nil then
Writeln('Pystoe.')
else
Writeln('Ne pystoe.');
3:
begin
TreeFree(PTree);
Writeln('Derevo ydaleno.');
end;
4:
begin
repeat
TreeFree(PTree);
Val(S, Data, Code);
if Code <> 0 then
Writeln('Kol-vo listev: ', NumberOfLeaves(PTree));
until Code = 0;
end;
5:
begin
TreeFree(PTree);
Writeln('ochisheno.');
end;
else
Writeln('Незарегистрированная команда. Повторите ввод.');
end;
until Cmd = 5;
Writeln('Работа программы завершена. Для выхода нажмите Enter.');
Readln;
end.