les exercices suivants concernent des compléments ou des modifications de la classe CTree étudiée au TP 14. Ils sont tous indépendants les uns des autres. Il n'est évidemment pas nécessaire de recopier à chaque question la totalité de la classe, mais d'indiquer les modifications de la façon suivante :
// fichier CTree.h
template <class T> class CTree
{
// ...
<-- vos ajouts
public :
// ...
<-- vos ajouts
}; // class CTreeet
// fichier CTree.hxx
// ...
<-- vos ajoutsVous utiliserez exclusivement les macros des corrigés :
#define TEMPL template <class T>
#define TEMPLINL TEMPL inline
#define CTREE nsSdD::CTree <T>Ne pas traiter les exceptions, en supposant qu'il y aura toujours assez d'espace mémoire pour ajouter de nouveau éléments. Cette supposition n'est faite que parce que les traitements seraient beaucoup trop longs et difficiles dans le cadre d'un test.
1 - Surcharge de l'opérateur <<
Contrairement à ce que l'habitude pourrait laisser croire, on ne surcharge pas seulement l'opérateur << pour injecter des données dans un flux de sortie. Toute classe, en particulier toute classe de conteneur, peut proposer cet opérateur pour charger des données de provenances diverses, en particulier d'un autre conteneur. Dans cet exercice, il vous est demandé d'écrire l'opérateur membre << permettant d'ajouter à un arbre existant (l'arbre courant) des informations stockées dans un vector, de façon à permettre l'usage suivant :
vector <string> VString1; VString1.push_back ("S4");
VString1.push_back ("S2");
VString1.push_back ("S6");CTree <string> Arbre;
// Eventuellement remplissage de Arbre
// ...
Arbre << VString1; // Ajout des trois chaînes à Arbre
Arbre.Editer();A la classe CTree générique, vous ajouterez préalablement un type privé CVectT qui représente un vecteur d'éléments du type T.
2 - Nouvelle surcharge de l'opérateur <<
Si la surcharge que vous avez écrite dans l'exercice précédent ne permet pas l'écriture suivante :
vector <string> VString1;
vector <string> VString2;// remplissage de VSring1
// ...
// remplissage de VSring2
// ...CTree <string> Arbre;
Arbre << VString1 << VString2;
Arbre.Editer();en proposer une nouvelle version qui la permette.
3 - Surcharge de l'opérateur +=
Le C++ autorisant la surcharge des opérateurs, il faut en profiter chaque fois que l'utilisation d'un opérateur est au moins aussi lisible que l'appel d'une fonction.Surcharger l'opérateur += destiné à remplacer la fonction publique Ajouter() (cela signifie que vous ne devez pas utiliser cette dernière). Il doit permettre l'écriture suivante :
CTree <string> Arbre; Arbre += "S4";
Arbre += "S2";Arbre.Editer();
4 - Nouvelle surcharge de l'opérateur +=
Si la surcharge que vous avez écrite dans l'exercice précédent ne permet pas l'écriture suivante :
CTree <string> Arbre; Arbre += "S4";
(Arbre += "S2").Editer();en proposer une nouvelle version qui la permette.
5 - Surcharge de l'opérateur =
La solution proposée ici est simple : elle consiste à transférer dans l'arbre courant chacune des valeurs que contient l'arbre source passé en paramètre. Ce dernier doit donc être parcouru récursivement afin d'atteindre chacun de ses noeuds.Comme pour les différentes fonctions étudiées en TD/TP, il faut écrire deux fonctions :
Corrigé : CTree.h - CTree.hxx
- une fonction membre privée Tranférer(), de profil :
void Transferer (CNoeudT * const Ptr); qui, au moyen de la fonction Ajouter() écrite en TP, transfère récursivement dans l'arbre courant l'information contenue dans le noeud Ptr passé en paramètre et tous ses fils. Cette fonction Tranférer()correspond à l'un des parcours récursifs classiques pré-, in- ou post-fixé. Justifiez en 1 ou 2 lignes le choix du parcours que vous avez fait.
- l'opérateur public =, de profil et de sémantique classiques, non récursif, qui sert à initialiser la récursivité. Comme précédemment, on supposera que la mémoire est suffisante pour ne pas traiter l'exception bad_alloc. L'opérateur = peut donc détruire l'ancienne arborescence avant de construire la nouvelle.
6 - Méthode Cloner()
La surcharge des opérateurs étant malheureusement impossible en Java, la méthode clone() existe pour tout objet, et permet de le dupliquer. Dans cette question, il est demandé d'écrire en C++ une fonction membre publique Cloner(), de profil :
CTree & Cloner (const CTree & Tree); Il serait possible de l'implémenter de façon analogue à l'affectation ci-dessus, mais nous préfèrerons utiliser une autre méthode pour deux raisons :
La fonction publique Cloner() doit utiliser une fonction membre privée Cloner(), de profil :
- un clone est une copie qui doit avoir rigoureusement la même structure que l'original. Or rien ne nous garantit, dans les spécifications de l'affectation, que le résultat a les mêmes noeuds aux mêmes positions, même si globalement, les deux arbres contiennent les mêmes valeurs et sont tous deux des arbres de recherche.
- l'affectation utilise la fonction Ajouter() qui, pour chaque nouvelle valeur, parcourt l'arbre pour rechercher la place de l'ajout, ce qui est long.
CNoeudT * Cloner (CNoeudT * const Ptr); qui :
Corrigé : CTree.h - CTree.hxx
- clone le fils gauche du noeud pointé par Ptr,
- clone le fils droit du noeud pointé par Ptr,
- construit un nouveau noeud en
- copiant la valeur du noeud pointé par Ptr,
- attachant à ce nouveau noeud les clones des fils gauche et droit précédemment obtenus,
- renvoie le nouvel arbre ainsi construit.
© D. Mathieu mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique