IFT 1020, TP2
Implantation de l'arbre de la Briandais

 

1. Date de la remise:

À rendre avant minuit, du 1 au 2 novembre.

2. But:

Ce TP vise à vous familiariser avec la manipulation des arbres binaires et la programmation récursive.

3. Description du problème

3.1. Arbre de la Briandais

L'arbre "de la Briandais" est un arbre binaire particulier, qu'on peut utiliser pour stocker un arbre quelconque. Pour un arbre quelconque, un noeud a éventuellement un ensemble d'enfants, et un frère. Dans un arbre de la Briandais, on les transforme de la façon suivante: l'enfant à gauche stocke le premier enfant, et l'enfant à droite stocke le frère. Cette structure peut être utilisée pour stocker un dictionnaire de français.

Initialement, un dictionnaire du français peut être structuré dans un "trie". Dans cette structure de trie, les mots sont constitués par des chemins entre la racine et un nœud "terminal". Par exemple, les arbres "trie" suivants contiennent les mots "bas", "base", basse", "beau", "bel", "belle", "liste", "lit", "livre", "table", et "tableau" (où les noeuds marqués par "." correspondent aux noeud "terminaux" - ceux qui terminent un mot):

L'arbre de la Briandais correspondant est comme suit:

C'est un arbre binaire. Les deux enfants d'un noeud sont respectivement la lettre suivante du même mot, et la lettre alternative. La contrainte dans cette organisation est que la lettre alternative soit supérieure à la lettre courante. Autrement dit, les lettres sont triées dans l'ordre alphabétique. On peut aussi voir un tel arbre comme étant organisé en niveau: le premier niveau correspond aux premières lettres des mots, le deuxième niveau aux deuxièmes lettres, etc.

L'avantage de cette organisation par rapport à une simple liste de mots est évident: elle économise l'espace pour le stockage (car les lettres communes sont partagées par plusieurs mots), et le temps pour trouver un mot est plus court.

Pour un vrai dictionnaire, les noeuds terminaux doivent contenir toutes les informations sur le mot telles que la catégorie grammaticale (nom, verbe, etc.), le genre, le nombre, la définition du mot, etc.

3.2. Le travail demandé

Le travail consiste à réaliser quelques opérations sur les arbres de la Briandais. Les opérations que vous devez réaliser sont les suivantes:

Ces opérations seront déclarées dans la classe Briandais qui doit "implements" l'interface suivante:

interface Dictionnaire {

String chercher(String mot);

// retourne l'INFORMATION associe à "mot" ou NULL si non trouve

void ajouter(String mot, String info);

// ajouter le mot s'il n'existe pas déjà. Si le mot existe, changer l'info seulement.

void enlever(String mot);

// enlever le mot s'il existe. Enlever aussi les nœuds qui sont utilisés juste pour ce mot.

// Par ex. dans l'exemple, si on enlève "basse", les noeud "s" et "e" sont enlevés, mais pas

// "b", "a" et "s" qui sont encore utilisés pour les mots "bas" et "base".

void imprimer();

// Imprimer tous les mots dans l'ordre, avec les informations associées.

}

class Briandais implements Dictionnaire {...}

Vous êtes libre de choisir la structure qui vous semble appropriée pour les noeuds des arbres de La Briandais..... mais ceux-ci auront probablement les attributs suivants:

class Noeud {

char lettre;

Noeud suite, alternative;

String info;

...

}

info correspond à un texte non vide si c'est un noeud terminal (la dernière lettre d'un mot).

En plus de la classe Briandais, vous devez aussi faire une interface graphique simple utilisant Frame pour qu'un utilisateur puisse lancer ces opérations, et afficher les mots et les informations dans une fenêtre TextArea à côté.

Pour la méthode "construire", l'utilisateur doit pouvoir entrer le nom du fichier à lire. Les données dans ce fichier ont le format suivant:

Par exemple:

sur;prep,sing,sur,rel

laquelle;pron_rel,fem,sing,

systeme;n,masc,sing,outil,

où pour le mot "sur", l'information est "prep,sing,sur,rel". Un fichier de test est disponible dans http://www.iro.umontreal.ca/~dift1020/liste_mots

3. Critères d'évaluation

Vous devez remettre le programme avant l'heure limite. Après l'heure, il y a 1 points de pénalité pour chaque jour de retard.

À part le programme, vous devez aussi remettre en même temps un mini rapport (environ 3 pages imprimées) qui doit contenir au moins les informations suivantes:

Ce TP compte pour 10% (10 points) dans la note finale, répartis comme suit: