unit utree;

interface

type
  info  = integer;
  pnode = ^node;
  node  =  record
             A          : info;
             left,right : pnode;
           end;

function tree(N:integer; var F:text):pnode;
  { precte z textoveho souboru F rostouci }
  { posloupnost N cisel a vytvori dokonale vybalancovany }
  { binarni vyhledavaci strom, vrati ukazatel na jeho koren }

implementation

type
  pitem = ^item;
  item  = record
            M    : integer;  { kolik prvku se ma pripojit }
            rf   : pnode;    { kam se to jako pravy podstrom pripojit }
            next : pitem;    { ukazatel na dalsi prvek zasobniku }
          end;

         
  function tree(N:integer; var F:text):pnode;
    var
      F1,        { fiktivni prvek - cely strom pripojuji k nemu zprava }
      F2,        { fiktivni prvek - v cyklu pripojuji k nemu zleva }
      R, Q, P        : pnode;
      Stack ,    { zasobnik zadosti o pripijeni  praveho podstromu }
      PS             : pitem;
      NL,        { pocet prvku v levem podstromu }
      NR         { pocet prvku v levem podstromu }
                     : integer;

    begin
      new(F1); new(F2);
      {vloz zadost o postaveni stromu z N prvku}
      new(Stack);
      with Stack^ do
        begin M:=N; rf:=F1; next:=nil; end;

      repeat

       {vyber vrcholu zasobniku}
        N:= Stack^.M; R:=Stack^.rf;
        PS:=Stack; Stack:=Stack^.next;
        dispose(PS);

        if R<>F1 then read(F,R^.A);

        {pripojim doprava k R}
        if N=0 then R^.right:=nil
               else
           begin

             { pripojuji zleva k fiktivnimu vrcholu F2^ }
             P:=F2;
             repeat
               NL:= (N-1) div 2;
               NR:= N-NL-1;
              { novy prvek do stromu }
               new(Q);
              { zadost o pripojeni stromu o NR prvcich
                jako pravy podstorom uzlu Q^ }
               new(PS);
               with PS^ do
                 begin
                   M:=NR; rf:=Q; next:=Stack;
                 end;
               Stack:=PS;
             { pokracuji v pripojovani leveho podstromu }
               N:=NL;
               P^.left:=Q; P:=Q;
             until N=0;

             Q^.left  := nil;
             R^.right := F2^.left;
           end

      until Stack=nil;

      tree:= F1^.right;

     {uvolneni pameti pri fiktivni prvky F1^ a F2^ }
      dispose(F1);
      dispose(F2)

    end;

end.