4.2 Application : types récursifs

Une classe est définie récursivement, ou est récursive, si l'un de ses champs a pour type cette classe. Plus généralement, on peut définir un ensemble de types mutuellement récursifs, de façon analogue aux fonctions mutuellement récursives. Cet auto-référencement est permis précisément parce que

• la valeur du champ est une référence à un objet et non l'objet lui-même ;
• une référence peut être nulle (null).

Les listes, les arbres et les expressions sont des exemples classiques de types récursifs. Voici la définition récursive des arbres binaires étiquetés, qu'on appelera arbres par la suite : un arbre est soit l'arbre vide, soit formé d'une étiquette et de deux arbres, appelés fils gauche et fils droit. Nous supposons pour l'instant que l'étiquette est un entier. Un exemple d'arbre est représenté sur la figure .

Figure: Un arbre binaire étiqueté.

Une traduction possible de cette définition mathématique en une classe est la suivante, qui définit un arbre comme composé d'une étiquette et de deux arbres :

package structures;

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

Figure: Un arbre à un nud new ArbreBinaire(5, null, null) ; un arbre à trois nuds.

L'arbre vide est représenté par la valeur null, et un arbre non-vide est créé à l'aide du constructeur ArbreBinaire ; par exemple, l'arbre de la figure  peut ainsi être construit par :

  ArbreBinaire c = 
    new ArbreBinaire(1, 
      new ArbreBinaire(2, 
        new ArbreBinaire(4, 
          null, 
          new ArbreBinaire(8, null, null)),
      new ArbreBinaire(5, null, null)),
    new ArbreBinaire(3,
      new ArbreBinaire(6,
        new ArbreBinaire(9, null, null),
        new ArbreBinaire(10,
          new ArbreBinaire(12, null, null),
          new ArbreBinaire(13, null, null))),
      new ArbreBinaire(7,
        new ArbreBinaire(11, null, null),
        null)));

Cette représentation des arbres est correcte et commode mais a un défaut : alors que les arbres non vides sont des instances de ArbreBinaire, l'arbre vide n'est pas un objet. Par suite, on ne peut pas définir de méthode d'instance pour tester le fait qu'un arbre soit vide. On ne peut que recourir au test d'égalité à null. L'utilisation d'un type abstrait permettra d'y remédier.