Discussion :

[Nono Sto]

Chères amies , chers amis du forum

Je me retourne à nouveaux vers vous pour mon probleme d'arbre binomial j'ai avancé cependant là je retrouve devant une difficulté que je n'arrive pas à résoudre.

j'ai tenté de créer une fonction creer_generation(), qui creer justement une generation.

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
void noeud::cree_generation(noeud &n_node) 
{
	noeud *pt;
	//n_node.fils_haut = new noeud;
	noeud *pt_sauv=n_node.fils_haut;
	//pt = n_node->frere_bas();
 
for (pt = &n_node; pt != NULL; pt = n_node.frere_bas())
	{
		if ( pt_sauv == NULL) pt ->fils_haut = n_node.cree_fils();
			else {
				pt->fils_haut =n_node.fils_haut;
				pt->fils_haut->pere_bas = &n_node;
				 }
				pt->fils_bas = cree_fils();
				pt_sauv = pt->fils_bas ;
} ;
}

et pour creer un arbre j'essaye d'utiliser une fonction créer arbre:

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
 
void noeud::creer_arbre ( int n) 
{
	int i ;
	noeud pt;
	noeud arbre;
 
	pt = arbre ;
 
	for ( i = 0 ; i < n ; i++) 
	{	
 
		arbre.cree_generation(arbre);
		pt = arbre;
	}
}

cependant je n'arrive pas à creer au dela de la deuxieme generation (voir l'image)


Merci pour votre aide.

Rappel:

Je reprend tous depuis le départ :

je considere un arbre dont chaque noeud N contient une valeur réelle y définie à partir de la valeur x du noeud père : y = f(x) si N est le fils “haut”, et y = g(x) si N est le fils “bas”. C'est un arbre binomial, voir le petit schema.

Il peut avoir des noeud avec deux père différent: le père “haut” et le père “bas”
Ainsi on peut représenter un noeud grâce à la classe suivante:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
class noeud
{
	public :
	noeud(): valeurs ( NULL ), fils_haut ( NULL ),
			fils_bas ( NULL ), pere_haut ( NULL ), pere_bas ( NULL ){};
 
	noeud ( const noeud &n) : pere_haut (n. pere_haut ), pere_bas (n. pere_bas ),
				valeurs (n. valeurs ), fils_haut (n. fils_haut ),
				fils_bas (n. fils_bas){};
 
	~noeud () { delete [] valeurs ;};

Dans la suite, j'appelle génération k d’un arbre l’ensemble des noeuds de la kiéme itération (voir à nouveau schema).



On choisit de construire l’arbre génération par génération. Pour commencer on alloue l’espace nécessaire pour un fils et on initialise sa valeur à 0, grâce au constructeur par défaut. Puis à partir d'un noeud on créer les fils grace à la fonction suivante: elle teste d'abord si il existe un fils haut, si oui elle créer le fils bas sinon elle creer le fils haut.

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
noeud * cree_fils () {
			noeud * nouveau =new noeud ;
			if ( fils_haut == NULL ) {
								nouveau -> pere_bas = this ;
								nouveau -> pere_haut = frere_haut ();
								if ( frere_haut ()!= NULL )
										nouveau -> pere_haut -> fils_bas = nouveau ;
										fils_haut = nouveau ;
									 }
			else {
								nouveau -> pere_haut = this ;
										nouveau -> pere_bas = frere_bas ();
										if ( frere_bas ()!= NULL )
												nouveau -> pere_bas -> fils_haut = nouveau ;
										fils_bas = nouveau ;
				 }
			return nouveau ;
};

De plus voici les code de deux fonctions : frere_bas qui renvoie l’adresse du frère “bas” d’un noeud (le noeud de même génération situé juste en-dessous),
et qui renvoie NULL s’il n’existe pas. De meme pour le frere haut :

Code :

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

1
2
3
4
5
6
7
noeud * frere_haut ()
			{ return ( pere_haut == NULL ) ? NULL : pere_haut -> fils_haut ;};
 
	noeud * frere_bas ()
			{ 
				return ( pere_bas == NULL ) ? NULL : pere_bas -> fils_bas ;
			};

[Médinoc]

Tu parles de ce genre d'arbre binomial?
http://en.wikipedia.org/wiki/Binomial_tree

[Nono Sto]

A peu de chose près que ce sont des arbre recombinant: nous considérons un arbre dont chaque nœud N contient une valeur réelle y définie à partir de la valeur x du nœud père : y = f(x) si N est le fils “haut”, et y = g(x) si N est le fils “bas”. Les fonctions f et g vérifient la condition suivante
f ° g = g ° f:
Sous cette hypothèse, on a à la seconde génération: X_haut_bas = X_bas_haut
On considère alors que c’est le même nœud avec deux pères différents : le père “haut” qui sera X_haut et le père “bas” qui sera X_bas.

[Médinoc]

Ah, je crois que je vois (même si je suis un peu désorienté car tu dis "haut" et "bas" là où je dis "gauche" et "droite").

Par contre, j'ai du mal à comprendre la fonction cree_generation(). Est-ce une fonction statique?

[Nono Sto]

Merci

Non ce n'est pas une fonction statique, la fonction creer_generation doit avoir un objet nœud en paramètre, elle part du premier nœud de la generation, le plus haut ou si tu prefere le plus à gauche et descend noeud par noeud.

[Médinoc]

J'ai peut-être la berlue, mais j'ai pourtant l'impression qu'elle ne touche à aucune variable membre de this...

Edit: Ah, je n'avais pas vu cree_fils().