2 (* Mlles Beau et Delburg *)
\r
3 (* representation d'un noeud *)
\r
11 nb est le nombre de fils
\r
12 IG est l'information de gauche
\r
13 IM est l'information de droite
\r
14 FG est le fils de gauche
\r
15 FM est le fils du milieu
\r
16 FD est le fils de droite
\r
19 (* initialisation des variables *)
\r
31 Unit barbre : class;
\r
34 unit afficher : procedure(inout courant : noeud);
\r
38 (* courant pointe sur une feuille *)
\r
39 writeln(courant.IG:1);
\r
41 (* courant pointe sur un noeud *)
\r
42 writeln(courant.IG:1, ":", courant.IM:1);
\r
45 if courant.FG =/= none
\r
47 (* courant a 1, 2 ou 3 fils *)
\r
48 if courant.FG.FG =/= none
\r
50 (* courant a 2 ou 3 petits fils *)
\r
51 (* appel de la procedure afficher avec le fils gauche de courant *)
\r
52 call afficher(courant.FG);
\r
53 if courant.FM =/= none
\r
55 (* courant a 2 ou 3 fils *)
\r
56 (* appel de la procedure afficher avec le fils milieu de courant *)
\r
57 call afficher(courant.FM);
\r
58 if courant.FD =/= none
\r
60 (* courant a 3 fils *)
\r
61 (* appel de la procedure afficher avec le fils droit de courant *)
\r
62 call afficher(courant.FD);
\r
66 (* courant n'a pas de petits fils
\r
67 i.e. les fils de courant sont des feuilles *)
\r
68 (* affichage de la feuille de gauche *)
\r
69 write(courant.FG.IG:1);
\r
70 if courant.FM =/= none
\r
72 (* courant a 2 ou 3 fils *)
\r
73 (* affichage de la feuille du milieu *)
\r
74 write(" ", courant.FM.IG:1);
\r
75 if courant.FD =/= none
\r
77 (* courant a 3 fils *)
\r
78 (* affichage de la feuille de droite *)
\r
79 writeln(" ", courant.FD.IG:1);
\r
81 (* il n'y a pas de fils droit *)
\r
85 (* il n'y a pas de fils milieu *)
\r
92 unit reorganiser : procedure(inout courant,bidon : noeud);
\r
94 if courant.FG =/= none
\r
96 (* courant a 1, 2 ou 3 fils *)
\r
97 if courant.FG.FG =/= none
\r
99 (* courant a 2 ou 3 petits fils *)
\r
100 (* appel de la procedure reorganiser avec le fils gauche *)
\r
101 call reorganiser(courant.FG, bidon);
\r
102 (* appel de la procedure reorganiser avec le fils milieu *)
\r
103 call reorganiser(courant.FM, bidon);
\r
104 if courant.FD =/= none
\r
106 (* courant a 3 fils *)
\r
107 (* appel de la procedure reorganiser avec le fils droit *)
\r
108 call reorganiser(courant.FD, bidon);
\r
111 (* recherche du plus grand element dans le sous arbre
\r
112 gauche de courant pour recuperer le IG de courant *)
\r
113 bidon := courant.FG;
\r
116 when 0 : courant.IG := bidon.IG;
\r
118 when 1 : bidon := bidon.FG;
\r
120 when 2 : bidon := bidon.FM;
\r
122 when 3 : bidon := bidon.FD;
\r
126 (* recherche du plus grand element dans le sous arbre
\r
127 du milieu de courant pour recuperer le IM de courant *)
\r
128 bidon := courant.FM;
\r
131 when 0 : courant.IM := bidon.IG;
\r
133 when 1 : bidon := bidon.FG;
\r
135 when 2 : bidon := bidon.FM;
\r
137 when 3 : bidon := bidon.FD;
\r
141 (* courant n'a pas de petis fils *)
\r
142 (* recuperation de IG pour courant *)
\r
143 courant.IG := courant.FG.IG;
\r
144 if courant.nb =/= 1
\r
146 (* recuperation de IM pour courant *)
\r
147 (* courant a 2 ou 3 fils *)
\r
148 courant.IM := courant.FM.IG;
\r
154 Unit vide : function : boolean;
\r
156 result := (racine.nb = 0);
\r
159 Unit minimum : function : integer;
\r
160 var courant : noeud;
\r
164 if courant.FG = none
\r
166 (* result contient le plus petit element de l'arbre *)
\r
167 result := courant.IG;
\r
170 (* descendre a gauche *)
\r
171 courant := courant.FG;
\r
176 Unit maximum : function : integer;
\r
177 var courant : noeud;
\r
181 (* suivant le nombre de fils de courant *)
\r
183 when 0 : (* result contient le plus grand element de l'arbre *)
\r
184 result := courant.IG;
\r
186 when 1 : (* le plus grand element se trouve
\r
187 dans le sous arbre de gauche *)
\r
188 courant := courant.FG;
\r
190 when 2 : (* le plus grand element se trouve
\r
191 dans le sous arbre du milieu *)
\r
192 courant := courant.FM;
\r
194 when 3 : (* le plus grand element se trouve
\r
195 dans le sous arbre de droite *)
\r
196 courant := courant.FD;
\r
201 unit present : function(v : integer; inout courant : noeud) : boolean;
\r
204 (* suivant le nombre de fils de courant *)
\r
206 when 0 : (* 0 fils donc c'est une feuille *)
\r
208 then result := true;
\r
209 else result := false;
\r
212 when 1 : (* 1 fils donc le pere est la racine *)
\r
213 courant := courant.FG;
\r
215 then result := true;
\r
216 else result := false;
\r
219 when 2 : (* 2 fils *)
\r
222 (* v se trouve a gauche, si il existe *)
\r
223 courant := courant.FG;
\r
227 if courant.nb =/= 0
\r
229 courant := courant.FG;
\r
232 (* v ne se trouve pas a gauche, si il existe *)
\r
235 (* v se trouve au milieu, si il existe *)
\r
236 courant := courant.FM;
\r
240 if courant.nb =/= 0
\r
242 courant := courant.FM;
\r
245 courant := courant.FM;
\r
250 when 3 : (* 3 fils *)
\r
253 (* v se trouve a gauche, si il existe *)
\r
254 courant := courant.FG;
\r
258 if courant.nb =/= 0
\r
260 courant := courant.FG;
\r
263 (* v ne se trouve pas a gauche, si il existe *)
\r
266 (* v se trouve au milieu, si il existe *)
\r
267 courant := courant.FM;
\r
271 if courant.nb =/= 0
\r
273 courant := courant.FM;
\r
276 (* v ne se trouve pas a gauche, si il existe *)
\r
279 (* v se trouve a droite, si il existe *)
\r
280 courant := courant.FD;
\r
294 unit supprimer : function(v: integer) : barbre;
\r
295 var courant, p : noeud,
\r
300 if present(v, courant)
\r
302 (* l'element est present dans l'arbre donc on peut le supprimer *)
\r
306 (* p pointe sur la racine *)
\r
308 when 1 : (* p a 1 fils *)
\r
310 courant.FG := none;
\r
314 when 2 : (* p a 2 fils *)
\r
315 if p.FG.IG = courant.IG
\r
323 when 3 : (* p a 3 fils *)
\r
324 if p.IG = courant.IG
\r
331 if p.FM.IG = courant.IG
\r
341 (* p ne pointe pas sur le racine *)
\r
343 when 2 : (* p a 2 fils *)
\r
344 writeln("Le cas ou l'on veut supprimer une feuille");
\r
345 writeln("dont le pere a 2 fils n'a pas ete gere.");
\r
347 when 3 : (* p a 3 fils *)
\r
348 if p.FG.IG = courant.IG
\r
355 if p.FM.IG = courant.IG
\r
367 writeln("On ne peut pas supprimer cet element");
\r
368 writeln("car il n'est pas dans l'arbre");
\r
370 b.racine := racine;
\r
374 unit inserer : function(v : integer) : barbre;
\r
376 unit refaire : procedure(inout p, f1, f2, j, r : noeud);
\r
378 (* suivant le nombre de fils de p *)
\r
380 when 3 : (* p a 3 fils *)
\r
389 when 4 : (* p a 4 fils *)
\r
390 (* et creer un nouveau noeud *)
\r
416 (* le pere de p n'est pas la racine *)
\r
417 (* il faut repeter la procedure refaire *)
\r
419 p.pere.nb := p.pere.nb + 1;
\r
420 call refaire(p.pere, p, j, j, r);
\r
422 (* le pere de p est la racine *)
\r
423 (* donc il faut creer une nouvelle racine *)
\r
436 var bidon, courant, i, f1, f2, j, p, r : noeud,
\r
442 bidon := new noeud;
\r
443 courant := new noeud;
\r
453 (* l'arbre est vide *)
\r
454 (* creer la feuille qui contiendra l'element a inserer *)
\r
455 courant := new noeud;
\r
456 courant.pere := racine;
\r
460 racine.FG := courant;
\r
462 b.racine := racine;
\r
466 (* l'arbre n'est pas vide *)
\r
468 if present(v,courant)
\r
470 writeln("L'element ne peut etre inserer puisqu'il appartient deja a l'arbre.");
\r
472 (* l'element n'existe pas dans l'arbre *)
\r
479 i.pere := courant.pere;
\r
482 (* creer le noeud qui contiendra l'element a inserer *)
\r
483 courant := new noeud;
\r
488 (* determination de la position ou inserer l'element *)
\r
510 (* suivant le nombre de fils de p *)
\r
512 when 2 : (* p a 2 fils *)
\r
513 if courant.IG > i.IG
\r
514 then pos := pos + 1;
\r
517 (* suivant la position de l'element *)
\r
519 when 1 : p.FM := p.FG;
\r
521 when 2 : p.FM := courant;
\r
523 when 3 : (* p a 3 fils *)
\r
524 if courant.IG > i.IG
\r
525 then pos := pos + 1;
\r
528 (* suivant la position de l'element *)
\r
530 when 1 : p.FD := p.FM;
\r
533 when 2 : p.FD := p.FM;
\r
535 when 3 : p.FD := courant;
\r
537 when 4 : (* p a 4 fils *)
\r
538 if courant.IG > i.IG
\r
539 then pos := pos + 1;
\r
545 (* suivant la position de l'element *)
\r
547 when 1 : f1 := p.FM;
\r
553 when 2 : f1 := p.FM;
\r
558 when 3 : f1 := courant;
\r
562 when 4 : f1 := p.FD;
\r
580 (* il faut repeter la procedure refaire *)
\r
582 p.pere.nb := p.pere.nb + 1;
\r
583 call refaire(p.pere, p, j, j, r);
\r
585 (* p est la racine *)
\r
586 (* donc il faut creer une nouvelle racine *)
\r
599 b.racine := courant;
\r
605 racine := new noeud;
\r
611 bidon, courant, a, b : noeud,
\r
616 courant := new noeud;
\r
617 courant := ba.racine;
\r
620 (* affichage du menu *)
\r
625 writeln("1 -> ajouter un element :");
\r
626 writeln("2 -> supprimer un element :");
\r
627 writeln("3 -> existence d'un element ? :");
\r
628 writeln("4 -> minimum de l'arbre :");
\r
629 writeln("5 -> maximum de l'arbre :");
\r
630 writeln("6 -> arbre vide ? :");
\r
631 writeln("7 -> afficher l'arbre :");
\r
632 writeln("8 -> fin.");
\r
637 writeln("-------------------------------------------");
\r
640 (* selon le choix *)
\r
642 when 1 : (* inserer un element *)
\r
643 write(" element = ");
\r
646 courant := ba.racine;
\r
647 ba := ba.inserer(e);
\r
648 courant := ba.racine;
\r
649 call ba.reorganiser(courant, bidon);
\r
652 when 2 : (* supprimer un element *)
\r
655 writeln("L'arbre est vide. Impossible de faire supprimer.");
\r
657 write(" element = ");
\r
660 courant := ba.racine;
\r
661 ba := ba.supprimer(e);
\r
662 courant := ba.racine;
\r
663 call ba.reorganiser(courant, bidon);
\r
667 when 3 : (* determiner si l'element est present dans l'arbre *)
\r
670 writeln("L'arbre est vide. Impossible de faire present.");
\r
672 write(" element = ");
\r
675 courant := ba.racine;
\r
676 if ba.present(e,courant)
\r
678 writeln(" -> present");
\r
680 writeln(" -> absent");
\r
684 when 4 : (* determiner l'element minimum *)
\r
687 writeln("L'arbre est vide. Impossible de faire minimum.");
\r
689 writeln(" minimum = ", ba.minimum);
\r
692 when 5 : (* determiner l'element maximum *)
\r
695 writeln("L'arbre est vide. Impossible de faire maximum.");
\r
697 writeln(" maximum = ", ba.maximum);
\r
700 when 6 : (* determiner si l'arbre est vide *)
\r
701 if ba.vide then writeln(" -> vide");
\r
702 else writeln(" -> pas vide");
\r
705 when 7 : (* affichage de l'arbre *)
\r
708 writeln("L'arbre est vide.");
\r
710 courant := ba.racine;
\r
711 call ba.afficher(courant);
\r
714 when 8 : (* fin du programme *)
\r