Remarques préliminaires :
Arbre de recherche | exo_01 |
Maximier | exo_02 |
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 :
void Ajouter (const T & Elem);
void Editer (void) const; |
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
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.
Corrigés : exo_01.cxx - CNode2Gen.h - CNode2Gen.hxx - CTree.h - CTree.hxx - Makefile_01
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 Indic_t GetGauche (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
© D. Mathieu
mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique