:: Enseignements :: ESIPE :: E4INFO :: 2012-2013 :: Java Avancé ::

TP noté de Java Avance

Exercice 1 - ReadOnlyTree

On cherche à implanter un arbre binaire (deux 2 fils max) de recherche (les valeurs sont rangées par ordre croissant) non mutable (je répète non mutable) générique (qui marche si les valeurs définissent un ordre de comparaison avec elles-mêmes). On considèrera que null n'est pas une valeur valide dans l'arbre.
On veux, de plus, qu'il soit impossible de construire un arbre binaire qui n'est pas un arbre binaire de recherche, pour cela en plus de la valeur (element) d'un noeud et de ces deux fils, on stockera aussi le maximum (max) et le minimum (min) du sous-arbre correspondant à un noeud.
Par exemple, l'arbre construit comme ceci :

     tree("l", tree("f", leaf("a"), leaf("g")), tree("o", leaf("n"), leaf("u")));

est représenté par l'arbre

                          "l"               avec l.min="a"   l.max="u"
                          / \                    f.min="a"   f.max="g"
                         /   \                   o.min="n"   o.max="u"
                        /     \                  a.min="a"   a.max="a"
                       /       \                 g.min="g"   g.max="g"
                     "f"       "o"               n.min="n"   n.max="n"
                     / \       / \               u.min="u"   u.max="u"
                    /   \     /   \
                  "a"   "g"  "n"  "u"

Les tests JUnit sont dans la classe ReadOnlyTreeTest.java.

Ecrire la classe ReadOnlyTree dans le package fr.umlv.tpnote paramétrée par E tel que E soit comparable avec lui-même.
Ecrire une méthode statique leaf permettant de créer une feuille de l'arbre.
Ecrire une méthode statique tree permettant de créer un noeud de l'arbre pouvant avoir des fils inexistants (null) et qui vérifie que si des fils existent l'arbre construit soit bien un arbre binaire de recherche.
Ecrire les getters permettant d'obtenir l'élement, le minimum et la maximum.
Ecrire une méthode size qui renvoie la taille de l'arbre. Dans notre exemple, la taille de l'arbre est 7.
Ecrire une méthode traverse qui fait un parcours infixe de l'arbre (on visite le fils gauche, l'élement courant puis le fils droit) et qui pour chaque élement appelle la méthode apply de l'objet Block pris en paramètre.
Pour tester, vous écrirez un main qui crée l'arbre ci-dessus et qui affiche celui-ci en utilisant la méthode traverse. Le block qui fait l'affichage devra être spécifié en utilisant la syntaxe des classes anonymes.
Ecrire une méthode toString qui permet l'affichage, entre crochets, des noeuds de l'arbre dans l'ordre infixe séparés par des virgules.
Par exemple, avec l'arbre ci-dessus, l'affichage est
```
       [a, f, g, l, n, o, u]
      
```
Ecrire une méthode into qui permet de copier tous les élements de l'arbre (dans l'ordre infixe) dans une collection. La collection prise en paramètre peut avoir un type différent de E, c'est pourquoi on spécifiera en second paramètre la classe des élements de la collection. De plus, pour faciliter l'utilisation, la méthode renverra la collection passée en paramètre (avec le même type).
Exemple d'utilisation:
```
        ReadOnlyTree<?> tree = leaf("foo");
        ArrayList<String> list = tree.into(new ArrayList<String>(), String.class);
      
```
Ecrire une méthode contains qui regarde si un élement est stocké dans l'arbre. Pour simplifier les choses, on considèrera que l'élément cherché est un E.
Note algorithmique: l'arbre est un arbre binaire de recherche, il n'est donc pas nécessaire de parcourir tout l'arbre pour trouver un élement.
Ecrire une méthode append qui prend un paramètre un élement et renvoie un arbre construit en ajoutant l'élément à l'arbre courant.
Note d'implantation: il est possible que l'arbre courrant et l'arbre renvoyé en tant que résultat partage des noeuds comme ceux-ci sont immutables.
Ecrire une méthode findElementAt qui prend un index, et renvoie l'élément à l'index de la liste créée en recopiant tous les élements par un parcours infixe. Bien sûr, l'idée est de ne pas recopier les élements pour éviter de créer la liste intermédiaire.
En utilisant l'exemple ci-dessus, tree.findElementAt(0) doit renvoyer "a" et tree.findElementAt(5) doit renvoyer "o".