Бинарное дерево - Просмотр дерева в следующем порядке: узел, левая ветвь, правая ветвь - Pascal ABC

uses crt;
type
PNode=^Node;  {Указатель на узел}
 Node=record  {Тип запись в котором будет храниться информация}
   data      : integer;
   left,right: PNode; {Ссылки на левого и правого сыновей}
end;
 
var
  Tree,p1: PNode; {Tree адрес корня дерева, p1-вспомогательная переменная}
  Ovn    : PNode; { Владелец найденного элемента после поиска }
  n,x,i:integer;
  ch:char; {для работы менюшки}
 
{Процедура добавления элемента }
procedure AddToTree (var Tree: PNode;x:integer); {Входные параметры - адрес корня дерева и добавл элемент }
begin
 if Tree=nil then  {Если дерево пустое то создаём его корень}
   begin
     New(Tree);   {Выделяем память }
     Tree^.data:=x;     {Добавляем данные }
     Tree^.left:=nil;     {Зануляем указатели на левого }
     Tree^.right:=nil;  {и правого сыновей }
      exit;
   end;
 if x < Tree^.data then   {Доб к левому или правому поддереву это завсит от вводимого элемента}
     AddToTree(Tree^.left,x)  {если меньше корня то в левое поддерево }
  else
    AddToTree(Tree^.right,x);  {если больше то в правое}
end;
 
{Функция поиска по дереву}
function Search(Tree: PNode;x:integer): PNode; {Возвращает адрес искомого элемента, nil если не найден}
var
p: PNode;   {вспомог переменнная }
begin
  if Tree=nil then   {если дерево пустое то}
     begin
       Search:=nil;  {присваеваем функции результат нил}
       exit; {и выходим }
     end;
  if x=Tree^.data then  {если искомый элемент равен корню дерева то }
    p:=Tree  {Пзапоминаем его адрес }
     else begin  {иначе}
       Ovn:=Tree; {сохраняем в глоб. перем адрес отца сыновей}
       if x < Tree^.data then {если вводимый элемент менньше корня то }
          p:=Search(Tree^.left,x) {то ищем его в левом поддереве}
                         else     {иначе }
          p:=Search(Tree^.right,x);  {ищем в правом поддереве }
     end;
  Search:=p; {присваеваем переменной с именем фугкции результат работы}
end;
 
{Обход дерева по принципу Левый-корень-правый }
procedure Lkp(Tree: PNode);
begin
  if Tree=nil then  {Если дерево пустое }
   exit;      {то выход }
  Lkp(Tree^.data);  {иначе начинаем обход с левого подднрева}
  write('  ',Tree^.data); {выводим данные }
  Lkp(Tree^.right);  {обходим правое поддерево}
end;
 
{ Вставить уже существующее дерево/элемент в структуру дерева }
procedure InsertNode(var Tree : PNode; Ins : PNode);
begin
 if Tree=nil then  {Если дерево пустое то вставляемый будет корнем }
   begin
     Tree:=Ins; exit;
   end;
 if Ins^.Data < Tree^.data then   {Доб к левому или правому поддереву это завсит от вводимого элемента}
     InsertNode(Tree^.left,Ins)  {если меньше корня то в левое поддерево }
  else
     InsertNode(Tree^.right,Ins);  {если больше то в правое}
end;
 
{Удаление елемента в дереве. true, если елемент был удален}
function DeleteNode(var Tree: PNode; x:integer):boolean;
var ToIns,ToDel: PNode;
begin
  Ovn:=nil; { глоб. перем для определения владельца удаляемого }
  ToDel:=Search(Tree,x); DeleteNode:=true;
  if ToDel = nil then begin DeleteNode:=false; exit; end;
  if ToDel=Tree then begin { найденный элемент является корнем }
    if ToDel^.left<>nil then begin
      Tree:=ToDel^.left;   { корнем становится левый сучок }
      ToIns:=ToDel^.right; { а правый потом вставим }
    end else begin        {если и правый окажется nil, то все дерево пустое}
      Tree:=ToDel^.right;  { корнем становится правый }
      ToIns:=ToDel^.left;  { левый вставим позже }
    end;
  end else begin
    if Ovn^.right=ToDel then begin {если найденный под удаление правый, то}
      Ovn^.right:=ToDel^.right; {правый сын предка теперь его внук }
      ToIns:=ToDel^.left;         {оставшийся сучок, который нужно вставить}
    end else begin
      Ovn^.left:=ToDel^.left;   { иначе левый внук становится сыном}
      ToIns:=ToDel^.right;      { оставшийся не у дел }
    end;
  end;
  Dispose(ToDel); { Удаление найденного элемента }
  InsertNode(Tree,ToIns); { Вставляем оставшийся сучок в структуру дерева }
end;
 
{Процедура удаления дерева}
procedure DeleteTree(var Tree1: PNode );
begin
        if Tree1 <> nil then
          begin
            DeleteTree (Tree1^.LEFT);
            DeleteTree (Tree1^.RIGHT);
            Dispose(Tree1);
          end;
end;
 {основная пограмма}
Begin
 Tree:=nil; Ovn:=nil;
 repeat {цикл для нашего меню}
 
    Writeln('Выберете действие ');
    Textcolor(2);
    Writeln('Доступны следующие пункты:');
    Writeln('1) Создание дерева поиска');
    if Tree<>nil then Writeln('2) Поиск элемента в дереве');
    Writeln('3) Вывод дерева');
    if Tree<>nil then WriteLn('4) Удаление элемента');
    Writeln('5) ВВыход');
    writeln;
    readln(ch); {ожидаем нажатия клавиши}
    case ch of {выбираем клавишу}
      '1': begin
            writeln(' kolv elementov');
            readln(n);
              for i:=1 to n do
                begin
                  writeln('Введите число');
                  readln(x);
                  AddToTree(Tree,x);
                end;
           end;
       '2': begin
               writeln('Ёлемент для поиска');
               readln(x);
               p1:=Search(Tree,x);
                  if p1 <> nil then
                    writeln('Найден')
                  else writeln('Такого элемента нет!');
            end;
        '3': begin
              writeln('Само дерево');
              Lkp(Tree);
              writeln;
             end;
       '4': begin
               writeln('Элемент для удаления');
               readln(x);
               if DeleteNode(Tree,x) then writeln('Удален')
                                     else writeln('Такого элемента нет!');
            end;
        end;
   until ch='5';
   DeleteTree(Tree);
End.

procedure Lkp(Tree: PNode);
begin
  if Tree=nil then  {Если дерево пустое }
   exit;      {то выход }
  Lkp(Tree^.data);  {иначе начинаем обход с левого подднрева}
  write('  ',Tree^.data); {выводим данные }
  Lkp(Tree^.right);  {обходим правое поддерево}
end;