Arbres et types abstraits

Voici une utilisation d'un type abstrait 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 :

abstract class ArbreBinaire {
  abstract boolean estVide();
}

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

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

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

  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()));

 

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

La définition de la classe AVide a cependant un défaut : chaque invocation du constructeur AVide() retourne un nouvel arbre vide, et tous les arbres vides retournés sont distincts. Ce défaut peut être corrigé en interdisant l'invocation de ce constructeur (il suffit de le rendre privé), et en s'assurant de l'existence d'une unique instance de la classe (ce qui s'obtient en en faisant une variable de classe arbreVide) : ceci est un exemple de classe singleton   (voir § 3.5). Pour empêcher toute modification de cette variable, on la rend également privée et on y accède en lecture seulement par une méthode de classe val() :

class AVide extends ArbreBinaire {
  private static AVide arbreVide = new AVide();
  private AVide(){}
  static AVide val() {
    return arbreVide;
  }

  boolean estVide() {
    return true;
  }
}

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