Arbre binaire et libération récursive de la mémoire

Bonjour,

J'ai un doute sur ce que fait exactement un bout de code que j'ai écrit pour l'école, en fait je crains que toute la mémoire allouée pour mon arbre binaire ne soit pas complètement libérée :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Dictionnaire { private: char *mot; Dictionnaire *gauche; Dictionnaire *droite;   void effacer();   public: ~Destructeur(); /* et d'autres choses ici bien entendu */ }   void Dictionnaire::effacer() { delete[] mot; if (gauche) gauche->effacer(); if (droite) droite->effacer(); }   Dictionnaire::~Dictionnaire() { effacer(); }

---

Est-ce que de cette manière, la mémoire allouée est bien complètement libérée lors de l'appel du destructeur?
J'ai un doute en fait, j'ai peur que seule la mémoire allouée pour mot[] soit libérée, et peut-être pas la mémoire de tous les *gauche et *droite.

J'aurais pu directement faire un destructeur récursif, mais j'ai également une fonction reinitialiser() qui doit aussi libérer la mémoire (et donc faire appel à effacer()).

Autre question, n'y a-t-il pas de problème avec le C++ et la récursivité si la récursion va trop loin? Je pense qu'au niveau performance il vaut mieux concevoir un algorithme itératif (je pense que fonction récursive = un CALL à chaque appel, mais peut-être que le compilateur arrive à éviter ça), et je crois avoir déjà entendu parler d'histoires de "dépassement de pile" si ça va trop profondément.

Merci!

Ça efface bien tout.
Par contre, si tu appelles effacer deux fois de suite, comportement indéfini.
Fais mot = 0 après delete[] mot.

OK ça me rassure alors :-)

Vu que effacer est en private, à moins que je fasse une erreur d'implémentation, je ne pense pas qu'il y ait un risque de double delete (mais je vais quand même rajouter le =NULL, c'est vrai que c'est une bonne habitude à prendre).

Bonjour,
Une façon de te rassurer ne serait-elle pas d'utiliser std::string à la place de char* (si mot désigne bien une chaîne de caractère) ? Tu n'a alors plus à te soucier des allocations :

Code:

---

1 2 3 4 5

class Dictionnaire { private: std::string mot;

---

Citation:

---

Envoyé par loufoque

Ça efface bien tout.

---

Attention tout de même aux fils gauche et droite

Code:

---

1 2	Dictionnaire *gauche; Dictionnaire *droite;

---

Je ne sais pas comment tu gères leur mémoire, mais si ils sont censés appartenir au parent Dictionnaire, il faut les libérer.

Citation:

---

Envoyé par pokraka

Vu que effacer est en private, à moins que je fasse une erreur d'implémentation, je ne pense pas qu'il y ait un risque de double delete

---

Oui mais tu as parlé d'une fonction reinitialiser() qui est susceptible de l'appeler ; de plus tu appelles directement effacer() sur tes fils (gauche et droite) ce que leur propre destructeur fera aussi (ça fait déjà deux appels :aie:), sauf si tu l'a omis comme je l'ai déjà évoqué plus haut (ce qui produit une fuit mémoire).

Citation:

---

Envoyé par 3DArchi

Bonjour,
Une façon de te rassurer ne serait-elle pas d'utiliser std::string à la place de char*

---

+1 ;)

Franchement, je serais plutôt du genre à faire ceci:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Dictionnaire { private: std::string mot; Dictionnaire *gauche; Dictionnaire *droite;   void effacer();   public: ~Destructeur(); /* et d'autres choses ici bien entendu */ }   void Dictionnaire::effacer() { delete gauche; //if inutile ici, car delete NULL est garanti ne rien faire delete droite; gauche=NULL; droite=NULL; }   Dictionnaire::~Dictionnaire() { effacer(); }

---

Ne pas oublier, les pointeurs gauche et droite doivent absolument être initialisés (à NULL ou à une valeur valide) par le constructeur de l'objet.

On ne sait pas exactement qui alloue mot, gauche et droite. J'aurais plutôt tendance à laisser le soin de libérer la mémoire à celui qui l'a crée. Non ?

Si tu fais:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

void f() { Dictionnaire tronc, g,d; tronc.set_gauche(&g); tronc.set_droit(&d); tronc.effacer();//si delete gauche et/ou droit dans effacer argghhh ! } //et donc plutôt   void f() { Dictionnaire *tronc = new Dictionaire(); Dictionnaire *g = new Dictionaire(); Dictionnaire *d = new Dictionaire(); tronc->set_gauche(g); tronc->set_droit(d); tronc->effacer();//si delete gauche et/ou droit dans effacer argghhh ! delete tronc; delete g; delete d; }

---

Le problème, c'est que ça n'est pas viable: Le dictionnaire étant un conteneur, celui qui l'utilise ne peut pas garder en mémoire ce qu'il a créé et ou.

Comment ferais-tu pour placer dans le dico des éléments lus en boucle?

Je suis d'accord mais dans ce cas il faut s'assurer que personne d'autre ne puisse obtenir un pointeur sur un gauche ou un droit.

C'est pour ça que dans un dictionnaire, on sépare généralement en deux classes: Dictionnaire et Noeud (qui peut être une classe imbriquée).

En fait, ma classe contient deux autres methodes: void inserer(char*) pour insérer un nouveau mot, et bool chercher(char*) pour renvoyer un mot (c'est l'énoncé qui demande de faire ainsi, idem pour le char* plutôt que string, et le prof aime bien qu'on ne s'éloigne pas trop de ce qu'il a demandé).

On ne peut pas manipuler soi-même l'arbre binaire ; l'utilisateur n'est pas censé se soucier de l'implémentation choisie (il fait juste Dictionnaire dico; pour créer un dictionnaire).
En fait, le but de l'exercice est de comparer le temps de construction d'une implémentation avec un arbre et d'une implémentation avec un vecteur trié, pas de faire une classe vraiment utile (par exemple, on ne nous demande même pas de pouvoir supprimer un mot, ou de lister tous les mots du dictionnaire).

Mais je préfère aussi la solution proposée par Médinoc, je pense que je vais opter pour celle-là.

Pour la fonction reinitialiser(), elle appelle effacer(), puis elle reconstruit un dictionnaire "vide", qui est en fait un arbre binaire non pas vide mais contenant la seule chaine vide "" à son sommet (ceci afin de ne pas avoir à traiter le cas d'un arbre vide dans les algorithmes).
Donc si le destructeur est appellé après reinitialiser() il n'y a pas de problème, il détruit juste l'arbre ("" (gauche: NULL) (droite: NULL)), sans détruire une deuxième fois l'arbre déjà détruit.

Je met le sujet en résolu, ça me semble bon comme ça, merci en tout cas :)

pff, c'est quoi ce prof ? Il a déjà une fois programmé en C++ ? Ou même en C moderne ?

void inserer(const char*) !
bool chercher(const char*) !

Et ça, c'est en C, je parle même pas de ce que tu devrais faire en C++ (utiliser des string).
La meilleure solution serait d'encapsuler tes pointeurs gauche droite sans un boost::scoped_ptr, mais j'imagine que ton prof n'en voudrait pas. Mais marque au moins que ce serait dans un monde professionnel le minimum à faire (tout ce qui a été indiqué ici).

Après, on se demande pourquoi les applications plantent... Pas étonnant.

C'était mon coup de gueule du jour :D

+1 avec Médinoc ;)