Сортировка двоичным деревом через список - Pascal ABC

Формулировка задачи:

Доброе время суток. Надеюсь на вашу помощь , ибо уже 2ой час сижу и пытаюсь с помощью интернета и магических заклинаний сделать программу . Суть в построении двоичного дерева через список. То есть , делаем список в котором 4 пункта ( Сам введенный элемент , ссылка на родителя , ссылка на левого сына , ссылка на правого сына ) . Как оно строится ? 1ый элемент становится корнем дерева и каждый последующий элемент сравнивается с корнем и ставится слева ( если меньше корня) или справа (если больше корня) . Вообщем суть в том чтобы взять определенную введенную последовательность , выстроить двоичным деревом ( в данном случае списком ) и выдать отсортированную последовательность ( по принципу левый сын - родитель - правый сын ) . Сижу ломаю голову , интернет не помогает . Вот что у меня получилось пока накрутить :
program SortDrev;
uses crt;
type
    derevo=^tderevo;
    tderevo=record
      roditel:derevo;
      info:integer;
      lsin:derevo;
      psin:derevo;
    end;
var
  info:integer;
  f,r:derevo;
 
function Elementi(f,r:derevo;info:integer):derevo; [I]// Построение самого дерева[/I]
  begin
    if r=nil then
      begin
        new(r);
        r^.lsin:=nil;
        r^.psin:=nil;
        r^.roditel:=nil;
        if info < f^.info then 
          f^.lsin:=r
        else 
          f^.psin:=r;
        Elementi:=r;
      end
    else
      begin
        if info<r^.info then 
          Elementi := Elementi(r, r^.lsin, info)
        else 
          Elementi := Elementi(r, r^.psin, info)
      end;
  end;
  
procedure PrintTree(r:derevo; n: integer); // [I]Вывод[/I]
var
  i:integer;
begin
  if r<>nil then 
    begin
      PrintTree(r^.lsin, n+1);
      for i := 1 to n do Write('   ');
      Writeln(r^.info);
      PrintTree(r^.psin, n+1);
     end;
end;

Код к задаче: «Сортировка двоичным деревом через список - Pascal ABC»

textual
type
    derevo=^tderevo;
    tderevo=record
      roditel:derevo;
      info:integer;
      lsin:derevo;
      rsin:derevo;
    end;
var
  P  : Derevo;
  i  : Integer;
 
Procedure AddElem(inf:integer); {[I] Построение самого дерева[/I]}
Var F,R : Derevo;
  begin
    New(R);
    R^.info:=inf;
    R^.roditel:=nil;
    R^.lsin:=nil;
    R^.rsin:=nil;
    If P=nil then P:=R else
    Begin
      F:=P;
      While ((F^.lsin<>nil) and (inf<=F^.info)) or ((F^.rsin<>nil) and (inf>F^.info)) do
        If inf<=F^.info then F:=F^.lsin else F:=F^.rsin;
      If inf<=F^.info then F^.lsin:=R else F^.rsin:=R;
      R^.roditel:=F;
    end;
  end;
  
procedure Sort(F : Derevo); { [I]Вывод[/I]}
Var R : Derevo;
begin
  If F<>nil then
  Begin
    // Write('(',f^.info,')');  {----------for debuging--------------------}  
    If F^.lsin<>nil then Sort(F^.lsin);
    Write(F^.info,' ');
    If F^.rsin<>nil then Sort(F^.rsin);
    Dispose(F);
  end;
end;
 
Begin
  P:=nil;
 
//  i:=1;
//  While i<>0 do  { вводим элементы, конец последовательности 0 }
//  Begin
//    Readln(i);
//    If i<>0 then AddElem(i);
//  end;
  AddElem(4);
  AddElem(2);
  AddElem(6);
  AddElem(1);
  AddElem(3);
  AddElem(5);
  AddElem(7);
  
  Sort(P);
  Writeln;
end.

10   голосов, оценка 4.100 из 5


СОХРАНИТЬ ССЫЛКУ