Arbres

Les listes, les arbres et les expressions d'un langage 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 4.2.

215#215

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;
  }
}

216#216

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 4.2 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 de remédier à ce défaut.