Cette section est largement inspirée du cours de René Lallement à l'Ecole Nationale des Ponts et Chaussées.

Introduction

Nous allons traiter ici l'exemple des arbres binaires, en illustrant leur utilisation pour représenter une expression arithmétique.
Ainsi à l'expression artihmétique parenthésée

((a + (b * c) + (5 * d)) / ((4 * a) -c )) + f

on associe classiquement l'arbre binaire :

On souhaite représenter de telles arbres en vue de leur manipulation, par exemple pour en permettre des parcours, ce qui dans le cas de l'arbre associé à une expression arithmétique permet par exemple d'en produire des représentations (polonaises) pré/post-fixéess.
Une représentation classique de tels arbres repose sur la définition récursive qu'on peut en donner : un arbre est formé d'un noeud racine étiqueté et de deux sous-arbres éventuellement vides.

Une première représentation

La définition récursive appliquée brutalement conduit à la première définition d'un arbre binaire correspondant à la classe ArbreBin1 suivante


   --> cat ArbreBin1.java
   class ArbreBin1 {
      String etiquette;      // l'étiquette de la racine de l'arbre
      ArbreBin1 arbreGauche; // référence du sous-arbre gauche
      ArbreBin1 arbreDroit;  // référence du sous-arbre droit
      ArbreBin1(String etiquette, ArbreBin1 gauche, ArbreBin1 droit) {    
         this.etiquette = etiquette;
         arbreGauche = gauche;
         arbreDroit = droit;
         }
   }

L'arbre vide n'a pas de représentation dans cette classe ArbreBin1 : il correspond à une référence non définie (valeur null).
La classe ArbreBin1DeLexpression ne fait que construire »en dur», au travers de son constructeur, l'arbre particulier associé à l'expression donnée en exemple .
L'arbre étant associé à une variable privée de la classe, une méthode getArbre est fournie pour accéder en lecture à cette arbre :


   --> cat ArbreBin1DeLexpression.java
   class ArbreBin1DeLexpression {
      private ArbreBinaire1 arbre;
      ArbreBin1DeLexpression( ){
         arbre =
         new ArbreBinaire1("+",
            new ArbreBinaire1("/",
               new ArbreBinaire1("+",
                  new ArbreBinaire1("+",
                     new ArbreBinaire1("a", null, null),
                     new ArbreBinaire1("*",
                        new ArbreBinaire1("b", null, null),     
                        new ArbreBinaire1("c", null, null)
                     )
                  ),
                  new ArbreBinaire1("*",
                     new ArbreBinaire1("5", null, null),
                     new ArbreBinaire1("d", null, null)
                  )
               ),
               new ArbreBinaire1("-",
                  new ArbreBinaire1("*",
                     new ArbreBinaire1("4", null, null),
                     new ArbreBinaire1("a", null, null)
                  ),
                  new ArbreBinaire1("c", null, null)
               )
            ),
            new ArbreBinaire1("f", null, null)
         );
      }   // fin du constructeur
      ArbreBin1 getArbre(){ // pour accéder à l'arbre
         return arbre;
      }                    
   }

Nous ajoutons dans la classe ArbreBin1 une méthode prefixe réalisant le parcours préfixe de l'arbre sur lequel elle est invoquée, avec impression des étiquettes des noeuds rencontrés dans ce parcours (c'est-à-dire la première fois qu'on y passe) :


   void prefixe(){
      System.out.print(etiquette + " ");    
      if (arbreGauche != null)
         arbreGauche.prefixe();
      if (arbreDroit != null)
         arbreDroit.prefixe();

      }

Enfin l'application correspondant à la classe Main1, après avoir instancié la classe ArbreBin1DeLexpression, applique à l'arbre obtenu la méthode prefixe :


   --> cat Main1.java
   class Main1 {
      public static void main(String[] arg) {
         ArbreBin1DeLexpression arbre = new ArbreBin1DeLexpression();    
         arbre.getArbre().prefixe();
      }
   }  
   --> java Main1
   + / + + a * b c * 5 d - * 4 a c f    // forme préfixée de l'expression    
   -->

Une seconde représentation intégrant l'arbre vide

