Discussion :

[valderama]

Bonjour,

Je souhaite implémenter des arbres N-aires, avec une structure de vecteurs, afin de pouvoir construire mon arbre dynamiquement.
J'ai donc crée une classe PrefixNode défini ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
class PrefixNode;
typedef string ItemType;
typedef vector<PrefixNode*> VectChild;
class PrefixNode {
 
private:
 
	ItemType 	Val;
	int      	Proba;
	int 		Niveau;
 
	//Calcul du Niveau
	void CalculerNiveau();
 
	//calcul la probabilité du noeud courant
	void CalculerProba();
 
public:
 
	//Liens
	VectChild	Successeurs;
        PrefixNode* 	Pere;
 
       //Constructeur par défault
       PrefixNode(){};
 
       //Constructeur
	PrefixNode(ItemType S){
		Val 		= S;
		Proba 		= 0;
		Niveau 		= 0;
		Pere		= NULL;
	}
        // Accesseurs
	ItemType 	getVal() const;
	int 	 	getProba() const;
	int     	getNiveau() const;
	VectChild getChildren() const;
	PrefixNode* getFather() const;
 
	// Mutateurs
	void setVal(ItemType);
	void setSuccesseurs(VectChild);
	void setNiveau(int);
 
	//Affichage
	void PrintNode();
	void PrintTree();
 
	//Gestion des noeuds enfants
	void CreateChildren(ItemType);
};

Un PrefixNode comporte donc ses attributs(valeur,niveau,etc...)et un vector de pointeurs vers des PrefixNode. Je ne sais pas si cette structure est optimale, mais elle me semble cohérente.

Il semble que j'ai un problème dans la méthode CreateChildren qui ajoute un Noeud Fils au noeud qui appelant ( créé un nouveau fils si aucun fils, ajoute un frère si un ou plusieurs fils est déjà présent). Je vous donne son code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void PrefixNode::CreateChildren(ItemType S){
 
	VectChild::iterator it;
	VectChild::iterator it2;
 
	if (Successeurs.empty()){
		//créer 1 fils
		(Successeurs).push_back(new PrefixNode(S));
		it=(Successeurs).begin();
		(*it)->Pere = this;
		(*it)->CalculerNiveau();
		(*it)->CalculerProba();
	}
 
	else{
		//creer un frere
		(Successeurs).push_back(new PrefixNode(S));
		 it2=(Successeurs).end();
		(*it)->Pere = this;
		(*it)->CalculerNiveau();
		(*it)->CalculerProba();
	}
}

Je teste tout ça en créant d'abord un premier fils, puis en créant ce qui devrai être un frère de ce dernier. Ce qui se fait par le main suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
int main() {
 
			PrefixNode* racine;
			racine= new PrefixNode("ROOT");
		        racine->CreateChildren("FILS1");
		       (racine)->PrintTree();
        	       (racine)->CreateChildren("FILS11");racine->PrintTree();
 
return 0;
}

A l'éxecution, le programme plante à la création du frère. ça affiche ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
+ Noeud (0x20fd0) :
 - Niveau = 0
 - Valeur= ROOT
 - Predecesseur = 0
 - Successeurs= { 0x21018 }
  + Noeud (0x21018) :
   - Niveau = 1
   - Valeur= FILS1
   - Predecesseur = 0x20fd0
   - Successeurs= { Aucun }

...puis ça plante. Le frère "FILS11" n'est pas crée.Je m'arrache les cheveux depuis des heures; donc je fais appel à vos connaissances ! Je débute vraiment en c++, est-il besoin de le préciser ... Merci par avance de votre aide.

[Sylvain Togni]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
		//creer un frere
		(Successeurs).push_back(new PrefixNode(S));
		 it2=(Successeurs).end();

Attention ici it2 ne va pas pointer sur le dernier élément mais une position après. Le dernier élément c'est *(Successeurs.end()-1) ou Successeurs.back().

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
		(*it)->Pere = this;
		(*it)->CalculerNiveau();
		(*it)->CalculerProba();

Attention ici it est utilisé sans avoir été initialisé.

[valderama]

Merci beaucoup pour votre réponse. ça marche en prenant effectivement it2=(Successeurs).end()-1.
je vais pouvoir travailler sur mes algo de recherche maintenant que la structure est bien définie

[loufoque]

Pourquoi ne pas utiliser un variant ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef boost::make_recursive_variant<
    std::string,
    std::vector< boost::recursive_variant_ >
>::type string_tree_t;