examples/examples.old/bbarbre1.log

   1 program myBarbres;\r
   2 (* Mlles Beau et Delburg *)\r
   3         (* representation d'un noeud *)\r
   4         Unit noeud : class;\r
   5         Var pere       : noeud,\r
   6                  nb         : integer,\r
   7                  IG, IM     : integer,\r
   8                  FG, FM, FD : noeud;\r
   9                  (* \r
  10                          pere est le pere\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
  17                  *)\r
  18         begin\r
  19                 (* initialisation des variables *)\r
  20                 pere := none;\r
  21                 nb := 0;\r
  22                 IG := -1;\r
  23                 IM := -1;\r
  24                 FG := none;\r
  25                 FM := none;\r
  26                 FD := none;\r
  27         end noeud;\r
  28 \r
  29 \r
  30 \r
  31         Unit barbre : class;\r
  32         Var racine : noeud;\r
  33 \r
  34                 unit afficher : procedure(inout courant : noeud);\r
  35                 begin\r
  36                         if courant.IM = -1\r
  37                         then\r
  38                                 (* courant pointe sur une feuille *)\r
  39                                 writeln(courant.IG:1);\r
  40                         else\r
  41                                 (* courant pointe sur un noeud *)\r
  42                                 writeln(courant.IG:1, ":", courant.IM:1);\r
  43                         fi;\r
  44                         \r
  45                         if courant.FG =/= none\r
  46                         then\r
  47                                 (* courant a 1, 2 ou 3 fils *)   \r
  48                                 if courant.FG.FG =/= none\r
  49                                 then\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
  54                                         then\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
  59                                                 then\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
  63                                                 fi;\r
  64                                         fi;\r
  65                                 else\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
  71                                         then\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
  76                                                 then\r
  77                                                         (* courant a 3 fils *)\r
  78                                                         (* affichage de la feuille de droite *)\r
  79                                                         writeln(" ", courant.FD.IG:1);\r
  80                                                 else\r
  81                                                         (* il n'y a pas de fils droit *)\r
  82                                                         writeln;\r
  83                                                 fi;\r
  84                                         else\r
  85                                                 (* il n'y a pas de fils milieu *)\r
  86                                                 writeln;\r
  87                                         fi;\r
  88                                 fi;\r
  89                         fi;\r
  90                 end;\r
  91 \r
  92                 unit reorganiser : procedure(inout courant,bidon : noeud);\r
  93                 begin\r
  94                                         if courant.FG =/= none\r
  95                                         then\r
  96                                                 (* courant a 1, 2 ou 3 fils *)\r
  97                                                 if courant.FG.FG =/= none\r
  98                                                 then\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
 105                                                         then\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
 109                                                         fi;\r
 110 \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
 114                                                         do\r
 115                                                                 case bidon.nb\r
 116                                                                         when 0 : courant.IG := bidon.IG;\r
 117                                                                                                 exit;\r
 118                                                                         when 1 : bidon := bidon.FG;\r
 119 \r
 120                                                                         when 2 : bidon := bidon.FM;\r
 121 \r
 122                                                                         when 3 : bidon := bidon.FD;\r
 123                                                                 esac;\r
 124                                                         od;\r
 125                                                         \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
 129                                                         do\r
 130                                                                 case bidon.nb\r
 131                                                                         when 0 : courant.IM := bidon.IG;\r
 132                                                                                                 exit;\r
 133                                                                         when 1 : bidon := bidon.FG;\r
 134 \r
 135                                                                         when 2 : bidon := bidon.FM;\r
 136 \r
 137                                                                         when 3 : bidon := bidon.FD;\r
 138                                                                 esac;\r
 139                                                         od;\r
 140                                                 else\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
 145                                                         then\r
 146                                                                 (* recuperation de IM pour courant *)\r
 147                                                                 (* courant a 2 ou 3 fils *)\r
 148                                                                 courant.IM := courant.FM.IG;\r
 149                                                         fi;\r
 150                                                 fi;\r
 151                                         fi;\r
 152                                 end reorganiser;\r
 153 \r
 154                 Unit vide : function : boolean;\r
 155                 begin\r
 156                         result := (racine.nb = 0);\r
 157                 end vide;\r
 158 \r
 159                 Unit minimum : function : integer;\r
 160                 var courant : noeud;\r
 161                 begin\r
 162                         courant := racine;\r
 163                         do\r
 164                                 if courant.FG = none\r
 165                                 then\r
 166                                         (* result contient le plus petit element de l'arbre *)\r
 167                                         result := courant.IG;\r
 168                                         exit;\r
 169                                 else\r
 170                                         (* descendre a gauche *)\r
 171                                         courant := courant.FG;\r
 172                                 fi;\r
 173                         od;\r
 174                 end minimum;\r
 175 \r
 176                 Unit maximum : function : integer;\r
 177                 var courant : noeud;\r
 178                 begin\r
 179                         courant := racine;\r
 180                         do\r
 181                                 (* suivant le nombre de fils de courant *)\r
 182                                 case courant.nb\r
 183                                         when 0 : (* result contient le plus grand element de l'arbre *)\r
 184                                                                 result := courant.IG;\r
 185                                                                 exit;\r
 186                                         when 1 : (* le plus grand element se trouve \r
 187                                                                 dans le sous arbre de gauche *)\r
 188                                                                 courant := courant.FG;\r
 189 \r
 190                                         when 2 : (* le plus grand element se trouve\r
 191                                                                 dans le sous arbre du milieu *)\r
 192                                                                 courant := courant.FM;\r
 193 \r
 194                                         when 3 : (* le plus grand element se trouve\r
 195                                                                 dans le sous arbre de droite *)\r
 196                                                                 courant := courant.FD;\r
 197                                 esac;\r
 198                         od;\r
 199                 end maximum;\r
 200          \r
 201                 unit present : function(v : integer; inout courant : noeud) : boolean;\r
 202                 begin\r
 203                         do\r
 204                                 (* suivant le nombre de fils de courant *)\r
 205                                 case courant.nb\r
 206                                         when 0 : (* 0 fils donc c'est une feuille *)\r
 207                                                                 if courant.IG = v\r
 208                                                                 then result := true;\r
 209                                                                 else result := false;\r
 210                                                                 fi;\r
 211                                                                 exit;\r
 212                                         when 1 : (* 1 fils donc le pere est la racine *)\r
 213                                                                 courant := courant.FG;\r
 214                                                                 if courant.IG = v\r
 215                                                                 then result := true;\r
 216                                                                 else result := false;\r
 217                                                                 fi;\r
 218                                                                 exit;\r
 219                                         when 2 : (* 2 fils *)\r
 220                                                                 if courant.IG > v\r
 221                                                                 then\r
 222                                                                         (* v se trouve a gauche, si il existe *) \r
 223                                                                         courant := courant.FG;\r
 224                                                                 else\r
 225                                                                         if courant.IG = v\r
 226                                                                         then\r
 227                                                                                 if courant.nb =/= 0\r
 228                                                                                 then\r
 229                                                                                         courant := courant.FG;\r
 230                                                                                 fi;\r
 231                                                                         else\r
 232                                                                                 (* v ne se trouve pas a gauche, si il existe *)\r
 233                                                                                 if courant.IM > v\r
 234                                                                                 then\r
 235                                                                                         (* v se trouve au milieu, si il existe *)\r
 236                                                                                         courant := courant.FM;\r
 237                                                                                 else\r
 238                                                                                         if courant.IM = v\r
 239                                                                                         then\r
 240                                                                                                 if courant.nb =/= 0\r
 241                                                                                                 then\r
 242                                                                                                         courant := courant.FM;\r
 243                                                                                                 fi;\r
 244                                                                                         else\r
 245                                                                                                 courant := courant.FM;\r
 246                                                                                         fi;\r
 247                                                                                 fi;\r
 248                                                                         fi;\r
 249                                                                 fi;\r
 250                                         when 3 : (* 3 fils *)\r
 251                                                                 if courant.IG > v\r
 252                                                                 then\r
 253                                                                         (* v se trouve a gauche, si il existe *)\r
 254                                                                         courant := courant.FG;\r
 255                                                                 else\r
 256                                                                         if courant.IG = v\r
 257                                                                         then\r
 258                                                                                 if courant.nb =/= 0\r
 259                                                                                 then\r
 260                                                                                         courant := courant.FG;\r
 261                                                                                 fi;\r
 262                                                                         else                            \r
 263                                                                                 (* v ne se trouve pas a gauche, si il existe *)\r
 264                                                                                 if courant.IM > v\r
 265                                                                                 then\r
 266                                                                                         (* v se trouve au milieu, si il existe *)\r
 267                                                                                         courant := courant.FM;\r
 268                                                                                 else\r
 269                                                                                         if courant.IM = v\r
 270                                                                                         then\r
 271                                                                                                 if courant.nb =/= 0\r
 272                                                                                                 then\r
 273                                                                                                         courant := courant.FM;\r
 274                                                                                                 fi;\r
 275                                                                                         else\r
 276                                                                                                 (* v ne se trouve pas a gauche, si il existe *)\r
 277                                                                                                 if courant.IM < v\r
 278                                                                                                 then \r
 279                                                                                                         (* v se trouve a droite, si il existe *)\r
 280                                                                                                         courant := courant.FD;\r
 281                                                                                                 fi;\r
 282                                                                                         fi;\r
 283                                                                                 fi;\r
 284                                                                         fi;\r
 285                                                                 fi;\r
 286                                 esac;\r
 287                         od;\r
 288                 end present;\r
 289 \r
 290 \r
 291 \r
 292 \r
 293 \r
 294                 unit supprimer : function(v: integer) : barbre;\r
 295                 var courant, p : noeud,\r
 296                          b : barbre;\r
 297                 begin\r
 298                         b := new barbre;\r
 299                         courant := racine;\r
 300                         if present(v, courant)\r
 301                         then\r
 302                                 (* l'element est present dans l'arbre donc on peut le supprimer *)\r
 303                                 p := courant.pere;\r
 304                                 if p.pere = none\r
 305                                 then\r
 306                                         (* p pointe sur la racine *)\r
 307                                         case p.nb\r
 308                                                 when 1 : (* p a 1 fils *)\r
 309                                                                         courant := p;\r
 310                                                                         courant.FG := none;\r
 311                                                                         courant.nb := 0;\r
 312                                                                         courant.IG := -1;\r
 313 \r
 314                                                 when 2 : (* p a 2 fils *)\r
 315                                                                         if p.FG.IG = courant.IG\r
 316                                                                         then\r
 317                                                                                 p.FG := p.FM;\r
 318                                                                                 p.IG := p.FG.IG;\r
 319                                                                         fi;\r
 320                                                                         p.FM := none;\r
 321                                                                         p.nb := p.nb - 1;\r
 322                                                                         p.IM := -1;\r
 323                                                 when 3 : (* p a 3 fils *)\r
 324                                                                         if p.IG = courant.IG\r
 325                                                                         then\r
 326                                                                                 p.FG := p.FM;\r
 327                                                                                 p.FM := p.FD;\r
 328                                                                                 p.IG := p.FG.IG;\r
 329                                                                                 p.IM := p.FM.IG;\r
 330                                                                         else\r
 331                                                                                 if p.FM.IG = courant.IG\r
 332                                                                                 then\r
 333                                                                                         p.FM := p.FD;\r
 334                                                                                         p.IM := p.FM.IG;\r
 335                                                                                 fi;\r
 336                                                                         fi;\r
 337                                                                         p.FD := none;\r
 338                                                                         p.nb := p.nb - 1;\r
 339                                         esac;\r
 340                                 else\r
 341                                         (* p ne pointe pas sur le racine *)\r
 342                                         case p.nb\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
 346                                                 \r
 347                                                 when 3 : (* p a 3 fils *)\r
 348                                                                         if p.FG.IG = courant.IG\r
 349                                                                         then\r
 350                                                                                 p.FG := p.FM;\r
 351                                                                                 p.FM := p.FD;\r
 352                                                                                 p.IG := p.FG.IG;\r
 353                                                                                 p.IM := p.FM.IG;\r
 354                                                                         else\r
 355                                                                                 if p.FM.IG = courant.IG\r
 356                                                                                 then\r
 357                                                                                         p.FM := p.FD;\r
 358                                                                                         p.IM := p.FM.IG;\r
 359                                                                                 fi;\r
 360                                                                         fi;\r
 361                                                                                 \r
 362                                                                         p.FD := none;\r
 363                                                                         p.nb := p.nb - 1 ;\r
 364                                         esac;\r
 365                                 fi;\r
 366                         else\r
 367                                 writeln("On ne peut pas supprimer cet element"); \r
 368                                 writeln("car il n'est pas dans l'arbre");\r
 369                         fi;\r
 370                         b.racine := racine;\r
 371                         result := b;\r
 372                 end supprimer;\r
 373 \r
 374                 unit inserer : function(v : integer) : barbre;\r
 375 \r
 376                         unit refaire : procedure(inout p, f1, f2, j, r : noeud);\r
 377                         begin\r
 378                                 (* suivant le nombre de fils de p *)\r
 379                                 case p.nb\r
 380                                         when 3 : (* p a 3 fils *)\r
 381                                                                 if p.FG = f1\r
 382                                                                 then\r
 383                                                                         p.FD := p.FM;\r
 384                                                                         p.FM := j;\r
 385                                                                 else\r
 386                                                                         p.FD := j;\r
 387                                                                 fi;\r
 388 \r
 389                                         when 4 : (* p a 4 fils *)\r
 390                                                                 (* et creer un nouveau noeud *)\r
 391                                                                 j := new noeud;\r
 392                                                                 if p.FG = f1\r
 393                                                                 then\r
 394                                                                         j.FG := p.FM;\r
 395                                                                         j.FM := p.FD;\r
 396                                                                         p.FM := f2;\r
 397                                                                 else\r
 398                                                                         if p.FM = f1\r
 399                                                                         then\r
 400                                                                                 j.FG := f2;\r
 401                                                                                 j.FM := p.FD;\r
 402                                                                         else\r
 403                                                                                 j.FG := f1;\r
 404                                                                                 j.FM := f2;\r
 405                                                                         fi;\r
 406                                                                 fi;\r
 407                                                                                                 \r
 408                                                                 j.FG.pere := j;\r
 409                                                                 j.FM.pere := j;\r
 410                                                                 j.nb := 2;\r
 411                                                                 p.FD := none;\r
 412                                                                 p.nb := 2;\r
 413                                                                                                 \r
 414                                                                 if p.pere =/= none\r
 415                                                                 then\r
 416                                                                         (* le pere de p n'est pas la racine *)\r
 417                                                                         (* il faut repeter la procedure refaire *)\r
 418                                                                         j.pere := p.pere;\r
 419                                                                         p.pere.nb := p.pere.nb + 1;\r
 420                                                                         call refaire(p.pere, p, j, j, r);\r
 421                                                                 else\r
 422                                                                         (* le pere de p est la racine *)\r
 423                                                                         (* donc il faut creer une nouvelle racine *)\r
 424                                                                         r := new noeud;\r
 425                                                                         r.nb := 2;\r
 426                                                                         r.FG := p;\r
 427                                                                         r.FM := j;\r
 428                                                                         p.pere := r;\r
 429                                                                         j.pere := r;\r
 430                                                                         racine := r;\r
 431                                                                 fi;\r
 432                                 esac;\r
 433                         end refaire;\r
 434 \r
 435 \r
 436                 var bidon, courant, i, f1, f2, j, p, r : noeud,\r
 437                          b : barbre,\r
 438                          pos : integer;\r
 439                 begin\r
 440                         b := new barbre;\r
 441 \r
 442                         bidon := new noeud;\r
 443                         courant := new noeud;\r
 444                         r := new noeud;\r
 445                         i:= new noeud;\r
 446                         f1 := new noeud;\r
 447                         f2 := new noeud;\r
 448                         j := new noeud;\r
 449                         p:= new noeud;\r
 450 \r
 451                         if vide\r
 452                         then\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
 457                                 courant.IG := v;\r
 458                                 racine.IG := v;\r
 459                                 racine.nb := 1;\r
 460                                 racine.FG := courant;\r
 461 \r
 462                                 b.racine := racine;\r
 463                                 result := b;\r
 464 \r
 465                         else\r
 466                                 (* l'arbre n'est pas vide *)\r
 467                                 courant := racine;\r
 468                                 if present(v,courant)\r
 469                                 then\r
 470                                         writeln("L'element ne peut etre inserer puisqu'il appartient deja a l'arbre.");\r
 471                                 else\r
 472                                         (* l'element n'existe pas dans l'arbre *)\r
 473                                         \r
 474                                         pos := 0;\r
 475 \r
 476                                         i := new noeud;\r
 477                                         p := new noeud;\r
 478                                         i := courant;\r
 479                                         i.pere := courant.pere;\r
 480                                         p := courant.pere;\r
 481 \r
 482                                         (* creer le noeud qui contiendra l'element a inserer *)\r
 483                                         courant := new noeud;\r
 484                                         courant.IG := v;\r
 485                                         courant.pere := p;\r
 486                                         p.nb := p.nb + 1;\r
 487 \r
 488                                         (* determination de la position ou inserer l'element *)\r
 489                                         if i.IG = p.FG.IG\r
 490                                         then\r
 491                                                 pos := 1;\r
 492                                         else\r
 493                                                 if p.FM =/= none\r
 494                                                 then\r
 495                                                         if i.IG = p.FM.IG\r
 496                                                         then\r
 497                                                                 pos := 2;\r
 498                                                         else\r
 499                                                                 if p.FD =/= none\r
 500                                                                 then\r
 501                                                                         if i.IG = p.FD.IG\r
 502                                                                         then\r
 503                                                                                 pos := 3;\r
 504                                                                         fi;\r
 505                                                                 fi;\r
 506                                                         fi;\r
 507                                                 fi;\r
 508                                         fi;\r
 509 \r
 510                                         (* suivant le nombre de fils de p *)\r
 511                                         case p.nb\r
 512                                                 when 2 : (* p a 2 fils *)\r
 513                                                                         if courant.IG > i.IG\r
 514                                                                         then pos := pos + 1;\r
 515                                                                         fi;\r
 516                                                                         \r
 517                                                                         (* suivant la position de l'element *)\r
 518                                                                         case pos\r
 519                                                                                 when 1 : p.FM := p.FG;\r
 520                                                                                                         p.FG := courant;\r
 521                                                                                 when 2 : p.FM := courant;\r
 522                                                                         esac;\r
 523                                                 when 3 : (* p a 3 fils *)\r
 524                                                                         if courant.IG > i.IG\r
 525                                                                         then pos := pos + 1;\r
 526                                                                         fi;\r
 527                                                                         \r
 528                                                                         (* suivant la position de l'element *)\r
 529                                                                         case pos\r
 530                                                                                 when 1 : p.FD := p.FM;\r
 531                                                                                                         p.FM := p.FG;\r
 532                                                                                                         p.FG := courant;\r
 533                                                                                 when 2 : p.FD := p.FM;\r
 534                                                                                                         p.FM := courant;\r
 535                                                                                 when 3 : p.FD := courant;\r
 536                                                                         esac;\r
 537                                                 when 4 : (* p a 4 fils *)\r
 538                                                                         if courant.IG > i.IG\r
 539                                                                         then pos := pos + 1;\r
 540                                                                         fi;\r
 541 \r
 542                                                                         f1 := new noeud;\r
 543                                                                         f2 := new noeud;\r
 544                                                                         \r
 545                                                                         (* suivant la position de l'element *)\r
 546                                                                         case pos\r
 547                                                                                 when 1 : f1 := p.FM;\r
 548                                                                                                         f2 := P.FD;\r
 549                                                                                                         p.FD := none;\r
 550                                                                                                         p.FM := p.FG;\r
 551                                                                                                         p.FG := courant;\r
 552                                                                                                         (**)\r
 553                                                                                 when 2 : f1 := p.FM;\r
 554                                                                                                         f2 := p.FD;\r
 555                                                                                                         p.FD := none;\r
 556                                                                                                         p.FM := courant;\r
 557                                                                                                         (**)\r
 558                                                                                 when 3 : f1 := courant;\r
 559                                                                                                         f2 := p.FD;\r
 560                                                                                                         p.FD := none;\r
 561                                                                                                         (**)\r
 562                                                                                 when 4 : f1 := p.FD;\r
 563                                                                                                         f2 := courant;\r
 564                                                                                                         p.FD := none;\r
 565                                                                                                         (**)\r
 566                                                                         esac;\r
 567 \r
 568                                                                         j := new noeud;\r
 569 \r
 570                                                                         j.FG := f1;\r
 571                                                                         j.FM := f2;\r
 572                                                                         j.FG.pere := j;\r
 573                                                                         j.FM.pere := j;\r
 574                                                                         j.nb := 2;\r
 575                                                                         p.nb := 2;\r
 576 \r
 577                                                                         if p.pere =/= none\r
 578                                                                         then\r
 579                                                                                 (* p a un pere *)\r
 580                                                                                 (* il faut repeter la procedure refaire *)\r
 581                                                                                 j.pere := p.pere;\r
 582                                                                                 p.pere.nb := p.pere.nb + 1;\r
 583                                                                                 call refaire(p.pere, p, j, j, r);\r
 584                                                                         else\r
 585                                                                                 (* p est la racine *)\r
 586                                                                                 (* donc il faut creer une nouvelle racine *)\r
 587                                                                                 r := new noeud;\r
 588                                                                                 r.nb := 2;\r
 589                                                                                 r.FG := p;\r
 590                                                                                 r.FM := j;\r
 591                                                                                 p.pere := r;\r
 592                                                                                 j.pere := r;\r
 593                                                                                 racine := r;\r
 594                                                                         fi;\r
 595                                         esac;\r
 596                                 fi;\r
 597 \r
 598                                 courant := racine;\r
 599                                 b.racine := courant;\r
 600                                 result := b;\r
 601                         fi;\r
 602                 end inserer;\r
 603 \r
 604         begin\r
 605                 racine := new noeud;\r
 606         end barbre;\r
 607 \r
 608 \r
 609 var ba : barbre,\r
 610          e : integer,\r
 611          bidon, courant, a, b : noeud,\r
 612          choix : integer;\r
 613 \r
 614 begin\r
 615         ba := new barbre;\r
 616         courant := new noeud;\r
 617         courant := ba.racine;\r
 618 \r
 619         do\r
 620                 (* affichage du menu *)\r
 621                 writeln;\r
 622                 writeln;\r
 623                 writeln;\r
 624                 writeln;\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
 633 \r
 634                 write("choix =");\r
 635                 read(choix);\r
 636                 writeln;\r
 637                 writeln("-------------------------------------------");\r
 638                 writeln;\r
 639                 \r
 640                 (* selon le choix *)\r
 641                 case choix\r
 642                         when 1 : (* inserer un element *)\r
 643                                                 write("          element = ");\r
 644                                                 read(e);\r
 645 \r
 646                                                 courant := ba.racine;\r
 647                                                 ba := ba.inserer(e);\r
 648                                                 courant := ba.racine;\r
 649                                                 call ba.reorganiser(courant, bidon);\r
 650                                                 writeln;\r
 651 \r
 652                         when 2 : (* supprimer un element *)\r
 653                                                 if ba.vide\r
 654                                                 then\r
 655                                                         writeln("L'arbre est vide. Impossible de faire supprimer.");\r
 656                                                 else\r
 657                                                         write("          element = ");\r
 658                                                         read(e);\r
 659                                                         \r
 660                                                         courant := ba.racine;\r
 661                                                         ba := ba.supprimer(e);\r
 662                                                         courant := ba.racine;\r
 663                                                         call ba.reorganiser(courant, bidon);\r
 664                                                         writeln;\r
 665                                                 fi;\r
 666 \r
 667                         when 3 : (* determiner si l'element est present dans l'arbre *)\r
 668                                                 if ba.vide\r
 669                                                 then\r
 670                                                         writeln("L'arbre est vide. Impossible de faire present.");\r
 671                                                 else\r
 672                                                         write("          element = ");\r
 673                                                         read(e);\r
 674                                                         writeln;\r
 675                                                         courant := ba.racine;\r
 676                                                         if ba.present(e,courant)\r
 677                                                         then\r
 678                                                                 writeln("          -> present");\r
 679                                                         else\r
 680                                                                 writeln("          -> absent");\r
 681                                                         fi;\r
 682                                                 fi;\r
 683 \r
 684                         when 4 : (* determiner l'element minimum *)\r
 685                                                 if ba.vide\r
 686                                                 then\r
 687                                                         writeln("L'arbre est vide. Impossible de faire minimum.");\r
 688                                                 else\r
 689                                                         writeln("         minimum = ", ba.minimum);\r
 690                                                 fi;\r
 691 \r
 692                         when 5 : (* determiner l'element maximum *)\r
 693                                                 if ba.vide\r
 694                                                 then\r
 695                                                         writeln("L'arbre est vide. Impossible de faire maximum.");\r
 696                                                 else\r
 697                                                         writeln("         maximum = ", ba.maximum);\r
 698                                                 fi;\r
 699 \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
 703                                                 fi;\r
 704                         \r
 705                         when 7 : (* affichage de l'arbre *)\r
 706                                                 if ba.vide\r
 707                                                 then\r
 708                                                         writeln("L'arbre est vide.");\r
 709                                                 else\r
 710                                                         courant := ba.racine;\r
 711                                                         call ba.afficher(courant);\r
 712                                                 fi;\r
 713 \r
 714                         when 8 : (* fin du programme *)\r
 715                                                 exit;\r
 716                 esac;\r
 717          od;\r
 718 end mybarbre.\r
 719 \r
 720 \r