Remarques préliminaires :

• Un cours complet sur les structures de données appelées arbres est à votre disposition. Les paragraphes "Introduction" à "Recherche dans un arbre" inclus, ainsi que le paragraphe "Maximier" concernent ce TP. Ils seront donc supposés connus lors des tests correspondants.
• Tous les exercices de ce TP doivent être effectués dans le répertoire dirarbres qui sera considéré comme répertoire courant.
• Uniquement pour des raisons de simplicité, aucune exception ne sera levée dans ces exercices. Elles seront cependant indiquées en commentaires dans le corrigé.
• Rappel : Chemins d'accès aux sources des corrigés.

Sommaire

Arbre de recherche

exo_01

• Liste des fichiers créés ou modifiés : exo_01.cxx, CNode2Gen.h, CNode2Gen.h, CTree.h, CTree.hxx, Makefile_01

Classe CNode2Gen

    La classe générique CNode2Gen est assez semblable à la classe CLink2Gen. Elle s'en distingue cependant par le fait que les opérations de suppression sont impossibles à effectuer dans une fonction membre. En effet, la suppression d'un noeud nécessite non seulement d'accrocher ses deux fils à d'autres noeuds, donc de se déplacer dans l'arborescence, mais aussi de mettre à jour le père du noeud supprimé. Or aucun lien ne permet de remonter dans l'arbre. L'opération de suppression d'un noeud doit donc être faite par une fonction non membre.

    L'insertion à gauche ou à droite d'un noeud pourrait à la rigueur être effectué par une fonction membre. Pour des raisons de cohérence, et parce qu'il est plus simple de le faire autrement, nous ne ferons donc aucune de ces opérations dans la classe CNode2Gen.

    Recopier les fichiers dirliste2/CLink2Gen.h et dirliste2/CLink2Gen.hxx dans les fichiers CNode2Gen.h et CNode2Gen.hxx, remplacer les identificateurs CLink2Gen par CNode2Gen, Precedent par Gauche, Suivant par Droit. Supprimer les fonctions inutiles et effectuer les dernières adaptations nécessaires.

Classe CTree

    La classe doit posséder :

