22 var n,cherche,choix : integer,
\r
29 (**** RECHERCHE DU MINIMUM ****)
\r
31 unit minimum:function(racine:barbre):integer;
\r
34 if (racine.inf = none)
\r
35 then result:=racine.page(1).cle
\r
36 else result:=minimum(racine.inf)
\r
40 (**** RECHERCHE DU MAXIMUM ****)
\r
42 unit maximum:function(racine:barbre):integer;
\r
45 if (racine.inf = none)
\r
46 then result := racine.page(racine.nb).cle;
\r
47 else result := maximum(racine.page(racine.nb).sup);
\r
52 (**** RECHERCHE D'UN ELEMENT ****)
\r
54 unit rechercher:function(cherche:integer;tree:barbre):boolean;
\r
55 var left,right,milieu:integer;
\r
58 if (tree=none) then result:=false else
\r
59 left:=1;right:=tree.NB;
\r
60 while (left<=right) and (right>=1)
\r
62 (* RECHERCHE DICHOTOMIQUE *)
\r
64 milieu:=(left+right) div 2;
\r
65 if (cherche<tree.page(milieu).cle) then right:=milieu-1;fi;
\r
66 if (cherche>tree.page(milieu).cle) then left:=milieu+1;fi;
\r
67 if (cherche=tree.page(milieu).cle) then result:=true;exit;fi;
\r
69 if (not result) then
\r
71 (* RECHERCHE DE L'ELEMENT AU NIVEAU SUIVANT *)
\r
73 then result:=rechercher(cherche,tree.inf);
\r
74 else result:=rechercher(cherche,tree.page(right).sup);
\r
81 (**** INSERTION D'UN ELEMENT ****)
\r
83 unit recherche_place:procedure(tree:barbre;cherche:integer;
\r
84 output h:boolean,v:couple);
\r
85 var left,right,milieu:integer,
\r
90 unit insere_deborde:procedure;
\r
92 (* INSERTION DE L'ELEMENT ET TRAITEMENT DES EVENTUELS DEBORDEMENTS *)
\r
100 (* INSERTION DANS LE CAS OU IL N'Y A PAS DE DEBORDEMENT *)
\r
102 tree.nb := tree.nb + 1;
\r
103 h:=false; (* IL N'Y A PAS DEBORDEMENT DONC ON MET H A FALSE *)
\r
104 for i:= tree.nb downto (right+2) do tree.page(i):=tree.page(i-1) od;
\r
105 tree.page(right+1):=u;
\r
108 (* INSERTION DANS LE CAS OU IL Y A DEBORDEMENT *)
\r
111 array b.page dim (1:2*n);
\r
112 if (right <= n) then
\r
113 if (right=n) then v:=u;
\r
114 else v:=tree.page(n);
\r
115 for i:= n downto (right +2) do tree.page(i):=tree.page(i-1) od;
\r
116 tree.page(right+1):=u;
\r
118 for i:= 1 to n do b.page(i):=tree.page(i+n) od;
\r
121 v:= tree.page(n+1);
\r
122 for i := 1 to (right-1) do b.page(i) := tree.page(i+n+1) od;
\r
124 for i := right+1 to n do b.page(i) := tree.page(i+n) od;
\r
132 end insere_deborde;
\r
137 (* CAS ON A DEPASSE LES FEUILLES, OU BIEN L'ARBRE EST VIDE *)
\r
144 (* RECHERCHE DE LA PLACE OU INSERER AU NIVEAU SUIVANT *)
\r
146 left:=1;right:=tree.NB;
\r
147 while (left<=right) and (right>=1)
\r
149 milieu:=(left+right) div 2;
\r
150 if (cherche<tree.page(milieu).cle) then right:=milieu-1;fi;
\r
151 if (cherche>tree.page(milieu).cle) then left:=milieu+1;fi;
\r
152 if (cherche=tree.page(milieu).cle) then
\r
153 writeln(" L'element ",cherche," est deja dans l'arbre");
\r
157 if (left=right) then h:=false;
\r
159 (* APPELS RECURSIFS DE LA PROCEDURE RECHERCHE *)
\r
161 then call recherche_place(tree.inf,cherche,h,u);
\r
162 else call recherche_place(tree.page(right).sup,cherche,h,u);;
\r
165 (* L'INSTRUCTION QUI SUIT N'EST EFFECTUEE QUE LORS DU DEPILAGE
\r
166 DE L'APPEL PRECEDENT DE LA PROCEDURE RECHERCHE_PLACE. SI IL Y A
\r
167 DEBORDEMENT APRES L'APPEL DE INSERE_DEBORDE, ALORS H GARDE LA VALEUR
\r
168 TRUE ET ON FAIT UN APPEL DE INSERE_DEBORDE SUR LE NIVEAU PRECEDENT
\r
169 GRACE AU DEPILLAGE DES APPELS DE RECHERCHE_PLACE *)
\r
171 if (h) then call insere_deborde fi;
\r
174 end recherche_place;
\r
177 unit inserer:procedure(x:integer;inout racine:barbre);
\r
180 call recherche_place(racine,x,h,u);
\r
182 (* CAS OU L'ARBRE EST VIDE, OU CAS OU IL FAUT CREER UNE NOUVELLE RACINE,
\r
183 LE DEBORDEMENT AYANT ATTEINT LA RACINE *)
\r
185 if (h) then q:=racine;
\r
186 racine:=new barbre;
\r
187 array racine.page dim (1:2*n);
\r
195 (**** VISUALISATION ****)
\r
197 unit visualise:procedure( b_arb:barbre;separe:integer);
\r
199 (* VISUALISATION DES ELEMENTS PAR APPELS RECURSIFS SUR L'ARBRE *)
\r
205 for i:= 1 to separe do write(" ") od;
\r
206 for i:= 1 to b_arb.nb do write(b_arb.page(i).cle:5) od;
\r
208 call visualise(b_arb.inf,separe+1);
\r
209 for i:= 1 to b_arb.nb do call visualise(b_arb.page(i).sup,separe+1) od;
\r
214 (**** SAUTER n LIGNES A L ECRAN ****)
\r
216 unit ligne:procedure(n:integer);
\r
219 for i := 1 to n do writeln od;
\r
225 unit menu: procedure(output choix:integer);
\r
228 write(" MANIPULATION DE B-ARBRE ");
\r
230 write(" 1 : recherche de l'element minimum ");
\r
232 write(" 2 : recherche de l'element maximun ");
\r
234 write(" 3 : recherche d'un element quelconque");
\r
236 write(" 4 : Insertion d'un element dans l'arbre ");
\r
238 write(" 5 : Visualisation de l'arbre");
\r
240 write(" 6 : Quitter le programme ");
\r
242 write(" Entrer votre choix : ");
\r
247 (**** PASSAGE AU MENU SUIVANT ****)
\r
249 unit continuer : procedure;
\r
251 (* PERMET DE "FIGER" L'ECRAN POUR LIRE LE RESULTAT *)
\r
257 write(" Pour continuer appuyez deux fois sur 'entree' :");
\r
262 (* ----------------- PROGRAMME PRINCIPAL ------------------- *)
\r
268 write(" ENTRER L'ORDRE DE L'ARBRE :");
\r
276 (* APPEL DE LA PROCEDURE CHERCHANT LE MINIMUM *)
\r
277 when 1 : call ligne(30);
\r
279 then writeln(" L' ARBRE EST VIDE !!!");
\r
281 write(" LE MINIMUM EST ", minimum(racine):2);
\r
286 (* APPEL DE LA PROCEDURE CHERCHANT LE MAXIMUM *)
\r
287 when 2 : call ligne(11);
\r
288 if (racine = none )
\r
290 writeln(" L' ARBRE EST VIDE !!!");
\r
292 write(" LE MAXIMUM EST ", maximum(racine):2);
\r
297 (* APPEL DE LA PROCEDURE CHERCHANT UN ELEMENT QUELCONQUE *)
\r
298 when 3 : write(" ENTRER L'ELEMENT A CHERCHER :");
\r
302 if (rechercher(cherche,racine))
\r
304 writeln(" L'ELEMENT ",cherche :2," SE TROUVE DANS L'ARBRE");
\r
306 writeln(" L'ELEMENT ",cherche:2," N'EST PAS DANS L'ARBRE");
\r
311 (* APPEL DE LA PROCEDURE INSERANT UN ELEMENT *)
\r
312 when 4 : write(" ENTRER L'ELEMENT A INSERER :");
\r
314 call inserer (cherche,racine);
\r
316 (* APPEL DE LA PROCEDURE VISUALISANT UN ARBRE *)
\r
319 then call ligne(30);
\r
320 writeln(" L'ARBRE EST VIDE .");
\r
322 else writeln(" L'arbre est : ");
\r
323 call visualise(racine,1);
\r
327 (* SORTIE DU PROGRAMME *)
\r
328 when 6: rep:= false;
\r