program Bin_vyhled_strom;
{Operace v binarnim vyhledavacim stromu}

type Uk = ^Uzel;
     Uzel = record
              Info: integer;
              L,P : Uk
            end;

function Hledej (M: Uk; X: integer): Uk;
  {Nalezeni odkazu na uzel s hodnotou X
  v binarnim vyhledavacim stromu s korenem M.
  Pokud tam neni, funkce vraci nil}
  var Nenalezen: boolean;
  begin
    Nenalezen := true;
    while (M<>nil) and Nenalezen do
      if M^.Info = X then
        Nenalezen:=false
      else if M^.Info > X then
        M:=M^.L
      else
        M:=M^.P;
    Hledej:=M
  end;  {Hledej}

procedure Pridej (var M: Uk; X: integer);
  {Pridani noveho uzlu s hodnotou X
  do binarniho vyhledavaciho stromu s korenem M.
  Kdyz uz tam X je, nic se nepridava}
  var Nenalezen: boolean;
      U: Uk;
      Pred: Uk;
  begin
    Nenalezen := true;
    U:=M; Pred:=nil;
    while (U<>nil) and Nenalezen do
      if U^.Info = X then
        Nenalezen:=false
      else if U^.Info > X then
        begin Pred:=U; U:=U^.L end
      else
        begin Pred:=U; U:=U^.P end;
    if Nenalezen then
      begin
        new(U);
        U^.Info:=X;
        U^.L:=nil; U^.P:=nil;
        if Pred=nil then
          M:=U
        else if Pred^.Info>X then
          Pred^.L:=U
        else  {Pred^.Info<X}
          Pred^.P:=U
      end
  end;  {Pridej}

procedure Zrus (var M: Uk; X: integer);
  {Zruseni uzlu s hodnotou X
  v binarnim vyhledavacim stromu s korenem M.
  Kdyz tam X neni, nic se neprovede}
  var Nenalezen: boolean;
      U: Uk;
      Pred: Uk;
      S, PredS: Uk;
  begin
    Nenalezen := true;
    U:=M; Pred:=nil;
    while (U<>nil) and Nenalezen do
      if U^.Info = X then
        Nenalezen:=false
      else if U^.Info > X then
        begin Pred:=U; U:=U^.L end
      else
        begin Pred:=U; U:=U^.P end;
    if not Nenalezen then
      if U^.L=nil then
        begin
        if Pred=nil then
          M:=U^.P
        else if Pred^.Info>X then
          Pred^.L:=U^.P
        else
          Pred^.P:=U^.P;
        dispose(U)
        end
      else if U^.P=nil then
        begin
        if Pred=nil then
          M:=U^.L
        else if Pred^.Info>X then
          Pred^.L:=U^.L
        else
          Pred^.P:=U^.L;
        dispose(U)
        end
      else
        begin
        S:=U^.L;
        PredS:=nil;
        while S^.P<>nil do
          begin PredS:=S; S:=S^.P end;
        U^.Info:=S^.Info;
        if PredS=nil then
          U^.L:=S^.L
        else
          PredS^.P:=S^.L;
        dispose(S)
        end
  end;  {Zrus}

procedure Vypis (M:Uk);
  {Pomocna kontrolni procedura pro vypis stromu M}
  begin
  if M<>nil then
    begin
    write('(');
    Vypis(M^.L);
    write(M^.Info);
    Vypis(M^.P);
    write(')')
    end
  end;

var I, X:integer;
    Z: Uk;

begin
Z:=nil;      {prazdny strom}
writeln('Pozadovana akce:');
writeln('1 ... hledat, 2 ... pridat, 3 ... vypustit');
writeln('4 ... vypis stromu, 0 ... konec');
repeat
  read(I);
  case I of
    1: begin
       write(' hledana hodnota: ');
       readln(X);
       if Hledej(Z,X)=nil then
         writeln('NENI')
       else
         writeln('>',Hledej(Z,X)^.Info,'<');
       end;
    2: begin
       write(' pridavana hodnota: ');
       readln(X);
       Pridej(Z,X);
       end;
    3: begin
       write(' rusena hodnota: ');
       readln(X);
       Zrus(Z,X);
       end;
    4: begin
       Vypis(Z);
       writeln
       end
  end
until I=0
end.