Cet exercice consiste à modéliser un arbre binaire de recherche et à utiliser un tel arbre pour effectuer un tri.
L'arbre binaire modélisé sera destiné à contenir des mots, instances de la classe String.
On écrira une classe ABR dans un paquetage nommé abr. La classe ABR modélisera un arbre binaire de recherche ; elle aura cinq attributs privés :
- un attribut de type boolean qui vaudra true si l'arbre est vide et false dès qu'il possède au moins un noeud ;
- un attribut de type String pour le mot contenu par la racine de l'arbre ;
- un attribut de type int qui servira à compter un nombre d'occurrences du mot contenu par la racine ;
- deux attributs pour les sous-arbres gauche et droit.
La classe ABR possèdera deux constructeurs :
- un pour construire un arbre vide,
- un pour construire un arbre en utilisant un fichier de mots dont le nom sera fourni en paramètre, et qui fera appel à la méthode construire décrite ci-dessous.
La classe ABR possèdera plusieurs méthodes :
- une méthode construire prend en paramètre un nom de fichier et ajoute à l'arbre binaire de recherche tous les mots contenus dans le fichier en appelant la méthode inserer décrite ci-dessous ; son code peut être :
public void construire(String nomFichier) throws IOException {
Scanner lecteur = new Scanner(new File(nomFichier));
while(lecteur.hasNext()) inserer(lecteur.next());
}
La méthode next de lecteur prend dans le fichier la prochaine chaîne de caractère, en s'arrêtant au premier caractère d'espacement rencontré. À chaque appel, elle prend la chaîne suivante du fichier.
Si vous ne connaissez pas les exceptions, le mieux est simplement de faire mention de throws IOException dans l'en-tête de toute méthode qui fait appel à une méthode qui fait appel à une méthode ... qui fait appel à cette méthode construire.
La classe IOException est plus précisément la classe java.io.IOException ; la classe File est plus précisément la classe java.io.File ; la classe Scanner est plus précisément la classe java.util.Scanner.
- la méthode inserer est récursive ; elle prend en paramètre un mot, c'est-à-dire une instance de la classe String et elle insère ce mot dans l'arbre ; il y a deux cas selon que l'arbre actuel est vide ou bien qu'il contient déjà un mot dans sa racine ; dans ce second cas, soit l'insertion à lieu dans le sous-arbre gauche, soit l'insertion a lieu dans le sous-arbre droit, soit le nombre d'occurrences est augmenté ;
- la méthode récursive ecrireListeTriee permet d'écrire la liste triée des mots contenus par l'arbre en ordre alphabétique, en indiquant aussi le nombre d'occurrences de chacun de ces mots ;
- une méthode récursive nommée hauteur calcule la hauteur de l'arbre.
On concevra ensuite une classe pour tester la classe ABR avec une méthode main. On pourra tester la classe ABR en insérant des mots un à un, ou bien en construisant l'arbre à partir d'un fichier quelconque (par exemple hiver.txt).
Corrigés
© Irène Charon, Télécom ParisTech 2011