• un type CNoeudT privé obtenu par instanciation de CNode2Gen (voir le type CLinkT dans les classes conteneurs),
• une donnée-membre privée m_Racine, pointant sur un noeud (la racine de l'arborescence),
• une méthode publique Ajouter() de profil ci-dessous, permettant d'ajouter une information (donc un nouveau noeud) dans l'arborescence. Cet ajout doit respecter la propriété fondamentale des arbres de recherche.
• un constructeur public par défaut et un destructeur permettant de détruire tous les noeuds de l'arborescence,
• une méthode publique Editer() de profil ci-dessous, permettant d'afficher à l'écran le contenu de l'arbre, bien entendu dans un ordre cohérent.

    Les trois méthodes, Ajouter(), Editer() et le destructeur, nécessitent un parcours récursif de l'arborescence. Or ce sont des méthodes publiques. Un principe général déjà rencontré dans l'étude de la récursivité est qu'une fonction récursive ne doit jamais être mise à la disposition directe de l'utilisateur. Elle doit au contraire être encapsulée dans une fonction non récursive, dont le rôle consiste généralement seulement à "amorcer" la récursivité. C'est ce que nous ferons ici.

    Dans la partie privée de la classe CTree, ajouter les trois fonctions de profils :
 

void      DetruireNoeud (CNoeudT * const Ptr); void      EditerNoeud   (CNoeudT * const Ptr) const; CNoeudT * Ajouter       (CNoeudT * const Ptr, const T & Elem);

    La première, DetruireNoeud(), détruit récursivement toute l'arborescence à partir du noeud Ptr qui lui est passé en paramètre.

    La deuxième, EditerNoeud(), affiche récursivement le contenu de toute l'arborescence à partir du noeud Ptr qui lui est passé en paramètre.

    La troisième, Ajouter(), ajoute l'information Elem à sa place dans l'arbre (ou le sous-arbre) dont la racine Ptr lui est passée en paramètre, et renvoie la racine de l'arbre résultant. Si l'arbre est vide en entrée, elle crée un nouveau noeud qu'elle initialise correctement et le renvoie.

    Dans la fonction exo_01(), instanciez un conteneur CTree avec des chaînes (string), puis afficher le contenu de l'arbre. Ajouter différentes chaînes (par exemple "S4", "S2", "S6", "S1", "S3", "S5", "S7", ce qui devrait avoir pour effet de construire un arbre parfait.

Fonction exo_01()

    Recopier un fichier précédemment utilisé dans Makefile_01. Le mettre à jour. Compiler et tester.

Remarques

1. La classe présentée ici est d'une extrême simplicité. Elle est seulement destinée à illustrer quelques manipulations simples d'un arbre binaire, en particulier d'un arbre de recherche. La suppression, indispensable pour rendre cette classe opérante, n'est pas étudiée ici pour des raisons de temps. On trouvera le principe dans le cours correspondant : Suppressions.

   La fonction Editer() n'a été introduite que pour pouvoir vérifier le contenu de l'arbre. Dans la pratique, elle pourrait être remplacée par un fonction ForEach() analogue à celles qui ont été étudiées dans les précédents exercices.

   Pour les mêmes raisons de manque de temps, l'utilisation d'un tel conteneur, même avec la suppression, serait rapidement inefficace par suite d'un déséquilibre grandissant des branches au cours des mises à jour successives. Il faudrait pour cela rééquilibrer l'arbre au fur et à mesure des modifications. Ces différentes techniques sont présentées dans : Arbres équilibrés.

   Enfin, les conteneurs de la bibliothèque standard qui implémentent des arborescences utilisent les arbres bicolores plus performants que les arbres AVL, mais difficiles à programmer.

2. La classe CTree pourrait servir de base à différents types de conteneurs, comme par exemple les ensembles (pas de doubles) et multi-ensembles (doubles autorisés) qui supportent les opérations ensemblistes. Bien que ne nécessitant pas de relation d'ordre d'un strict point de vue mathématique, les ensembles de la bibliothèque standard de C++ supposent l'existence de la relation inférieur.
3. Une seule exception devrait être levée, lors de la tentative d'ajout d'un élément lorsque la mémoire est insuffisante : la fonction Ajouter() récursive lèverait bad_alloc et la fonction publique Ajouter() lèverait une exception de code d'erreur CstMemInsuff ou CstArbrePlein par exemple.
4. De nombreuses améliorations devraient être effectuées, qui ne demandent que de très légères modifications :
   1. à chaque appel récursif sont empilés les paramètres. Il faut donc en limiter le nombre aux seuls vraiment indispensables. Dans la fonction privée Ajouter(), c'est toujours le même paramètre Elem qui se transmet d'appel en appel. Il faudrait donc le passer en variable globale, en en faisant une donnée-membre privée m_InfoAAjouter, de type T, dans la classe CTree, qui serait initialisée avant le premier appel récursif.
   2. sauf lors de la création d'un nouveau noeud, la fonction Ajouter() renvoie toujours le pointeur du noeud qu'elle a reçu en paramètre. Il est possible de court-circuiter tous les retours normaux de cette fonction, qui permettent de sortir de l'appel le plus profond de la récursivté, en levant une exception et en la récupérant dans la fonction publique non récursive Ajouter().

Corrigés :      exo_01.cxx      -      CNode2Gen.h      -      CNode2Gen.hxx      -      CTree.h      -      CTree.hxx      -      Makefile_01

Sommaire

Maximier

exo_02

• Liste des fichiers créés ou modifiés : exo_02.cxx, CMaximier.h, CMaximier.hxx, Makefile_02

    Dans les fichiers CMaximier.h et CMaximier.hxx, ajouter à l'espace de noms nsSdD la classe générique CMaximier. Ajouter la donnée membre m_Vect de type vector<T>, dans laquelle seront stockés les différents noeuds du maximier. Ajouter un constructeur par défaut, et les fonctions empty(), Deposer() et Retirer(), de profils suivants :
 

bool empty   (void) const; void Deposer (const T & Info); T    Retirer (void);

    Nous avons signalé dans le cours que les deux fils du noeud d'indice i sont aux indices 2i et 2i + 1, et que son père a pour indice i/2, sous réserve de commencer les indices à 1. Pour ce faire, le constructeur de CMaximier ajoutera en début de m_Vect un élément fictif (une sorte de sentinelle). Le premier véritable élément sera dont placé en m_Vect [1].

    Afin de faciliter la lisibilité du code, ajouter à la classe CMaximier le type et les trois fonctions membres privées :
 

typedef std::vector ::size_type Indic_t; Indic_t GetGauche (const Indic_t i) const; Indic_t GetDroit  (const Indic_t i) const; Indic_t GetPere   (const Indic_t i) const;

qui renvoient l'indice de l'élément voulu. Attention, les valeurs renvoyées peuvent être invalides : == 0 ou >= m_Vect.size(). Il faudra donc les tester avant toute utilisation.

    La fonction Deposer() consiste à placer la nouvelle valeur en fin de vecteur (push_back()), c'est-à-dire sur la première feuille disponible, puis à faire remonter la valeur ajoutée le long des branches, soit jusqu'à ce que la valeur de son père soit supérieure, soit jusqu'à ce qu'elle soit à la racine.

    La fonction Retirer() consiste à retirer la première valeur (m_Vect [1]), à la remplacer par la dernière valeur du vecteur (m_Vect.back()), à tronquer le vecteur (m_Vect.pop_back()), puis à faire redescendre la valeur placée sur la racine jusqu'à ce qu'elle soit plus grande que ses deux fils ou qu'elle soit sur une feuille.

    Dans la fonction exo_02(), déposer dans un maximier 10 entiers entre 0 et 100, passées en argument de la commande (ne pas oublier de les transformer en entier au moyen de la fonction C atoi() dont le profil es t dans le fichier <cstdlib>). On pourrait aussi les générer aléatoirement.

    Retirer et afficher toutes les valeurs du maximier jusqu'à ce qu'il soit vide.

    Recopier le fichier Makefile_01 dans Makefile_02. Le mettre à jour. Compiler et tester.

Corrigés :      exo_02.cxx      -      Maximier.h      -      Maximier.hxx      -      Makefile_02

Sommaire

Téléchargement des corrigés :

Chemins d'accès aux sources des corrigés :

© D. Mathieu     mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique