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.