Определить число вхождений элемента Е в дерево Т

program Project1;
 
type
  {Тип ключа (тип основных данных) узла дерева.}
  TData = Integer;
  {Тип указателя на узел.}
  TPNode = ^TNode;
  {Тип узла дерева.}
  TNode = record
    Data : TData; {Ключ (основные данные) узла дерева.}
    PLeft, PRight : TPNode; {Указатели на левый и правый узел.}
  end;
 
{Рекурсивная процедура для построения дерева через пользовательский ввод.
Процедура добавляет дочерний узел к узлу aPNode.
aPNode - указатель на родительский узел. Если родительского узла нет (при
создании корня дерева), то aPNode = nil.
aLR = 1 - создать левый узел, иначе (если aLR <> 1) - создать правый узел.
aName - имя узла. Этот параметр предназначен для удобства ввода.
aName = '0' - корневой узел дерева;
aName = '0-1' - левый узел, связанный с корневым узлом.
aName = '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; aName : String);
var
  PNode : TPNode;
  Data : TData;
  Code : Integer;
  S : String;
begin
  {Формируем имя узла.}
  if aPNode = nil then {Если дерево пустое, то задаём имя корневого узла: "0".}
    aName := '0'
  else {Если дерево непустое, то имя текущего узла будет таким: "<Имя родительского узла>-<aLR>" }
  begin
    Str(aLR, S);
    aName := aName + '-' + S;
  end;
  {Предлагаем пользователю создать узел и задать его ключ.}
  Write('Узел ', aName, '. Значение: ');
  Readln(S);
  if S <> '' then {Если пользователь согласился создать узел и задал его ключ.}
  repeat
    Val(S, Data, Code); {Преобразуем строковое значение в числовое.}
    if Code = 0 then {Если пользователь ввёл значение ключа правильно.}
    begin
      {Создаём узел, записываем в него ключ и в зависимости от флага aLR
      прикрепляем его к левой или к правой ветви родительского узла aPNode.}
      New(PNode); {Выделяем память для узла.}
      PNode^.Data := Data;  {Записываем в узел значение ключа.}
      PNode^.PLeft := nil;  {Обнуляем указатель на левого потомка.}
      PNode^.PRight := nil; {Обнуляем указатель на правого потомка.}
      if aPNode = nil then
        aPNode := PNode {Узел становится корнем дерева.}
      else
      begin
        if aLR = 1 then
          aPNode^.PLeft := PNode {Узел становится левым потомком родительского узла.}
        else
          aPNode^.PRight := PNode; {Узел становится правым потомком родительского узла.}
      end;
      {Рекурсивный вызов диалога создания левого потомка.}
      ReadNode(PNode, 1, aName);
      {Рекурсивный вызов диалога создания правого потомка.}
      ReadNode(PNode, 2, aName);
    end
    else {Если пользователь ввёл данные НЕправильно.}
      Writeln('Неверный ввод. Следует ввести целое число. Повторите.');
  until Code = 0;
end;
 
{Рекурсивная процедура для освобождения памяти, занятой деревом. (Удаление дерева).}
procedure TreeFree(var aPNode : TPNode);
begin
  if aPNode <> nil then
  begin
    if aPNode^.PLeft <> nil then
      TreeFree(aPNode^.PLeft); {Рекурсивный вызов для освобождения памяти в левой ветви.}
    if aPNode^.PRight <> nil then
      TreeFree(aPNode^.PRight); {Рекурсивный вызов для освобождения памяти в правой ветви.}
    Dispose(aPNode); {Освобождение памяти, занятой для текущего узла.}
    aPNode := nil; {Обнуление указателя на текущий узел в родительском узле.}
  end;
end;
 
{Рекурсивная функция для подсчёта узлов с заданным значением ключа.}
function CountNode(const aPNode : TPNode; const aData : TData) : Integer;
var
  Cnt : Integer;
begin
  Cnt := 0; {Количество узлов, у которых значение ключа равено aData.}
  if aPNode <> nil then {Если дерево НЕпустое.}
  begin
    {Если ключ текущего узла равен искомому, то учитываем этот узел в подсчёте.}
    if aPNode^.Data = aData then
      Inc(Cnt);
    {Рекурсивный вызов для подсчёта узлов в левой и правой ветвях.}
    Cnt := Cnt + CountNode(aPNode^.PLeft, aData) + CountNode(aPNode^.PRight, aData);
  end;
  CountNode := Cnt;
end;
 
var
  PTree : TPNode;
  Data : TData;
  Cmd, Code : Integer;
  S : String;
begin
  {Начальная инициализация дерева.}
  PTree := nil;
 
  repeat
    {Меню}
    Writeln('----------');
    Writeln('Выберите действие:');
    Writeln('1: Создать дерево.');
    Writeln('2: Проверить дерево на пустоту.');
    Writeln('3: Подсчитать кол-во узлов с заданным значением ключа.');
    Writeln('4: Удалить дерево.');
    Writeln('5: Выход.');
    Write('Задайте команду: ');
    Readln(Cmd);
    case Cmd of
      1:
      begin
        Writeln('Ввод дерева.');
        Writeln('Программа будет сама предлагать вам ввод узлов. Если вы согласны');
        Writeln('создать предложенный узёл, то задайте его значение и нажмите Enter.');
        Writeln('Чтобы отказаться от создания узла оставьте пустую строку и нажмите Enter.');
        TreeFree(PTree);
        ReadNode(PTree, 0, '');
        Write('Создание дерева завершено. ');
        Readln;
      end;
      2:
      begin
        if PTree <> nil then
          Write('Дерево не пустое. ')
        else
          Write('Дерево пустое. ');
        Readln;
      end;
      3:
      begin
        repeat
          Write('Задайте искомое значение ключа: ');
          Readln(S);
          Val(S, Data, Code);
          if Code <> 0 then
            Writeln('Неверный ввод. Следует ввести целое число. Повторите.');
        until Code = 0;
        Write('Кол-во узлов с заданным значением ключа: ', CountNode(PTree, Data), '. ');
        Readln;
      end;
      4:
      begin
        TreeFree(PTree);
        Write('Дерево удалено (память освобождена). ');
        Readln;
      end;
      5:
      begin
        TreeFree(PTree);
        Writeln('Дерево удалено (память освобождена).');
      end;
      else
        Writeln('Незарегистрированная команда. Повторите ввод.');
        Readln;
    end;
  until Cmd = 5;
 
  Writeln('Работа программы завершена. Для выхода нажмите Enter.');
  Readln;
end.

{Рекурсивная процедура для построения дерева через пользовательский ввод.
Процедура добавляет дочерний узел к узлу aPNode.
aPNode - указатель на родительский узел. Если родительского узла нет (при
создании корня дерева), то aPNode = nil.
aLR = 1 - создать левый узел, иначе (если aLR <> 1) - создать правый узел.
aName - имя узла. Этот параметр предназначен для удобства ввода.
aName = '0' - корневой узел дерева;
aName = '0-1' - левый узел, связанный с корневым узлом.
aName = '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; const aName : String);
var
  PNode : TPNode;
  Data : TData;
  Code : Integer;
  SName, S : String;
begin
  {Формируем имя узла.}
  SName := aName;
  if aPNode = nil then {Если дерево пустое, то задаём имя корневого узла: "0".}
    SName := '0'
  else {Если дерево непустое, то имя текущего узла будет таким: "<Имя родительского узла>-<aLR>" }
  begin
    Str(aLR, S);
    SName := SName + '-' + S;
  end;
  {Предлагаем пользователю создать узел и задать его ключ.}
  Write('Узел ', SName, '. Значение: ');
  Readln(S);
  if S <> '' then {Если пользователь согласился создать узел и задал его ключ.}
  repeat
    Val(S, Data, Code); {Преобразуем строковое значение в числовое.}
    if Code = 0 then {Если пользователь ввёл значение ключа правильно.}
    begin
      {Создаём узел, записываем в него ключ и в зависимости от флага aLR
      прикрепляем его к левой или к правой ветви родительского узла aPNode.}
      New(PNode); {Выделяем память для узла.}
      PNode^.Data := Data;  {Записываем в узел значение ключа.}
      PNode^.PLeft := nil;  {Обнуляем указатель на левого потомка.}
      PNode^.PRight := nil; {Обнуляем указатель на правого потомка.}
      if aPNode = nil then
        aPNode := PNode {Узел становится корнем дерева.}
      else
      begin
        if aLR = 1 then
          aPNode^.PLeft := PNode {Узел становится левым потомком родительского узла.}
        else
          aPNode^.PRight := PNode; {Узел становится правым потомком родительского узла.}
      end;
      {Рекурсивный вызов диалога создания левого потомка.}
      ReadNode(PNode, 1, SName);
      {Рекурсивный вызов диалога создания правого потомка.}
      ReadNode(PNode, 2, SName);
    end
    else {Если пользователь ввёл данные НЕправильно.}
      Writeln('Неверный ввод. Следует ввести целое число. Повторите.');
  until Code = 0;
end;