Arbres

1. * On souhaite réaliser un arbre binaire de recherche. Un tel arbre se formalise par la classe suivante.

   class Arbre {
     int val;
     Arbre g,d;
     Arbre(int v,Arbre ag,Arbre ad) {
       val=v;
       g=ag;
       d=ad;
     }
   }
   

   La propriété d'un arbre binaire de recherche est que pour tout sommet v qui est descendant de u.g, on a v.val < u.val et pour tout sommet v qui est descendant de u.d, on a u.val < v.val.

   On cherche à faire une application tp07_ex1 telle que si l'on tappe

   java tp07_ex1 6 3 8 9 2 4 6
   on crée un arbre binaire de recherche par insertion successives qui contienne les valeurs 6 3 8 9 2 4 6. Dans le programme tp07_ex1tmplt.java (pour télécharger, cliquer ici), on fournit les méthodes suivantes.
   1. public String toString()
      méthode d'instance de la classe Arbre qui permet de visualiser un arbre (par System.out.print(a)).
   2. static void main(String[] argv)
   Définir la méthode suivante.
   3. static Arbre insere(int v,Arbre a)
      insère une valeur v dans un arbre et retourne le nouvel arbre
   
   [Corrigé]

2. ** En s'inspirant de l'exercice précédant, écrire les méthodes suivantes.
   1. static void affichePrefixe(Arbre a)
      qui affiche un arbre binaire dans l'ordre préfixe.
   2. static void affichePostfixe(Arbre a)
      qui affiche un arbre binaire dans l'ordre postfixe.
   3. static void afficheInfixe(Arbre a)
      qui affiche un arbre binaire dans l'ordre infixe.
   4. static void afficheEnLargeur(Arbre a)
      qui affiche un arbre binaire par un parcours en largeur.
   Exemple:

      .___4____.
      |        |
    ._2_. .____7____.
    |   | |         |
    1   3 5_.   .__11___.
            |   |       |
            6 ._9_.  ._13
              |   |  |
              8  10 12
   

   Ordre préfixe: (4 (2 (1) (3)) (7 (5 (6)) (11 (9 (8) (10)) (13 (12)))))
   Ordre postfixe: (((1) (3) 2) (((6) 5) (((8) (10) 9) ((12) 13) 11) 7) 4)
   Ordre infixe: (((1) 2 (3)) 4 ((5 (6)) 7 (((8) 9 (10)) 11 ((12) 13))))
   Ordre en largeur: (4) (2 7) (1 3 5 11) (6 9 13) (8 10 12)
   [corrigé]

3. *** En s'inspirant de l'exercice 1, écrire une méthode
   static Arbre supprime(Arbre a,int val)
   qui permet de supprimer un entier donné dans un arbre binaire de recherche. Attention: la suppression devra préserver la structure d'arbre binaire de recherche, soit la relation d'ordre entre les valeurs.
   [corrigé]