L'objectif est d'intégrer l'arbre vide dans la famille des arbres binaires, ce qui autorisera en particulier la définition d'une méthode permettant de tester si un arbre est vide ou non.

Pour cela, on va définir une classe abstraite qui contient deux méthodes abstraites estVide et prefixe :


   --> cat ArbreBinaire.java
   abstract class ArbreBinaire {    
     abstract boolean estVide();
     abstract void prefixe();
   }

Cette classe est spécialisée en deux classes concrètes qui implantent la méthode abstraite estVide.

Les deux classes concrètes doivent donc implanter les deux méthodes estVide et prefixe :

Dans la première, appelée ArbreVide1, la méthode estVide renvoie toujours la valeur true et la méthode prefixe ne fait rien.
Sa définition est donc :


   --> cat ArbreVide1.java
   class ArbreVide1 extends ArbreBinaire {     
     boolean estVide() {
       return true;
     }
     public void prefixe() {}
   }

la seconde classe correspond à la définition d'un arbre non vide, c'est-à-dire possédant une racine et deux sous-arbres.
La méthode estVide renvoie toujours la valeur false
La classe comporte des variables d'instance qui permettent d'accéder à l'étiquette de la racine et aux deux sous-arbres. Il est bien clair que les deux sous-arbres peuvent être vides ou non et donc que les variables associés doivent permettre de référencer l'un ou l'autre de ces types d'arbres : c'est la raison pour laquelle, le type utilisé pour les variables d'insstance ou les paramètres du constructeur est ArbreBinaire.
Rappelons que la classe abstraite n'est pas instanciable en tant que telle mais que les instanciations se feront au travers de constructeurs des classes concrètes ArbreVide1 et ArbreNonVide, les références étant affectées à ces variables d'instance. Le mécanisme de transtypage vers le haut autorise l'affectation de références vers une variable de référence de la classe abstraite puisque les deux classes concrètes en dérivent.
Par ailleurs le mécanisme de liaison tardive permettra de sélectionner, lors d'une invocation de la méthode estVide pour une référence sur la classe ArbreBinaire, la méthode adaptée à la classe réelle (soit ArbreVide1, soit ArbreNonVide) de l'objet référencé.


   --> cat ArbreNonVide.java
   class ArbreNonVide extends ArbreBinaire {    
      String etiquette;
      ArbreBinaire arbreGauche, arbreDroit;
      ArbreNonVide(String etiquette,
                   ArbreBinaire gauche,
                   ArbreBinaire droit) {
        this.etiquette = etiquette;
        arbreGauche = gauche;
        arbreDroit = droit;
      }
      void prefixe(){
         if (! estVide()){
            System.out.print(etiquette + " ");
            arbreGauche.prefixe();
            arbreDroit.prefixe();
            }
      }
      boolean estVide() {
          return false;
      }
   }

Une représentation avec un arbre vide unique

Une critique qu'on peut formuler relativement à l'implantation précédente, et plus particulièrement à l'implantation de l'arbre vide, est que chacune de ses instanciations crée effectivement un nouvel objet et donc une nouvelle référence, ce qui est inutile puisque l'objet ne contient aucune information et n'est pas modifiable.
D'où l'idée de n'autoriser qu'une seule instance de la classe, ce qu'on appelle traditionnellement classe singleton.

Une première solution

Elle consiste à :

