Partage

Arbre binaire (Destruction d'un noeud)

Sujet résolu

anonyme

Le 13 octobre 2008 à 20:47:36

Bonjour à tous.

Voilà, je suis en train de coder une class Noeud pour faire un arbre binaire, seulement, un petit problème apparait.
A la fin de mon programme, je souhaite supprimer l'arbre que je viens de créer, et là, j'ai le droit à ceci : "Erreur de segmentation" :s

Voici un peu mon code :

#include <iostream>
#include <list>

#include "Noeud.h"

using namespace std;
typedef Noeud Arbre;

int main(int argc, char **argv)
{
	string expression;
	list<Noeud*> pile;
	Arbre *arbre = NULL;
	Noeud *nouveauNoeud = NULL;

	cout << "Entrez une expression postfixée : ";
	getline(cin, expression);

	for(int i = 0 ; i < expression.size() ; i++)
	{
		nouveauNoeud = new Noeud(expression[i]);

		if((expression[i] == '+') || (expression[i] == '-') || (expression[i] == '*') || (expression[i] == '/'))
		{
				nouveauNoeud->setFilsDroit(pile.back());

				pile.pop_back();
				nouveauNoeud->setFilsGauche(pile.back());
				pile.pop_back();
		}

		pile.push_back(nouveauNoeud);
	}


	arbre = new Noeud(pile.back());



	delete nouveauNoeud;
	delete arbre;

	return 0;
}

Et, je sais que l'erreur se produit lorsque je fais delete arbre; .

Voici mon destructeur pour Noeud.cpp :

/* du code avant */

Noeud::~Noeud()
{
	if(m_gauche != NULL)
		delete m_gauche;
	
	if(m_droit != NULL)
		delete m_droit;
}

/* du code après */

Voilà, je ne comprends pas vraiment pourquoi j'ai cette erreur je dois avouer...

Si quelqu'un à une piste, je suis preneur !

Le 13 octobre 2008 à 20:47:36

chlablak

Le 13 octobre 2008 à 20:56:56

Il est inutile de tester si un pointeur n'est pas nul avant un delete.

Sinon juste avec ça on pourra pas t'aider, fait un code minimal.

anonyme

Le 13 octobre 2008 à 21:03:58

Très bien.

Voici ma class Noeud complète :

#ifndef DEF_NOEUD
#define DEF_NOEUD

#include <iostream>


class Noeud;

class Noeud
{
	public :
		Noeud(char donnees);
		Noeud(Noeud *gauche, Noeud *droit, char donnees);
		Noeud(Noeud *noeud);
		~Noeud();

		char getDonnees();
		Noeud* getFilsGauche();
		Noeud* getFilsDroit();
		void setFilsGauche(Noeud *gauche);
		void setFilsDroit(Noeud *droit);
		bool possedeFils();
		bool filsGauche();
		bool filsDroit();



	private :
		Noeud *m_gauche;
		Noeud *m_droit;
		char m_donnees; //Contient la données (nombre, caractère...);
};

#endif

#include <iostream>
#include "Noeud.h"

Noeud::Noeud(char donnees)
{
	m_donnees = donnees;
	m_droit = NULL;
	m_gauche = NULL;
}

Noeud::Noeud(Noeud *gauche, Noeud *droit, char donnees)
{
	m_donnees = donnees;
	m_droit = new Noeud(*droit);
	m_gauche = new Noeud(*gauche);
}

Noeud::Noeud(Noeud *noeud)
{
	m_donnees = noeud->m_donnees;
	m_droit = noeud->m_droit;
	m_gauche = noeud->m_gauche;
}

Noeud::~Noeud()
{
	if(m_gauche != NULL)
		delete m_gauche;
	
	if(m_droit != NULL)
		delete m_droit;
}

void Noeud::setFilsGauche(Noeud *gauche)
{
	m_gauche = gauche; 
}

void Noeud::setFilsDroit(Noeud *droit)
{
	m_droit = droit;
}
	

char Noeud::getDonnees() { return m_donnees; }
Noeud* Noeud::getFilsGauche() { return m_gauche; }
Noeud* Noeud::getFilsDroit() { return m_droit; }

bool Noeud::possedeFils()
{
	if(filsGauche() || filsDroit())
		return true;
	else
		return false;
}

bool Noeud::filsGauche()
{
	if(m_gauche != NULL)
		return true;
	else
		return false;
}

bool Noeud::filsDroit()
{
	if(m_droit != NULL)
		return true;
	else
		return false;
}

chlablak

Le 13 octobre 2008 à 21:18:36

- Pourquoi tu fais une déclaration anticipé dans ton header ?
- Utilises la liste d'initialisation au maximum.
- Comme déjà dit, il est inutile de tester si un pointeur n'est pas nul avant un delete.
- J'ai pas trop confiance en tes constructeurs n°2 (réallocation) et n°3 (copie du pointeur).
- les "if(a == b) return true; else return false;" c'est moche, "return a == b;" suffit.
- Je comprends pas ce que tu cherches à faire dans ton main().

Corriges ton code en conséquence et commentes (ou expliques) mieux ce que tu veux faire, Courage.

anonyme

Citation : Chlab_lak<blockquote>- Pourquoi tu fais une déclaration anticipé dans ton header ?</blockquote> J'ai toujours cru que lorsqu'on utilisait un objet dans l'objet lui-même, il fallait faire une déclaration anticipée. Force est de constater que non. Citation : Chlab_lak<blockquote>- Utilises la liste d'initialisation au maximum.</blockquote> c'est-à-dire ? Liste d'initialisation ? Citation : Chlab_lak<blockquote>- Comme déjà dit, il est inutile de tester si un pointeur n'est pas nul avant un delete.</blockquote> Corrigé. Citation : Chlab_lak<blockquote>- J'ai pas trop confiance en tes constructeurs n°2 (réallocation) et n°3 (copie du pointeur).</blockquote> Modifié. (Mieux ?) Citation : Chlab_lak<blockquote>- les "if(a == b) return true; else return false;" c'est moche, "return a == b;" suffit.</blockquote> Corrigé. Citation : Chlab_lak<blockquote>- Je comprends pas ce que tu cherches à faire dans ton main().</blockquote> Alors en fait, je voudrais construire un arbre binaire selon une expression postfixée. Par exemple, l'expression mathématique "A + B" en écriture postfixée donne "AB+", et c'est par rapport à cette expression que je construis mon arbre. Ainsi, si je tombe sur un signe mathématique, j'ajoute les deux derniers éléments de la pile à l'arbre, sinon, je met l'élément dans la pile, en attendant de tomber sur un signe... Voici mes modifications : <pre class="brush: cpp;">#include <iostream> #include <list> #include "Noeud.h" using namespace std; typedef Noeud Arbre; int main(int argc, char **argv) { string expression; list<Noeud*> pile; Arbre *arbre = NULL; Noeud *nouveauNoeud = NULL; cout << "Entrez une expression postfixée : "; getline(cin, expression); for(int i = 0 ; i < expression.size() ; i++) { nouveauNoeud = new Noeud(expression[i]); if((expression[i] == '+') || (expression[i] == '-') || (expression[i] == '*') || (expression[i] == '/')) { nouveauNoeud->setFilsDroit(pile.back()); pile.pop_back(); nouveauNoeud->setFilsGauche(pile.back()); pile.pop_back(); } pile.push_back(nouveauNoeud); } arbre = new Noeud(*pile.back()); delete nouveauNoeud; //delete arbre; return 0; } </pre> <pre class="brush: cpp;">#ifndef DEF_NOEUD #define DEF_NOEUD #include <iostream> class Noeud { public : Noeud(const char donnees); Noeud(const Noeud &gauche, const Noeud &droit, const char donnees); Noeud(const Noeud &noeud); ~Noeud(); char getDonnees(); Noeud* getFilsGauche(); Noeud* getFilsDroit(); void setFilsGauche(Noeud *gauche); void setFilsDroit(Noeud *droit); bool possedeFils(); bool filsGauche(); bool filsDroit(); private : Noeud *m_gauche; Noeud *m_droit; char m_donnees; //Contient la données (nombre, caractère...); }; #endif </pre> <pre class="brush: cpp;">#include <iostream> #include "Noeud.h" Noeud::Noeud(const char donnees) { m_donnees = donnees; m_droit = NULL; m_gauche = NULL; } Noeud::Noeud(const Noeud &gauche, const Noeud &droit, const char donnees) { m_donnees = donnees; m_droit = new Noeud(droit); m_gauche = new Noeud(gauche); } Noeud::Noeud(const Noeud &noeud) { m_donnees = noeud.m_donnees; m_droit = new Noeud(*(noeud.m_droit)); m_gauche = new Noeud(*(noeud.m_gauche)); } Noeud::~Noeud() { delete m_gauche; delete m_droit; } void Noeud::setFilsGauche(Noeud *gauche) { m_gauche = gauche; } void Noeud::setFilsDroit(Noeud *droit) { m_droit = droit; } char Noeud::getDonnees() { return m_donnees; } Noeud* Noeud::getFilsGauche() { return m_gauche; } Noeud* Noeud::getFilsDroit() { return m_droit; } bool Noeud::possedeFils() { return filsGauche() || filsDroit(); } bool Noeud::filsGauche() { if(m_gauche != NULL) return true; else return false; } bool Noeud::filsDroit() { if(m_droit != NULL) return true; else return false; } </pre> Le problème initial est toujours là, soit dit en passant... Le 13 octobre 2008 à 22:23:56

Citation : Chlab_lak

- Pourquoi tu fais une déclaration anticipé dans ton header ?

J'ai toujours cru que lorsqu'on utilisait un objet dans l'objet lui-même, il fallait faire une déclaration anticipée. Force est de constater que non.

Citation : Chlab_lak

- Utilises la liste d'initialisation au maximum.

c'est-à-dire ? Liste d'initialisation ?

Citation : Chlab_lak

- Comme déjà dit, il est inutile de tester si un pointeur n'est pas nul avant un delete.

Corrigé.

Citation : Chlab_lak

- J'ai pas trop confiance en tes constructeurs n°2 (réallocation) et n°3 (copie du pointeur).

Modifié. (Mieux ?)

Citation : Chlab_lak

- les "if(a == b) return true; else return false;" c'est moche, "return a == b;" suffit.

Corrigé.

Citation : Chlab_lak

- Je comprends pas ce que tu cherches à faire dans ton main().

Alors en fait, je voudrais construire un arbre binaire selon une expression postfixée. Par exemple, l'expression mathématique "A + B" en écriture postfixée donne "AB+", et c'est par rapport à cette expression que je construis mon arbre. Ainsi, si je tombe sur un signe mathématique, j'ajoute les deux derniers éléments de la pile à l'arbre, sinon, je met l'élément dans la pile, en attendant de tomber sur un signe...

Voici mes modifications :

#include <iostream>
#include <list>

#include "Noeud.h"

using namespace std;
typedef Noeud Arbre;

int main(int argc, char **argv)
{
	string expression;
	list<Noeud*> pile;
	Arbre *arbre = NULL;
	Noeud *nouveauNoeud = NULL;

	cout << "Entrez une expression postfixée : ";
	getline(cin, expression);

	for(int i = 0 ; i < expression.size() ; i++)
	{
		nouveauNoeud = new Noeud(expression[i]);

		if((expression[i] == '+') || (expression[i] == '-') || (expression[i] == '*') || (expression[i] == '/'))
		{
				nouveauNoeud->setFilsDroit(pile.back());
				pile.pop_back();
				nouveauNoeud->setFilsGauche(pile.back());
				pile.pop_back();
		}

		pile.push_back(nouveauNoeud);
	}


	arbre = new Noeud(*pile.back());



	delete nouveauNoeud;
	//delete arbre;

	return 0;
}

#ifndef DEF_NOEUD
#define DEF_NOEUD

#include <iostream>

class Noeud
{
	public :
		Noeud(const char donnees);
		Noeud(const Noeud &gauche, const Noeud &droit, const char donnees);
		Noeud(const Noeud &noeud);
		~Noeud();

		char getDonnees();
		Noeud* getFilsGauche();
		Noeud* getFilsDroit();
		void setFilsGauche(Noeud *gauche);
		void setFilsDroit(Noeud *droit);
		bool possedeFils();
		bool filsGauche();
		bool filsDroit();



	private :
		Noeud *m_gauche;
		Noeud *m_droit;
		char m_donnees; //Contient la données (nombre, caractère...);
};

#endif

#include <iostream>
#include "Noeud.h"

Noeud::Noeud(const char donnees)
{
	m_donnees = donnees;
	m_droit = NULL;
	m_gauche = NULL;
}

Noeud::Noeud(const Noeud &gauche, const Noeud &droit, const char donnees)
{
	m_donnees = donnees;
	m_droit = new Noeud(droit);
	m_gauche = new Noeud(gauche);
}

Noeud::Noeud(const Noeud &noeud)
{
	m_donnees = noeud.m_donnees;
	m_droit = new Noeud(*(noeud.m_droit));
	m_gauche = new Noeud(*(noeud.m_gauche));
}

Noeud::~Noeud()
{
	delete m_gauche;
	delete m_droit;
}

void Noeud::setFilsGauche(Noeud *gauche)
{
	m_gauche = gauche; 
}

void Noeud::setFilsDroit(Noeud *droit)
{
	m_droit = droit;
}
	

char Noeud::getDonnees() { return m_donnees; }
Noeud* Noeud::getFilsGauche() { return m_gauche; }
Noeud* Noeud::getFilsDroit() { return m_droit; }

bool Noeud::possedeFils() { return filsGauche() || filsDroit(); }

bool Noeud::filsGauche()
{
	if(m_gauche != NULL)
		return true;
	else
		return false;
}

bool Noeud::filsDroit()
{
	if(m_droit != NULL)
		return true;
	else
		return false;
}

Le problème initial est toujours là, soit dit en passant...

chlablak

Citation : TuxWeb<blockquote> Citation : Chlab_lak <blockquote>- Utilises la liste d'initialisation au maximum.</blockquote> c'est-à-dire ? Liste d'initialisation ?</blockquote> Par exemple pour ton premier constructeur: <pre class="brush: cpp;">Node::Node(char Value) : myValue(Value) , myLeft(0) // ou NULL si tu préfères , myRight(0) {} </pre> Citation : TuxWeb<blockquote> Citation : Chlab_lak <blockquote>- J'ai pas trop confiance en tes constructeurs n°2 (réallocation) et n°3 (copie du pointeur).</blockquote> Modifié. (Mieux ?)</blockquote> Il me semble que c'est mieux, j'ai pas chercher trop loin, mais on peut faire surement mieux. Citation : TuxWeb<blockquote> Citation : Chlab_lak <blockquote>- les "if(a == b) return true; else return false;" c'est moche, "return a == b;" suffit.</blockquote> Corrigé.</blockquote> Tu n'as pas tout corrigé. Citation : TuxWeb<blockquote>Ainsi, si je tombe sur un signe mathématique, j'ajoute les deux derniers éléments de la pile à l'arbre</blockquote> Si tu as A+B: 1) Tu rajoutes A à la liste 2) Il y a une opération => Tu assignes au noeud droit A puis tu l'enlèves de la liste => Ensuite tu refais appelles à back() alors qu'il n'y a plus rien dans la liste => Boum Citation : TuxWeb<blockquote> sinon, je met l'élément dans la pile, en attendant de tomber sur un signe...</blockquote> Je vois pas vraiment où se trouve ton sinon (else) <img src="/bundles/tinymce/vendor/tiny_mce/plugins/emotions/img/clin.png" alt=";)" class="smilies"> Je pense pas que tout soit corrigé, mais je te conseille de reprendre ta conception depuis le début car je trouve ton code trop obscure/mal organisé (c'est sans doute pas les meilleures mots mais là je sèche). Le 13 octobre 2008 à 23:15:57

Citation : TuxWeb

Citation : Chlab_lak

- Utilises la liste d'initialisation au maximum.

c'est-à-dire ? Liste d'initialisation ?

Par exemple pour ton premier constructeur:

Node::Node(char Value)
: myValue(Value)
, myLeft(0) // ou NULL si tu préfères
, myRight(0)
{}

Citation : TuxWeb

Citation : Chlab_lak

- J'ai pas trop confiance en tes constructeurs n°2 (réallocation) et n°3 (copie du pointeur).

Modifié. (Mieux ?)

Il me semble que c'est mieux, j'ai pas chercher trop loin, mais on peut faire surement mieux.

Citation : TuxWeb

Citation : Chlab_lak

- les "if(a == b) return true; else return false;" c'est moche, "return a == b;" suffit.

Corrigé.

Tu n'as pas tout corrigé.

Citation : TuxWeb

Ainsi, si je tombe sur un signe mathématique, j'ajoute les deux derniers éléments de la pile à l'arbre

Si tu as A+B:
1) Tu rajoutes A à la liste
2) Il y a une opération => Tu assignes au noeud droit A puis tu l'enlèves de la liste => Ensuite tu refais appelles à back() alors qu'il n'y a plus rien dans la liste => Boum

