Program AVL;
(*******************************************************************)
(*******************************************************************)
(**                                                               **)
(**           IMPLEMENTATION DE QUEUE DE PRIORITE                 **)
(**             REALISATION AVEC ARBRES A.V.L.                    **)
(**                                                               **)
(*******************************************************************)
(**************       PROJET 1  DE LI1        **********************)
(*******************************************************************)
(** Annee 1993-1994      REALISE PAR                        UPPA  **)
(**           GOUGEON Jean-Yves et RICHARD Jerome                 **)
(*******************************************************************)
(*******************************************************************)
 
 
(*************** DEBUT DU PROGRAMME  **********************)
 
(****************** UNIT ************************)
 
(****************************************************************************************************)
(**********             LISTE DES UNITs                                                   ***********)
(****************************************************************************************************)
(********** presentation : page d'acuei                                                   ***********)
(********** init_graph   : contient menu et gestion souris                                ***********)
(********** aide         : page d'aide du programme                                       ***********)
(********** mousepos     : recherche position de souris                                   ***********)
(********** message      : regroupement des messages                                      ***********)
(********** erreur       : regroupement des messages d'erreurs                            ***********)
(********** efface       : efface une partie de l'‚cran concernant les messages           ***********)
(********** ecrit        : ecrit le nombre lu au clavier                                  ***********)
(********** AVL          : d‚claration de la classe AVL pour initialisation des arbres    ***********)
(********** PAUSE        : pour cr‚er une pause ‚cran                                     ***********)
(********** RG           : rotation gauche                                                ***********)
(********** RGD          : rotation gauche droite                                         ***********)
(********** INSERT       : insertion dans un arbre                                        ***********)
(********** EQUILIBRE    : pour ‚quilibrer l'arbre                                        ***********)
(********** MEMBER       : pour d‚tecter si l'element est membre de l'arbre               ***********)
(********** VIDE         : teste si l'arbre est vide ou non                               ***********)
(********** AFFICHE      : affiche l'arbre (racine gauche droit)                          ***********)
(********** MAX          : determine l'element maximum de l'arbre                         ***********)
(********** MIN          : determine l'element minimum de l'arbre                         ***********)
(********** DELETE       : supprime l'element de l'arbre                                  ***********)
(****************************************************************************************************)
 
unit presentation:iiuwgraph procedure;
begin
 
        (* creation d'une bordure*)
 
    call border(13);
 
        (*creation d'un cadre pour la fenetre*)
 
    call move(10,10);
    call draw(10,340);
    call draw( 628,340);
    call draw(628,10);
    call draw(10,10);
    call color(2);
        
        (*contenu du titre*)
    call move(160,80);
    call outstring("IMPLEMENTATION D'UNE QUEUE DE PRIORITE");
    call move(210,100);
    call outstring("METHODE DES ARBRES A.V.L.");
    call color(12);
    call move(250,180);
    call outstring("PROJET NUMERO 1");
    call color(14);
    call move(130,300);
    call outstring("PAR : Mr GOUGEON Jean-Yves et Mr RICHARD Jerome");
        
        (*appel de la procedure pause pour passer a la suite*)
    call PAUSE;
        
        (*appel de l'effacage de l'ecran*)
    call cls;
end presentation;
 
unit init_graph : iiuwgraph procedure(output chx : integer);
var i,b,h,v:integer;
 
begin
pref mouse block
begin
        (*teste si le driver de la souris est charge*)
    if(driver) then
    
    call color(10);
    
    call  move(0,0);
    (*creation d'un cadre pour le menu*)
    call draw(0,26);
    call draw(639,26);
    call draw(639,0);
    call draw(0,0);
    call move(5,10);
    
    (*contenu du menu*)
    call outstring("   INSERT   SUPPRE   RECHRCH   VIDE   MIN   MAX       QUIT                 ?  ");
    
    call move(400,330);
    call showcursor;
    (*montre le curseur de la souris*)

    do
        call getpress(0,h,v,b,gauche,droit,centre);
        (*attend un click et detecte le bouton*)

        if gauche then call mousepos(h,v,chx);
        (*demande la position de la souris*)

                call hidecursor;
                (*enleve le curseur et sauve garde l'envirronnement*)

                gauche:=false;
                (*remet le bouton gauche a false*)

                exit;
        fi;
    od;
    else
        call move(150,200);
        call outstring("VOUS AVEZ BESOIN DE LA SOURIS");

        call PAUSE;
        (*appel de la procedure pause pour passer a la suite*)

        chx:=7;
        (*met chx a 7 pour sortir directement*)
        exit;
    fi;
    call color(9);
    end;
end init_graph;
 
unit aide:iiuwgraph procedure;
begin
call cls;
call color(1);
call move(180,65);
(*creation d'un cadre pour le titre*)
call draw(500,65);
call draw(500,100);
call draw(180,100);
call draw(180,65);
call color(3);
call move(200,80);
(*contenu du titre*)
call outstring("AIDE SUR L'UTILISATION DU PROGRAMME");
call color(4);
call move(80,120);
(*contenu de l'aide*)
call outstring(" INSERT  : Pour construire et inserer des valeurs dans l'arbre.");
call move(80,140);
call outstring(" SUPPRE  : Pour supprimer un element de l'arbre. ");
call move(80,160);
call outstring(" RECHRCH : Pour rechercher un element dans l'arbre. ");
call move(80,180);
call outstring(" VIDE    : Pour indiquer si l'arbre est vide ou non vide.");
call move(80,200);
call outstring(" MIN     : Pour indiquer le minimum present dans l'arbre.");
call move(80,220);
call outstring(" MAX     : Pour indiquer le maximum present dans l'arbre.");
call move(80,240);
call outstring(" QUIT    : Pour sortir de ce programme.");
call move(80,260);
call outstring(" ?       : Cette page d'aide !");
call color(14);
call move(80,280);
call outstring("Pour selectionner une de ces option il faut placer le cuseur de la");
call move(80,300);
call outstring("souris sur le choix et cliquer sur le bouton gauche.");
 
 
 
end aide;
 
unit mousepos : iiuwgraph procedure (x,y:integer;output chx : integer);
var touche:integer;
begin
(*declaration des emplacements du titre pour retourner le choix correspondant*)
if((y>0)and(y<25))then
        if((x<80)and(x>0)) then chx:=1;
        else
        if((x<160)and(x>88)) then chx:=2;
        else
        if((x<220)and(x>168)) then chx:=3;
        else
        if((x<300)and(x>228)) then chx:=4;
        else
        if((x<350)and(x>308)) then chx:=5;
        else
        if((x<400)and(x>358)) then chx:=6;
        else
        if((x<500)and(x>432)) then chx:=7;
        else
        if((x<639)and(x>580)) then chx:=8;
         fi;  fi;  fi;  fi; fi; fi;  fi; fi;
fi;
 
end mousepos;
 
(****** UNIT DE MESSAGE ***********)
unit message:iiuwgraph procedure(x:integer);
begin
case x
        when 0 :

        call move(120,330);
        call outstring("Valider votre choix en cliquant sur le menu ");
        
 
 
        when 1 :

        call efface;
        (*efface les messages*)

        call move(90,330);
        call outstring("Entrez la valeur … ins‚rer (taper 100 pour stopper la saisie):");

 
        when 2 :

        call efface;
        (*efface les messages*)

        call move(150,330);
        call outstring("Entrer la valeur … supprimer:");

 
        when 3 :

        call efface;
        (*efface les messages*)

        call move(150,330);
        call outstring("Entrer la valeur … rechercher : ");

 
        when 4 :

        call efface;
        (*efface les messages*)

        call move(250,290);
        call outstring("L'arbre est vide");

        call PAUSE;
        (*appel de la procedure pause pour passer a la suite*)

 
        when 5 :

        call efface;

        call move(150,290);
        call outstring("L'arbre n'est pas vide");

        call PAUSE;
        (*appel de la procedure pause pour passer a la suite*)
 
        
        when 6 :

          call cls;

          call move(80,150);
          call outstring("Au revoir … bient“t pour une future utilisation !!!");

          call PAUSE;
          (*appel de la procedure pause pour passer a la suite*)
 
        
        when 7 :
                    call move(200,40);
                    call outstring("Voi‡i l'arbre avant r‚‚quilibrage");
        
        when 8 :
                    call move(200,40);
                    call outstring("Voi‡i l'arbre APRES r‚‚quilibrage");
        
        when 9 :

          call efface;
          (*efface les messages*)

          call move(150,290);
          call outstring("Voi‡i l'‚l‚ment maximun de l'arbre :");
          call ecrit(tampon,550,290);

          call PAUSE;
          (*appel de la procedure pause pour passer a la suite*)

 
        when 10 :

          call efface;
          (*efface les messages*)

          call move(150,290);
          call outstring("Voi‡i l'‚l‚ment minimun de l'arbre :");
          call ecrit(tampon,500,290);

          call PAUSE;
          (*appel de la procedure pause pour passer a la suite*)

 
        when 11 :

          call efface;
          (*efface les messages*)

          call move(250,290);
          call outstring(" n'est pas membre de l'arbre");
          call ecrit(val,200,290);

          call PAUSE;
          (*appel de la procedure pause pour passer a la suite*)

 
        when 12 :

         call efface;
         (*efface les messages*)

         call move(150,290);
         call outstring(" est membre de l'arbre");
          call ecrit(val,100,290);

          call PAUSE;
          (*appel de la procedure pause pour passer a la suite*)

 
        when 13 :
          call efface;
          (*efface les messages*)

          call move(250,290);
          call outstring("L'arbre est vide.");

          call PAUSE;
          (*appel de la procedure pause pour passer a la suite*)
 
        when 14 :
           call move(230,40);
           call outstring(" L'ARBRE A.V.L. ACTUEL");
           call move(358,60);
           call outstring("NOEUD");
           call move(358,80);
           call outstring("BALANCE");
 
esac;
call move(400,330);
end message;
 
(********* UNIT ERREUR ********)
unit erreur:iiuwgraph procedure(x:integer);
begin
case x
 
        when 1 :
         call color(10);
         call efface;
          (*efface les messages*)

         call move(100,290);
         call outstring("L'arbre est vide : IMPOSSIBLE D'EFFECTUER UNE SUPPRESSION");
         call move(400,330);
 
        when 2 :
           call color(10);
           call efface;
           (*efface les messages*)

           call move(100,290);
           call outstring("L'arbre est vide : IMPOSSIBLE D'EFFECTUER UNE RECHERCHE");
           call move(400,330);
 
esac;
end erreur;
 
unit efface:iiuwgraph procedure;
var i : integer;
begin

(*efface l'ecran de y=280 a y=330*)
for i:=280 step 5 to 330 do
    call move(80,i);
    call outstring("                                                                             ");
od;
end efface;
 
unit ecrit :iiuwgraph procedure(element : integer, x, y : integer);
    var length, i : integer;
  begin
       call color(5);

       (*convertion du code ascii en chiffre <1000*)
       if(element<0) then
          call move(x-10,y);
          call outstring("-");
          element:=(element*(-1));
       fi;
       call move(x,y);
       call Hascii(48 + element div 100);
       element := element mod 100;
       call Hascii(48 + element div 10);
       call Hascii(48 + element mod 10);
       call move(x-5,y-4);
            (*creation d'un cadre pour l'element*)
       call draw(x+28,y-4);
       call draw(x+28,y+10);
       call draw(x-5,y+10);
       call draw(x-5,y-4);
end ecrit;
 
unit AVL:class;
       var balance,info:real,
       fd,fg:AVL;
end AVL;
 
unit PAUSE:iiuwgraph procedure;
var touche:char;
 
begin
pref mouse block
var h,b,v,p:integer,
touche:char;
begin
droit:=false;

driver:=init(b);
(*teste le driver de souris*)

if(driver) then
    call color(13);
    call move(150,330);
    call outstring("Appuyez sur une le bouton droit de la souris...");
    call move(400,330);

    (*tantque le bouton droit n'est pas selectionner*)
    while ( NOT droit) do
          call getpress(1,h,v,p,gauche,droit,centre);
    od;

    (*efface les messages*)
    call efface;

    (*restitue la couleur*)
    call color(9);
else
   call efface;
   (*efface les messages*)

   call move(150,330);
   call outstring("APPUYER SUR UNE TOUCHE....");

   read(touche);
fi;
end;
end PAUSE;
 
unit RG:procedure(inout sous_arbre:AVL);
   var aux:AVL;
begin
   aux:=sous_arbre.fd;
   sous_arbre.fd:=aux.fg;
   aux.fg:=sous_arbre;
   sous_arbre:=aux;
end RG;
 
unit RD:procedure(inout sous_arbre:AVL);
   var aux:AVL;
begin
   aux:=sous_arbre.fg;
   sous_arbre.fg:=aux.fd;
   aux.fd:=sous_arbre;
   sous_arbre:=aux;
end RD;
 
unit RGD:procedure(inout sous_arbre:AVL);
begin
   call RG(sous_arbre.fg);
   call RD(sous_arbre);
end RGD;
 
unit RDG:procedure(inout sous_arbre:AVL);
begin
   call RD(sous_arbre.fd);
   call RG(sous_arbre);
end RDG;
 
unit INSERT:iiuwgraph procedure(x:integer;inout arbre:AVL);
   var sous_arbre,
       ps_arbre,
       noeud_courant,
       pn_courant,
       noeud_cree:AVL;
begin
   (* cr‚ation de l'objet … ins‚rer *)
 
   noeud_cree:=new AVL;
   noeud_cree.info:=x;
   noeud_cree.balance:=0;
   noeud_cree.fd:=none;
   noeud_cree.fg:=none;
 
   (* si l'arbre est vide *)
 
   if arbre=none
      then
         arbre:=noeud_cree;
      else
 
         (* recherche de l'emplacement o— doit s'effectuer l'insertion *)
 
 
         sous_arbre:=new AVL;
         ps_arbre:=new AVL;
         noeud_courant:=new AVL;
         pn_courant:=new AVL;
         sous_arbre:=arbre;
         ps_arbre:=none;
         noeud_courant:=arbre;
         pn_courant:=none;
         while noeud_courant=/=none
            do
 
               (* recherche de l'emplacement et m‚morisation du
                  dernier sous arbre pour lequel il y aura
                  eventuellement desequilibre aprŠs insertion
                  (valeur actuelle de la balance:+1 ou -1)      *)
 
               if noeud_courant.balance=/=0
                  then
                     sous_arbre:=noeud_courant;
                     ps_arbre:=pn_courant;
               fi;
               pn_courant:=noeud_courant;
               if x<=noeud_courant.info
                  then
                     noeud_courant:=noeud_courant.fg;
                  else
                     noeud_courant:=noeud_courant.fd;
               fi;
            od;
 
            (* ajout du noeud cr‚‚ *)
 
            if x<=pn_courant.info
               then
                  pn_courant.fg:=noeud_cree;
               else
                  pn_courant.fd:=noeud_cree;
            fi;
 
            (* mise … jour des d‚s‚quilibres du sous_arbre au
               noeud cr‚‚ *);
 
            noeud_courant:=sous_arbre;
            while noeud_courant=/=noeud_cree
               do
                  if x<=noeud_courant.info
                     then
                        noeud_courant.balance:=noeud_courant.balance+1;
                        noeud_courant:=noeud_courant.fg;
                     else
                        noeud_courant.balance:=noeud_courant.balance-1;
                        noeud_courant:=noeud_courant.fd;
                  fi;
            od;
 
            (* r‚‚quilibrage *)
 
            call cls;

            call message(7);
            (*Voi‡i l'arbre avant r‚‚quilibrage*)

            call AFFICHE(arbre,0,649,60);
                (*appel procedure affichage arbre*)  

            call EQUILIBRE(sous_arbre);
 
            if ps_arbre=none
               then
                  arbre:=sous_arbre;
               else
                  if sous_arbre.info<=ps_arbre.info
                     then
                        ps_arbre.fg:=sous_arbre;
                     else
                        ps_arbre.fd:=sous_arbre;
                  fi;
            fi;

            call PAUSE;
            (*appel de la procedure pause pour passer a la suite*)

            call cls;
            (*appel de l'effacage de l'ecran*)

            call color(9);

            call message(8);
            (*Voi‡i l'arbre APRES r‚‚quilibrage*)

            call AFFICHE(arbre,0,649,60);
            (*appel procedure affichage arbre*) 

            call PAUSE;
            (*appel de la procedure pause pour passer a la suite*)

            call color(9);
   fi;
end INSERT;
 
unit EQUILIBRE:procedure(inout sous_arbre:AVL);
   var
      aux1,aux2:AVL,
      balance,
      balance_fd,
      balance_fg:real;
begin
if (NOT VIDE(sous_arbre)) then
   if sous_arbre.balance=-1
      then
 
         balance:=3;
      else
         if sous_arbre.balance=-2
            then
               balance:=4;
            else
               balance:=sous_arbre.balance;
         fi;
   fi;
   case balance
      when 0:
         exit;
      when 1:
         exit;
      when 3:
         exit;
      when 2:
         if sous_arbre.fg.balance=-1
            then
               balance_fg:=2;
            else
               balance_fg:=sous_arbre.fg.balance;
         fi;
         case balance_fg
            when 0:
               aux1:=sous_arbre.fg;
               aux2:=aux1.fd;
               sous_arbre.balance:=1;
               aux1.balance:=-1;
               sous_arbre.fg:=aux2;
               aux1.fd:=sous_arbre;
               sous_arbre:=aux1;
            when 1:
               call RD(sous_arbre);
               sous_arbre.balance:=0;
               sous_arbre.fd.balance:=0;
            when 2:
               call RGD(sous_arbre);
               if sous_arbre.balance=-1
                  then
                     balance:=2;
                  else
                     if sous_arbre.balance=1
                        then
                           balance:=1;
                        else
                           balance:=0;
                     fi;
               fi;
               case balance
                  when 1:
                     sous_arbre.fg.balance:=0;
                     sous_arbre.fd.balance:=-1;
                  when 2:
                     sous_arbre.fg.balance:=1;
                     sous_arbre.fd.balance:=0;
                  when 0:
                     sous_arbre.fg.balance:=0;
                     sous_arbre.fd.balance:=0;
               esac;
               sous_arbre.balance:=0;
         esac;
      when 4:
         if sous_arbre.fd.balance=-1
            then
               balance_fd:=2;
            else
               balance_fd:=sous_arbre.fd.balance;
         fi;
         case balance_fd
            when 1:
               call RDG(sous_arbre);
               if sous_arbre.balance=-1
                  then
                     balance:=2;
                  else
                     if sous_arbre.balance = 1
                        then
                           balance := 1;
                        else
                           balance := 0;
                     fi;
               fi;
               case balance
                  when 1:
                     sous_arbre.fd.balance:=-1;
                     sous_arbre.fg.balance:=0;
                  when 2:
                     sous_arbre.fd.balance:=0;
                     sous_arbre.fg.balance:=1;
                  when 0:
                     sous_arbre.fd.balance:=0;
                     sous_arbre.fg.balance:=0;
               esac;
               sous_arbre.balance:=0;
            when 0:
               aux1:=sous_arbre.fd;
               aux1.balance:=1;
               sous_arbre.balance:=-1;
               aux2:=aux1.fg;
               aux1.fg:=sous_arbre;
               sous_arbre.fd:=aux2;
               sous_arbre:=aux1;
            when 2:
               call RG(sous_arbre);
               sous_arbre.balance:=0;
               sous_arbre.fg.balance:=0;
         esac;
   esac;
fi;
 
end EQUILIBRE;
 
unit MEMBER:function(val:real;
                     arbre:AVL;
                     output pos_element:AVL):boolean;
begin
   do
      if arbre=/=none
         then
            pos_element:=arbre;
            if val>arbre.info
               then
                  arbre:=arbre.fd;
               else
                  if arbre.info=val
                     then
                        result:=TRUE;
                        exit;
                     else
                        arbre:=arbre.fg;
                  fi;
            fi;
         else
            result:=FALSE;
            exit;
      fi;
   od;
end MEMBER;
 
unit VIDE:function(arbre:AVL):boolean;
begin
   if arbre=none
      then
         result:=TRUE;
      else
         result:=FALSE;
   fi;
end VIDE;
 
unit AFFICHE:iiuwgraph procedure(t:AVL;xmin,xmax,y:integer);
var w:integer;
begin
   if t=/=none
      then
        w:=((xmin-xmax)/2)+xmax;
        (*divise la longeur de l'ecran par 2 pour la position*)

        call color(10);
        call ecrit(t.info,w,y);

        call ecrit(t.balance,w,y+20);

        call AFFICHE(t.fg,xmin,w,y+60);
        (*appel procedure affichage arbre avec fils gauche*) 

        call AFFICHE(t.fd,w,xmax,y+60);
        (*appel procedure affichage arbre avec fils droit*) 
   fi;
   call color(9);
end AFFICHE;
 
unit MAX:procedure(input sous_arbre:AVL;output element:AVL);
begin
   element:=sous_arbre;
   while element.fd=/=none
      do
         element:=element.fd;
   od;
end MAX;
 
unit MIN:procedure(input sous_arbre:AVL;output element:AVL);
begin
   element:=sous_arbre;
   while element.fg=/=none
      do
         element:=element.fg;
   od;
end MIN;
 
unit DELETE:procedure(x:real;input arbre:AVL;input pere:AVL);
var
   balance_pere:integer,
   pere_element,pos_element,element:AVL;
begin
   if x>arbre.info
      then
                (*si x>info de l'arbre aller fils droit*)
         call DELETE(x,arbre.fd,arbre);
      else
         if x<arbre.info
            then
                (*si x<info aller fils gauche*)
               call DELETE(x,arbre.fg,arbre);
            else
 
               (* on a trouv‚ x *)
               (* si la balance de l'objet … supprimer=0 et si il n'a*)
               (* pas de fils droit par exemple cela veut dire qu'il n'a*)
               (*pas de sous_arbre*)
 
               if (arbre.balance=0 AND arbre.fd=none)
                  then
                     balance_pere:=pere.balance;
                     if pere.info>x
                        then
                           pere.fg:=none;
                           pere.balance:=pere.balance-1;
                        else
                           pere.fd:=none;
                           pere.balance:=pere.balance+1;
                     fi;
                  else
                     if (arbre.fg=none AND arbre.fd=/=none) OR
                        (arbre.fg=/=none AND arbre.fd=none)
                        then
                           balance_pere:=pere.balance;
                           if arbre.fd=none
                              then
                                 if x<pere.info
                                    then
                                       pere.fg:=arbre.fg;
                                       y:=arbre.fg.info;
                                       pere.balance:=pere.balance-1;
                                    else
                                       pere.fd:=arbre.fg;
                                       pere.balance:=pere.balance+1;
                                 fi;
                              else
                                 (*le fils gauche est … none *)
                                 if x<pere.info
                                    then
                                       pere.fg:=arbre.fd;
                                       pere.balance:=pere.balance-1;
                                    else
                                       pere.fd:=arbre.fd;
                                       pere.balance:=pere.balance+1;
                                 fi;
                           fi;
                     fi;
               fi;
               kill(arbre);
                (*destruction de la feuille*)
               call EQUILIBRE(pere);
               (* r‚‚quilibrage selon la balance *)
                                     (* du pŠre *)
         fi;
   fi;
   if low
      then
         if x<pere.info
            then
               balance_pere:=pere.balance;
               pere.balance:=pere.balance-1;
            else
               balance_pere:=pere.balance;
               pere.balance:=pere.balance+1;
         fi;
      low:=FALSE;
   fi;
   if pere.balance=0 AND balance_pere=/=0
      then
         low:=TRUE;
      else
         low:=FALSE;
   fi;
end DELETE;
 
(**********************FIN UNIT ****************************)
 
 
(**************************** DEBUT PRINCIPAL *******************)
var
  val,choix,cas,y,valeur,tampon:real,
  tree,pere_max,elem_max,pere_noeud_supprime,pos_noeud_supprime,pere
  ,position,recherche:AVL,
  low,driver,droit,gauche,centre:boolean,
  nombre_noeud : integer,
  touche:char;
 
 
BEGIN
    pref iiuwgraph block
    begin
        driver:=false;
        call HPAGE(0,0,0);
        call HPAGE(0,639,349);
        call gron(0);
        call presentation;
        gauche:=false;
        droit:=false;
        centre:=false;
 
        call border(5);
        call color(9);
 
        (*** demande choix ***)
        call message(0);
        (*Valider votre choix en cliquant sur le menu*)
        
        call init_graph(choix);
        
        nombre_noeud:=0;
do
  case choix
 
     when 1:

        call message(1);
        (*Entrez la valeur … ins‚rer (taper 100 pour stopper la saisie):*)

        call move(400,330);
        read(val);

        while(MEMBER(val,tree,position))do

         call message(12);
         (*est membre de l'arbre*)

         call move(400,330);

         call message(1);
         (*Entrez la valeur … ins‚rer (taper 100 pour stopper la saisie):*)

         read(val);
        od;
        nombre_noeud:=nombre_noeud+1;
 
        while val=/=100
        do
        if nombre_noeud<16
        then
              call INSERT(val,tree);

              call message(7);
              (*Voi‡i l'arbre avant r‚‚quilibrage*)

              call message(1);
              (*Entrez la valeur … ins‚rer (taper 100 pour stopper la saisie):*)

              call move(400,330);

              read(val);

              while(MEMBER(val,tree,position))do

                    call message(12);
                    (*est membre de l'arbre*)

                    call move(400,330);

                    call message(1);
                    (*Entrez la valeur … ins‚rer (taper 100 pour stopper la saisie):*)

                    read(val);
              od;
              nombre_noeud:=nombre_noeud+1;
        else
           call color(10);
           call move(150,290);
           call outstring(" VOUS AVEZ ATTEINT LE MAXIMUM ");

           call PAUSE;
           (*appel de la procedure pause pour passer a la suite*)

           val:=100;
           (*affecte 100 pour sortir de la boucle*)

           call color(9);
        fi;
        od;
        call efface;
 
     when 2:
 
        if VIDE(tree)
        then

         call erreur(1);
         (*L'arbre est vide : IMPOSSIBLE D'EFFECTUER UNE SUPPRESSION*)

         call PAUSE;
         (*appel de la procedure pause pour passer a la suite*)

        else
 
         call message(2);
         (*Entrer la valeur … supprimer:*)

         call move(400,330);
         read(val);
         (*lit nouvelle valeur*)
 
         if member(val,tree,position)
           then

              call message(7);
              (*Voi‡i l'arbre avant r‚‚quilibrage*)
              pere:=new AVL;

              if position.fg=/=none AND position.fd=/=none
                 then

                    call MAX(position.fg,elem_max);
                    valeur:=elem_max.info;
                    call DELETE(elem_max.info,tree,pere);
                    if MEMBER(val,tree,position)
                       then
                          position.info:=valeur;
                    fi;

                    if VIDE(tree)
                    then

                     call message(13);
                     (*L'arbre est vide.*)

                    else

                     call cls;
                     (*appel de l'effacage de l'ecran*)

                     call message(7);
                     (*Voi‡i l'arbre avant r‚‚quilibrage*)

                     call AFFICHE(tree,0,649,60);
                     (*appel procedure affichage arbre*)

                     call EQUILIBRE(tree);

                     call PAUSE;
                      (*appel de la procedure pause pour passer a la suite*)

                     call cls;
                      (*appel de l'effacage de l'ecran*)

                     call message(8);
                     (*Voi‡i l'arbre APRES r‚‚quilibrage*)

                     call AFFICHE(tree,0,649,60);
                     (*appel procedure affichage arbre*)

                     call PAUSE;
                     (*appel de la procedure pause pour passer a la suite*)
                     call color(9);
                  fi;
                 else
                    call DELETE(val,tree,pere);

                    call cls;
                    (*appel de l'effacage de l'ecran*)

                    call message(7);
                    (*Voi‡i l'arbre avant r‚‚quilibrage*)

                    call AFFICHE(tree,0,649,60);
                    (*appel procedure affichage arbre*)
                    call EQUILIBRE(tree);
                    call PAUSE;
                    (*appel de la procedure pause pour passer a la suite*)

                    call cls;
                    (*appel de l'effacage de l'ecran*)

                    call message(8);
                    (*Voi‡i l'arbre APRES r‚‚quilibrage*)

                    call AFFICHE(tree,0,649,60);
                    (*appel procedure affichage arbre*)

                    call PAUSE;
                    (*appel de la procedure pause pour passer a la suite*)

                    call color(9);
              fi;
              if(VIDE(tree)) then
                 nombre_noeud:=0;
              else
                 nombre_noeud:=nombre_noeud-1;
              fi;
        else
 
              call message(11);
 
         fi;
        fi;
 
     when 3:
        if VIDE(tree)
        then
           call erreur(2);
           (*L'arbre est vide : IMPOSSIBLE D'EFFECTUER UNE RECHERCHE*)
           call PAUSE;
            (*appel de la procedure pause pour passer a la suite*)
        else
                call message(3);
                  (*Entrer la valeur … rechercher :*)
                call move(400,330);
                read(val);
                if (MEMBER(val,tree,position))
                then
                   call message(12);
                    (*est membre de l'arbre*)
                else
                   call message(11);
                   (*n'est pas membre de l'arbre*)
                fi;
        fi;
 
     when 4:
 
        if VIDE(tree)
           then
                call message(4);
                 (*L'arbre est vide*)
           else
                call message(5);
                (*L'arbre n'est pas vide*)
        fi;
 
     when 5:
 
        if VIDE(tree)
        then
                call erreur(2);
                (*L'arbre est vide : IMPOSSIBLE D'EFFECTUER UNE RECHERCHE*)
                call PAUSE;
                (*appel de la procedure pause pour passer a la suite*)
        else
           recherche:=tree;
           while(recherche=/=none)
           do
              tampon:=recherche.info;
              recherche:=recherche.fg;
           od;
           call message(10);
           (*Voi‡i l'‚l‚ment minimun de l'arbre :*)
        fi;
 
     when 6:
 
        if VIDE(tree)
        then
                call erreur(2);
                (*L'arbre est vide : IMPOSSIBLE D'EFFECTUER UNE RECHERCHE*)
                call PAUSE;
                (*appel de la procedure pause pour passer a la suite*)
        else
          recherche:=tree;
          while(recherche=/=none)
          do
              tampon:=recherche.info;
              recherche:=recherche.fd;
          od;
          call message(9);
          (*Voi‡i l'‚l‚ment maximun de l'arbre :*)
        fi;
 
     when 7:
                call message(6);
                (*Au revoir … bient“t pour une future utilisation !!*)
                exit;
     when 8 : (* AIDE *)
                call efface;
                (*efface les messages*)
                call aide;
                (*appel procedure aide*)
                call PAUSE;
                (*appel de la procedure pause pour passer a la suite*)
  esac;
        call cls;
          (*appel de l'effacage de l'ecran*)
        call message(14);
         (*L'ARBRE A.V.L. ACTUEL*)
        call AFFICHE(tree,0,649,60);
        (*appel procedure affichage arbre*)
        call color(9);
        call message(0);
        (*Valider votre choix en cliquant sur le menu*)
        call init_graph(choix);
  od;
        call groff;
    end;
END AVL;
(*************************FIN PRINCIPAL ********************)