Exemple : arbres et types abstraits

Voici une utilisation d'une interface et du sous-typage pour représenter tous les arbres, même l'arbre vide, par des objets. On commence par définir un type abstrait ArbreBinaire, puis deux sous-types concrets, un pour les arbres non-vides, et un pour les arbres vides :

interface ArbreBinaire {
  boolean estVide();
}

class AVide implements ArbreBinaire {
  public boolean estVide() {
    return true;
  }
}

class ACons implements ArbreBinaire {
  int étiquette;
  ArbreBinaire gauche, droit;

  ACons(int étiquette, 
        ArbreBinaire gauche, 
        ArbreBinaire droit) {
   this.étiquette = étiquette;
   this.gauche = gauche;
   this.droit = droit;
  }

  public boolean estVide() {
    return false;
  }
}

On remarquera que la classe ACons n'est plus directement auto-référencée : les champs gauche et droit ne sont pas de type ACons, mais ArbreBinaire, de manière à permettre à un sous-arbre d'être vide. Une application pourra déclarer une variable a de type abstrait ArbreBinaire, et pourra l'initialiser à l'aide des constructeurs des classes concrètes :

    ArbreBinaire a = 
      new ACons(1,
                new ACons(2, new AVide(), new AVide()),
                new ACons(3, new AVide(), new AVide()));

Figure 4.4: Représentation d'un arbre binaire où l'arbre vide est un objet.

217#217

L'exécution de l'appel a.estVide() conduit à invoquer la méthode estVide de ACons, qui retourne false.