Citation : TuxWeb

sinon, je met l'élément dans la pile, en attendant de tomber sur un signe...

Je vois pas vraiment où se trouve ton sinon
(else)

Je pense pas que tout soit corrigé, mais je te conseille de reprendre ta conception depuis le début car je trouve ton code trop obscure/mal organisé (c'est sans doute pas les meilleures mots mais là je sèche).

Nanoc

Staff Le 14 octobre 2008 à 14:10:10

<citation rid="3049817

Citation : TuxWeb

Citation : Chlab_lak

- J'ai pas trop confiance en tes constructeurs n°2 (réallocation) et n°3 (copie du pointeur).

Modifié. (Mieux ?)

Il me semble que c'est mieux, j'ai pas chercher trop loin, mais on peut faire surement mieux. </citation>

Je pose plutot la question: Ces constructeurs ont-ils un sens ?

Sinon, tu peux essayer le debuggueur pour repérer ou se situe l'erreur.

Co-auteur du cours de C++. -> Posez vos questions sur le forum !

anonyme

Citation : Nanoc<blockquote> Je pose plutot la question: Ces constructeurs ont-ils un sens ? </blockquote> Il est vrai que le 2ième constructeur n'est pas utile, (mais je m'en étais servi avant). Néanmoins, pour le troisième, il trouve son sens dans le fait que j'en ai besoin pour recopier la qui est dans la pile sur mon arbre "final", non ? Dois-je procéder autrement ? Citation : Nanoc<blockquote> Sinon, tu peux essayer le debuggueur pour repérer ou se situe l'erreur. </blockquote> Je sais que l'erreur se trouve dans le destructeur de Noeud. Mais pas plus <img src="/bundles/tinymce/vendor/tiny_mce/plugins/emotions/img/triste.png" alt=":(" class="smilies">. Je vais voir ce que je peux avoir avec un débuggeur. Citation : Chlab_lak<blockquote> Citation : TuxWeb <blockquote> sinon, je met l'élément dans la pile, en attendant de tomber sur un signe...</blockquote> Je vois pas vraiment où se trouve ton sinon (else) <img src="/bundles/tinymce/vendor/tiny_mce/plugins/emotions/img/clin.png" alt=";)" class="smilies"> </blockquote> En fait, il n'y a pas de "sinon", il faut toujours ajouter l'élément dans la pile. Citation : Chlab_lak<blockquote> Si tu as A+B: 1) Tu rajoutes A à la liste 2) Il y a une opération => Tu assignes au noeud droit A puis tu l'enlèves de la liste => Ensuite tu refais appelles à back() alors qu'il n'y a plus rien dans la liste => Boum </blockquote> D'où l'interêt d'utiliser l'expression postfixée de A+B (à savoir AB+) Edit : Je vous donne les informations au fur et à mesure que je les obtiens. Alors mon débuggeur me dit ceci : <pre class="brush: plain;">Starting program: /home/tuxweb/Programmation/C++/Console/Algo/Chap5/Expression_algo/exe Entrez une expression postfixée : AB+ Program received signal SIGSEGV, Segmentation fault. 0x08049309 in Noeud (this=0x9957098, noeud=@0x0) at Noeud.cpp:20 20 m_donnees = noeud.m_donnees; Current language: auto; currently c++ (gdb)</pre> Je ne comprends pas pourquoi ça plante ici je dois dire... :s Edit2 : Après tests, il s'avèrerait que c'est tout le constructeur de copie qui fait planter :s Edit3 : C'est bon, ça fonctionne ! J'ai modifié mon constructeur de copie comme ceci : <pre class="brush: cpp;">Noeud::Noeud(const Noeud &noeud) { m_donnees = noeud.m_donnees; if(noeud.filsGauche()) m_gauche = new Noeud(*(noeud.m_gauche)); else m_gauche = NULL; if(noeud.filsDroit()) m_droit = new Noeud(*(noeud.m_droit)); else m_droit = NULL; } </pre> J'ai compris ce qu'il se passait réellement grâce au debuggeur. Je ne m'en étais jamais servi auparavant. Je dois avouer que c'est plutôt pratique et efficace ! Merci ! Le 14 octobre 2008 à 18:11:20

Citation : Nanoc

Je pose plutot la question: Ces constructeurs ont-ils un sens ?

Il est vrai que le 2ième constructeur n'est pas utile, (mais je m'en étais servi avant). Néanmoins, pour le troisième, il trouve son sens dans le fait que j'en ai besoin pour recopier la qui est dans la pile sur mon arbre "final", non ? Dois-je procéder autrement ?

Citation : Nanoc

Sinon, tu peux essayer le debuggueur pour repérer ou se situe l'erreur.

Je sais que l'erreur se trouve dans le destructeur de Noeud. Mais pas plus

. Je vais voir ce que je peux avoir avec un débuggeur.

Citation : Chlab_lak

Citation : TuxWeb

sinon, je met l'élément dans la pile, en attendant de tomber sur un signe...

Je vois pas vraiment où se trouve ton sinon
(else)

En fait, il n'y a pas de "sinon", il faut toujours ajouter l'élément dans la pile.

Citation : Chlab_lak

Si tu as A+B:
1) Tu rajoutes A à la liste
2) Il y a une opération => Tu assignes au noeud droit A puis tu l'enlèves de la liste => Ensuite tu refais appelles à back() alors qu'il n'y a plus rien dans la liste => Boum

D'où l'interêt d'utiliser l'expression postfixée de A+B (à savoir AB+)