définir une variable de classe (c'est-à-dire static) initialisée par appel du constructeur par défaut ;
rendre privé (private) ce constructeur afin qu'il ne soit pas appelable de l'extérieur de la classe
fournir une méthode de classe (donc static) qui est ici appelée get et qui renvoie la référence de la variable de classe référençant l'arbre vide unique.

Avec cette solution, dont le code est donné ci-après, le singleton est créé au chargement de la classe indépendamment du fait que la méthode get permettant d'accéder à cette instance unique soit invoquée :


   --> cat ArbreVide.java
   class ArbreVide extends ArbreBinaire {    
      private static ArbreVide arbreVide = new ArbreVide();
      private ArbreVide() {}
      static ArbreVide get() {
         return arbreVide;
      }
      public void prefixe() {}
      boolean estVide() {
         return true;
      }
   }

Le code permettant l'instanciation de l'arbre associé à l'expression et un programme réalisant son parcours préfixe sont donnés ci-après :


   --> cat ArbreBinDeLexpression.java
   class ArbreBinDeLexpression {
      private ArbreBinaire arbre;
      ArbreBinDeLexpression( ){
         arbre =
         new ArbreNonVide("+",
            new ArbreNonVide("/",
               new ArbreNonVide("+",
                  new ArbreNonVide("+",
                     new ArbreNonVide("a", ArbreVide.get(), ArbreVide.get()),
                     new ArbreNonVide("*",
                        new ArbreNonVide("b", ArbreVide.get(), ArbreVide.get()) ,    
                        new ArbreNonVide("c", ArbreVide.get(),  ArbreVide.get())
                     )
                  ),
                  new ArbreNonVide("*",
                     new ArbreNonVide("5", ArbreVide.get(), ArbreVide.get()),
                     new ArbreNonVide("d", ArbreVide.get(), ArbreVide.get())
                  )
               ),
               new ArbreNonVide("-",
                  new ArbreNonVide("*",
                     new ArbreNonVide("4", ArbreVide.get(), ArbreVide.get()), 
                     new ArbreNonVide("a", ArbreVide.get(), ArbreVide.get())
                  ),
                  new ArbreNonVide("c", ArbreVide.get(), ArbreVide.get())
               )
            ),
            new ArbreNonVide("f", ArbreVide.get(), ArbreVide.get())
         );
     }
     ArbreBinaire getArbre(){ return arbre; }
   }                                            
   --> cat Main2.java
   class Main2 {
      public static void main(String[] arg) {
         ArbreBinDeLexpression arbre = new ArbreBinDeLexpression();   
         arbre.getArbre().prefixe();
      }
   }    
   --> java Main2
   + / + + a * b c * 5 d - * 4 a c f      
   -->

Une seconde solution

Avec cette solution, l'instance unique de la classe n'est créée que si nécessaire. Elle consiste à :

définir comme précédemment une variable de classe static référençant l'instance mais qui n'est pas initialisée, c'est-à-dire qui a null comme valeur initiale ;
définir comme précédemment une méthode public (de nom get) qui crée l'instance si elle ne l'a pas été et renvoie dans tous les cas la référence de cette instance unique ;
fournir, comme précédemment un constructeur par défaut qualifié private.

Avec cette solution, la classe singleton ArbreVide est définie comme suit :


   --> cat ArbreVide.java
   class ArbreVide extends ArbreBinaire {    
      private static ArbreVide arbreVide;
      private ArbreVide() {}
      static ArbreVide get() {
         if (arbreVide == null)
              arbreVide = new ArbreVide();
         return arbreVide;
      }
      public void prefixe() {}
      boolean estVide() { return true; }
   }

En guise de conclusion

Une solution peut être développée sans classe abstraite, avec des interfaces :


   --> cat BinaryTree.java
   interface BinaryTree {boolean estVide(); }   
   --> cat Prefixe.java
   interface Prefixe extends BinaryTree {void prefixe(); }      
   --> cat ArbreVide.java
   class ArbreVide implements BinaryTree, Prefixe {
      static ArbreVide arbreVide = new ArbreVide();
      private ArbreVide() {}
      static ArbreVide get() {return arbreVide; }
      public void prefixe() {}
      public boolean estVide() {return true;}
   }
   --> cat ArbreNonVide.java
   class ArbreNonVide implements BinaryTree, Prefixe {
      String etiquette;
      BinaryTree arbreGauche, arbreDroit;
      ArbreNonVide(String etiquette,
                    BinaryTree gauche,
                    BinaryTree droit) {
         this.etiquette = etiquette;
         arbreGauche = gauche;
         arbreDroit = droit;
      }
      public void prefixe(){
         if (! estVide()){
            System.out.print(etiquette + " ");
            ((Prefixe)arbreGauche).prefixe();
            ((Prefixe)arbreDroit).prefixe();
         }
      }
      public boolean estVide() {return false; }
   }