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 d'abord une classe Noeud modélisant un noeud de l'arborescence et qui contiendra :
- un attribut privé de type String nommé mot pour le mot contenu par le nœud ;
- un attribut privé de type int nommé nbOcc qui servira à compter un nombre d'occurrences du mot contenu par le nœud dans un texte donné ;
- deux attributs privé nommés fg et fd, de type Noeud, pour les sous-arbres gauche et droit issus de ce nœud ;
- un constructeur prenant en paramètre une chaîne de caractères pour initialiser l'attribut mot.
la classe contiendra aussi des accesseurs pour ces attributs privés.
On écrira une classe ABR dans un paquetage nommé abr. La classe ABR modélisera un arbre binaire de recherche ; elle aura :
- un attribut privé de type Noeud nommé racine pour la racine de l'arbre ;
- un constructeur pour construire un arbre vide, pour lequel racine vaut null;
- un constructeur 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 ;
- une méthode construire : cette méthode 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.
- une méthode inserer privée ayant deux paramètres, un de type String nommé mot pour le mot à insérer et un de type Noeud nommé rac pour la racine de l'arbre ou du sous-arbre dans lequel le mot doit être inséré : cette méthode est récursive ; il y a deux cas selon que l'arbre dans lequel le mot doit être inséré est vide ou non ; 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é ;
- une méthode inserer ayant un paramètre de type String nommé mot pour le mot à insérer ; elle insère mot dans l'arbre modélisé ;
- une méthode ecrireListeTriee sans paramètre : elle 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 ; elle invoque une autre méthode ecrireListeTriee, récursive, ayant un paramètre de type Noeud.
- une méthode nommée hauteur calcule la hauteur de l'arbre en invoquant une méthode privée récursive de même nom.
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).
Vous pouvez aussi voir ici une autre façon de modéliser un arbre binaire de recherche.
Corrigés
© Irène Charon, Télécom ParisTech 2011
