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).

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

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

Si vous voulez en savoir un peu plus sur les arbres binaires de recherche

Un arbre binaire de recherche est un structure de données dans laquelle les données sont rangées de telle sorte qu'on peut les retrouver rapidement et dans un certain ordre. Un lien vers une page en anglais et un lien vers une page en français. Un lien pour voir en image comment une donnée peut être retrouvée rapidement. Un lien pour voir en image comment les données sont ajoutées dans un arbre binaire de recherche (commencez par cliquer sur "Random BSTree") ainsi que plusieurs façons de retrouver les données ("inorder" pour les retrouver dans l'ordre croissant).
Une vidéo un peu plus générale. Commentaires sur cette vidéo :

• Les dictionnaires correspondent aux Map en Java.
• Python est un autre langage de programmation que Java ; il est facile de comprendre le code donné en Python (à la fin de la vidéo) si on connait Java.
• Ecoutez attentivement ce qui est dit sur la complexité des opérations. Si vous voulez en savoir plus : Une introduction à la complexité des algorithmes.

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

• un constructeur sans paramètre,
• un constructeur qui prend une valeur en paramètre,
• un constructeur qui prend une valeur et les 2 noeuds gauche et droit en paramètres,
• les accesseurs et les modificateurs pour la valeur et les 2 noeuds gauche et droit,
• une méthode toString() qui affiche les valeurs du noeud et les sous-noeuds attachés à ce noeud.

Voici une classe TestNoeud pour tester rapidement votre classe. Vous pouvez y ajouter des tests plus complexes si vous voulez.

Correction :

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 une variable d'instance qui contient un noeud racine (classe Noeud de l'exercice précédent). Modifiez un peu la classe Noeud pour qu'elle devienne une classe interne de la classe ArbreBinaireRecherche.

Pour tout noeud de l'arbre

• le sous-noeud gauche est la racine d'un arbre qui contient les éléments inférieurs ou égaux à la valeur du noeud ;
• le sous-noeud droit est la racine d'un arbre qui contient les éléments supérieurs à la valeur du noeud.

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 de type E 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 ; si vous ne trouvez pas, voici un peu d'aide.

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

• une méthode inserer pour ajouter un élément dans l'arbre ;
• une méthode contient qui indique si un objet appartient à l'arbre ;
• une méthode afficherElements qui affiche tous les éléments de l'arbre dans leur ordre naturel ;
• et évidemment une méthode toString pour tester.

La première chose à faire est de vous assurer que l'ajout d'un élément est correct :

1. Commencez par écrire la méthode inserer et la méthode toString(). Dans une méthode main créez un arbre qui contient des nombres entiers, ajoutez un seul élément et faite afficher l'arbre avec toString(). Vérifiez que tout est correct.
2. Ensuite ajoutez un élément plus grand que l'élément qui est déjà dans l'arbre. Faites afficher l'arbre et vérifiez.
3. Ensuite ajoutez un élément plus petit que l'élément qui est déjà dans l'arbre. Faites afficher l'arbre et vérifiez.
4. Ajoutez d'autres éléments et vérifiez que tout est correct en faisant afficher l'arbre.

Quelle visibilité allez-vous donner à la classe Noeud (private, public,...) ?

Aide pour la méthode qui ajoute une valeur dans l'arbre :

Le plus simple est d'utiliser la récursivité.

Pour l'ajout (méthode void inserer(element)), commencez par regarder si la racine de l'arbre est null. Si la racine est vide, on crée une racine avec le nouvel élément.

Si la racine n'est pas vide, on appelle une méthode récursive insererRecursif qui prend en paramètre l'élément à insérer et aussi le noeud à partir duquel cet élément sera inséré.

Au début ce noeud sera la racine mais ensuite ça sera d'autres noeuds. Par exemple, si la valeur à ajouter est plus grande que la valeur de la racine, insererRecursif prendra en paramètre le noeud droit de la racine (plus de détails sont donnés juste en dessous de la méthode inserer).

On aura donc ce code :

public void inserer(E elt) {
  if (racine == null) {
    racine = new Noeud<>(elt);
  } else {
    insererRecursif(elt, racine);
  }
}

Il vous reste à écrire insererRecursif. L'idée : on compare l'élément à la valeur du noeud passé en paramètre. Si l'élément est plus petit, insérer dans le noeud gauche (appel récursif de insererRecursif en lui passant l'élément et le noeud gauche du noeud), sinon insérer dans le noeud droit (appel récursif de insererRecursif en lui passant l'élément et le noeud droit du noeud). Comme pour la méthode inserer, attention à distinguer les cas où le noeud droit ou le noeud gauche est null. ; par exemple, si le noeud droit est vide, créez un nouveau noeud et le mettre comme noeud droit.

Aide pour la méthode qui affiche tous les éléments de l'arbre :

Testez si votre méthode marche quand l'arbre ne contient aucune valeur. Dans ce cas la méthode n'affiche rien.

Correction :

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.

Optionnel : Vous pouvez essayer de faire mieux mais ça sera bien plus difficile : écrivez une classe interne qui implémente Iterator. 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.