Edit : Je vous donne les informations au fur et à mesure que je les obtiens.

Alors mon débuggeur me dit ceci :

Starting program: /home/tuxweb/Programmation/C++/Console/Algo/Chap5/Expression_algo/exe 
Entrez une expression postfixée : AB+

Program received signal SIGSEGV, Segmentation fault.
0x08049309 in Noeud (this=0x9957098, noeud=@0x0) at Noeud.cpp:20
20                m_donnees = noeud.m_donnees;
Current language:  auto; currently c++
(gdb)

Je ne comprends pas pourquoi ça plante ici je dois dire... :s

Edit2 : Après tests, il s'avèrerait que c'est tout le constructeur de copie qui fait planter :s

Edit3 : C'est bon, ça fonctionne !

J'ai modifié mon constructeur de copie comme ceci :

Noeud::Noeud(const Noeud &noeud)
{
	m_donnees = noeud.m_donnees;
	
	if(noeud.filsGauche())
		m_gauche = new Noeud(*(noeud.m_gauche));
	else
		m_gauche = NULL;

	if(noeud.filsDroit())
		m_droit = new Noeud(*(noeud.m_droit));
	else
		m_droit = NULL;
}

J'ai compris ce qu'il se passait réellement grâce au debuggeur. Je ne m'en étais jamais servi auparavant. Je dois avouer que c'est plutôt pratique et efficace !

Merci !