Program P129;
 { Crearea unui arbore binar - iteraţie }
type AdresaNod=^Nod;
     Nod=record
               Info : string;
            Stg, Dr : AdresaNod
         end;

     AdresaCelula=^Celula;
     Celula=record
                  Info : AdresaNod;
                   Urm : AdresaCelula
            end;

var  T : AdresaNod;    { rădăcina }
   Prim,               { primul element din coadă }
 Ultim : AdresaCelula; { ultimul element din coadă }


procedure IntroduInCoada(Q : AdresaNod);
var R : AdresaCelula;
begin
 new(R);
 R^.Info:=Q;
 R^.Urm:=nil;
 if Prim=nil then begin Prim:=R; Ultim:=R end
          else begin Ultim^.Urm:=R; Ultim:=R end;
end; { IntroduInCoada }

procedure ExtrageDinCoada(var Q : AdresaNod);
var R : AdresaCelula;
begin
 if Prim=nil then writeln('Coada este vidă')
          else begin
                 R:=Prim;
                 Q:=R^.Info;
                 Prim:=Prim^.Urm;
                 dispose(R);
               end;
end; { ExtrageDinCoada }


procedure CreareArboreBinar;
var R, Q : AdresaNod;
       s : string;
begin
 T:=nil;                { iniţial arborele este vid }
 Prim:=nil; Ultim:=nil; { iniţial coada este vidă }
 writeln('Daţi rădăcina:'); readln(s);
 if s<>'' then
    begin
     new(R); { crearea rădăcinii }
     R^.Info:=s;
     T:=R;   { iniţializarea adresei rădăcinii }
     IntroduInCoada(T);
    end;
 while Prim<>nil do  { cît coada nu e vidă }
    begin
     ExtrageDinCoada(R);
     writeln('Daţi descendenţii nodului  ', R^.Info);
     write('  stîng:  '); readln(s);
     if s='' then R^.Stg:=nil
        else
            begin
             new(Q); R^.Stg:=Q;
             Q^.Info:=s;
             IntroduInCoada(Q);
            end; { else }
     write('  drept:  '); readln(s);
     if s='' then R^.Dr:=nil
        else
            begin
             new(Q); R^.Dr:=Q;
             Q^.Info:=s;
             IntroduInCoada(Q);
            end; { else }
    end; { while }
end; { CreareArboreBinar }

procedure AfisareArboreBinar;
var R : AdresaNod;
begin
 if T=nil then writeln('Arbore vid')
    else
     begin
      writeln('Arborele este format din:');
      Prim:=nil; Ultim:=nil;
      IntroduInCoada(T);
      while Prim<>nil do
            begin
             ExtrageDinCoada(R);
             writeln('Nodul  ', R^.Info);
             write('  descendenţi: ');
             if R^.Stg=nil then write('nil, ')
                else begin
                      write(R^.Stg^.Info, ', ');
                      IntroduInCoada(R^.Stg);
                     end;

             if R^.Dr=nil then writeln('nil')
                else begin
                      writeln(R^.Dr^.Info);
                      IntroduInCoada(R^.Dr);
                     end;
            end; { while }
     end; { else }
 readln;
end; { AfisareArboreBinar }

begin
 CreareArboreBinar;
 AfisareArboreBinar;
end.