TP sur la généricité

Page Home (contact) Retour TPs

Support de cours sur la généricité
Support de cours sur les classes internes


Dans ce TP vous allez écrire une classe pour représenter un arbre binaire de recherche dans lequel les éléments seront rangés selon leur ordre naturel (ou selon un ordre déterminé, pour une des dernières questions).

Une référence en anglais et une référence en français (parmi bien d'autres) pour vous rafraichir la mémoire sur les arbres binaires de recherche.

Toutes les classes de ce TP seront dans un paquetage fr.unice.abr.

Ce TP est long mais il vous est fortement conseillé de le terminer seul après la séance de TP, ou au moins d'étudier attentivement sa correction.


Classe Noeud

Cette classe représentera un noeud d'un arbre binaire (pas nécessairement d'un arbre binaire de recherche). Un noeud a une valeur et peut avoir 2 noeuds fils : le noeud gauche et le noeud droit.

La classe Noeud doit être générique. On devra pouvoir indiquer le type E des valeurs qui seront conservées dans le noeud. Les éléments de E ne sont pas nécessairement ordonnés.

Mettez dans la classe

Vous écrirez une classe TestNoeud pour tester votre classe. Testez seulement la création d'un noeud qui contient un noeud fils ; utilisez la méthode toString() pour vérifier que tout marche bien.

Correction :

Classe Noeud
Classe TestNoeud

Classe ArbreBinaireRecherche

Cette classe sera générique. On pourra indiquer le type E des élements contenus dans l'arbre.

Un arbre binaire de recherche a un noeud racine. Pour tout noeud de l'arbre

Un arbre binaire de recherche doit nécessairement travailler avec une relation d'ordre sur les éléments de type E (ça n'est pas nécessaire pour le noeud d'un arbre binaire quelconque). Vous allez commencer par écrire un arbre dont les éléments ont un ordre naturel, comme c'est le cas, par exemple, pour Integer ou String. Cet ordre naturel sera représenté par l'interface générique java.lang.Comparable. C'est à vous de compléter la définition de Comparable pour trouver la bonne instanciation.

Cette classe contiendra 2 constructeurs de signatures : ArbreBinaireRecherche() (construit un arbre vide) et ArbreBinaireRecherche(E) (indique la valeur de la racine de l'arbre).

Elle contiendra aussi

Quelle visibilité allez-vous donner à la classe Noeud (vous pouvez modifier cette classe si vous le souhaitez) ?

Correction :

Classe ArbreBinaireRecherche

Test de ArbreBinaireRecherche avec une instanciation

Écrivez une classe TestArbreBinaire qui crée un arbre binaire qui contient des Integer et un autre qui contient des String. Pour tester avec des entiers, vous pouvez générer un grand nombre d'entiers de façon aléatoire en utilisant la classe java.util.Random et sa méthode nextInt() ou nextInt(int).

Testez aussi avec un arbre binaire qui contient des employés. Utilisez pour cela les 2 classes Personne et Employe (classe fille de Personne). Les employés seront rangés dans l'arbre suivant l'ordre alphabétique de leur nom.

Correction :

Classe TestArbreBinairerecherche


Arbre binaire de recherche pour des éléments sans ordre naturel

Les types qui ont un ordre naturel sont assez rares. On veut pouvoir ranger les éléments d'autres types dans un arbre binaire de recherche, en indiquant le critère de comparaison. Par exemple, on voudrait ranger des employés dans un arbre binaire en les rangeant suivant la valeur de leur salaire ou suivant l'ordre alphabétique de leur nom. On veut aussi pouvoir ranger les éléments selon un autre ordre que leur ordre naturel s'ils en ont un.

Modifiez votre classe ArbreBinaireRecherche en conséquence. Testez avec un arbre qui contient des employés, d'abord en les rangeant par ordre alphabétique des noms, puis par ordre des salaires croissants.

Correction :

Classe ArbreBinaireRecherche
Classe TestArbreBinaireRecherche


Itérateur

Ajoutez ce qu'il faut pour que l'arbre binaire soit parcourable par une boucle "for-each". Ajoutez un test dans la classe TestArbreBinaire vérifier que ça fonctionne.

Plusieurs solutions sont possibles. Sans doute la plus simple est de copier les éléments de l'arbre dans une liste et de renvoyer l'itérateur de la liste. Sinon vous aurez besoin de remonter dans l'arbre vers la racine. Vous pouvez le faire en ajoutant dans les noeuds une référence vers le noeud parent ou en utilisant une pile pour garder le parcours depuis la "racine" des noeuds non encore traités vers le noeud "courant". Aidez-vous de la référence sur les arbres binaires de recherche donnée plus haut.

Testez avec une boucle "for-each" dans TestArbreBinaireRecherche.

Correction :

Classe ArbreBinaireRecherche
Classe TestArbreBinaireRecherche


Pour ceux qui ont fini

Complétez le code pour ajouter une méthode qui supprime un élément de l'arbre. Consultez la référence donnée au début pour trouver un algorithme correct.


Retour TPs