program bintree;
uses crt;
type pnode=^node;
node = record
    data: word; {ключ}
    left : pnode; {указатель на левое поддерево}
    right:pnode;  {указатель на правое поддерево}
end;
var
root: pnode;
key : word;
option : word;
function find(root :pnode;key:word;var p,parent:pnode):boolean;
begin
 p:=root;{поиск начинается от корня}
 while p <>nil do begin
    if key= p^.data then    {узел с таким ключем есть}
     begin find :=true;exit end;
     parent:=p; {запомнить указатель перед спуском}
     if key < p^.data
      then p:=p^.left  {спуститься влево}
      else p:=p^.right; {спуститься вправо}
     end;
     find :=false;
 end;

Procedure del (var root:pnode; key:word);
var p : pnode; {удаялемый узел}
    parent : pnode; {предоок удаляемого узла}
    Y : pnode; {узел, заменяющий удаляемый}
function descent( p: pnode):pnode; {спуск по дереву}
var y : pnode;  {узел заменящий удаляемый}
    prev :pnode; {предок узла "Y"}
     begin
    y:=p^.right;
     if y^.left = nil then y^.left:=p^.left
     else begin
       repeat
        prev := y; y:=y^.left;
        until y^.left = nil;
        y^.left:=p^.left;
        prev^.left := y^.right;
        y^.right:=p^.right;
        end;
        descent:=y;
        end;
 begin
 if not find(root,key,p,parent) then begin
   writeln('takogo elementa net'); exit; end;
 if  p^.left = nil then y:=p^.right
 else if p^.right = nil then y:=p^.left
 else y:=descent(p);
 if p=root then root:=y
 else
   if  key <parent^.data
    then parent^.left := y
    else parent^.right:=y;
   dispose(p);
 end;
 procedure print_tree(p:pnode; level:integer);
 var i:integer;
  begin
   if p=nil then exit;
   with p^ do begin
       print_tree(right,level+1);
       for i:=1 to level do write('    ');
       writeln(data);
       print_tree(left,level+1);
   end
  end;
  
 Procedure insert(var root:pnode;key:word);
 var p,parent:pnode;
  begin
   if find(root,key,p,parent) then begin
     writeln('takoi element y*e est'); exit;end;
      new(p);
      p^.data:=key;
      p^.left:=nil;
      p^.right:=nil;
      if root = nil then root :=p
      else {присоединение нового элемента}
          If key < parent^.data
          then parent^.left:=p
          else parent^.right:=p;
      end;
 {****************************************************************}
  begin
   root:=nil;
   while true do begin
   writeln('1 - vstavka, 2 - delete, 3 - vivod, 4 - exit');
   readln(option);
   case option of
    1: begin
         writeln('vvedite key dl9 vstavki : ');
         readln(key);
         insert(root,key);
       end;
    2:begin
        writeln('vvedite key dl9 ydalenu9: ');
            readln(key);
            del(root, key);
       end;
    3: begin
       clrscr;
         if root = nil then writeln('derevo pystoe')
         else print_tree(root,0);
         end;
    4: exit;
    end;
    writeln;
    end

  end.