unit UBVS;

interface

TYPE
  TKLIC = INTEGER;

  TUK = ^TUZEL;

  TUZEL = RECORD
            klic : TKLIC;
            llink, rlink : TUK
          END;

  cDvs = object
            public
              koren : TUK;
            public

              function ziskejKoren : TUK;
              { metody}
              constructor init;
              procedure preorder(u : TUK);
              procedure inorder(u : TUK);
              procedure postorder(u : TUK);
              {function hledej_Rek(u : TUK; h : TKLIC) : TUK;}
              function hledej_Nerek(u : TUK; h : TKLIC) : TUK;
              procedure pridejList_Rek(var u : TUK; h : TKLIC);
              procedure pridejList_Nerek(var u : TUK; h : TKLIC);
              procedure odeberUzel(var u : TUK; h : TKLIC);
              procedure zrusStrom(var u : TUK);
              procedure vypisStrom(u : TUK);

          end;


implementation
uses crt;

{ ------------ METODY Z TEORIE --------------------------------------------}

constructor cDvs.init;

begin
  self.koren := nil;
end;

procedure cDvs.preorder(u : TUK);

  begin
    if u <> nil then begin
      writeln(u^.klic);
      preorder(u^.llink);
      preorder(u^.rlink);
    end;
  end;

procedure cDvs.inorder(u : TUK);

  begin
    if u <> nil then begin
      inorder(u^.llink);
      writeln(u^.klic);
      inorder(u^.rlink);
    end;
  end;

procedure cDvs.postorder(u : TUK);

  begin
    if u <> nil then begin
      postorder(u^.llink);
      postorder(u^.rlink);
      writeln(u^.klic);
    end;
  end;

function cDvs.hledej_Nerek(u : TUK; h : TKLIC) : TUK;

  begin

    while (u <> nil) and (u^.klic <> h) do begin

      if h < u^.klic then
        u := u^.llink
      else
        u := u^.rlink;
    end;

    hledej_Nerek := u;

  end;

procedure cDvs.pridejList_Rek(var u : TUK; h : TKLIC);

  begin

    if u = nil then begin
      new(u);
      u^.klic := h;
      u^.llink := nil;
      u^.rlink := nil;
    end
    else {<,>,=}
      if h < u^.klic then
        pridejList_Rek(u^.llink, h)
      else {>,=}
        if h > u^.klic then
          pridejList_Rek(u^.rlink, h)
        else {=}
          writeln('Uzel se stejnym klicem uz ve stromu je. operace pridani neprovedena.');
  end;

procedure cDvs.odeberUzel(var u : TUK; h : TKLIC);

  var odeber, predodeber : TUK;

  begin

    if u = nil then
      { h nenalezi bvs}
    else { <,>,= }
      if h < u^.klic then
        odeberUzel(u^.llink, h)
      else
        if h > u^.klic then
          odeberUzel(u^.rlink, h)
        else begin { = }
          odeber := u;
          if u^.llink = nil then
            u := u^.rlink
          else
            if u^.rlink = nil then
              u := u^.llink
            else begin {L,R}
              predodeber := nil;
              odeber := u^.llink;
              while odeber <> nil do begin
                predodeber := odeber;
                odeber := odeber^.rlink;
              end;
              u^.klic := odeber^.klic;
              if predodeber = nil then
                u^.llink:= odeber^.llink
              else
                predodeber^.rlink := odeber^.llink
            end;
        end;

  end;

{-------------- KONEC METOD Z TEORIE ---------------------------------------}

function cDvs.ziskejKoren : TUK;

begin
  ziskejKoren := koren;
end;

procedure cDvs.zrusStrom(var u : TUK);

  {var}

  begin
     if u <> nil then begin
      zrusStrom(u^.llink);
      zrusStrom(u^.rlink);
      dispose(u);
    end;
  end;

{function cDvs.hledej_Rek(u : TUK; h : TKLIC) : TUK;

  begin

    if (u <> NIL) and (u^.klic <> h) then begin

      if h < u^.klic then
        u := hledej_Rek(u^.llink, h)
      else
        u := hledej_Rek(u^.rlink, h);

    end;

    hledej_Rek := u;

  end; }

procedure cDvs.pridejList_Nerek(var u : TUK; h : TKLIC);

  begin

  while u <> nil do begin

      if h < u^.klic then
        u := u^.llink
      else if h > u^.klic then
          u := u^.rlink
          else writeln('uzel se stejnym klicem uz ve stromu je. operace pridani nebyla provedena');

  end;
    if u = nil then begin
      new(u);
      u^.klic := h;
      u^.llink := nil;
      u^.rlink := nil;
    end;

  end;


procedure cDvs.vypisStrom(u : TUK);

begin

  if u<>nil then begin

    writeln(u^.klic);
    vypisStrom(u^.llink);
    vypisStrom(u^.rlink);

  end;

end;


begin



end.