Arbre Binomial en C++

**Nono Sto** · 03/01/2011, 21h24

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** · 04/01/2011, 17h32

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

**Nono Sto** · 04/01/2011, 20h31

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** · 05/01/2011, 09h41

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** · 05/01/2011, 15h15

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** · 06/01/2011, 13h34

~~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().

**Oussapik** · 06/01/2011, 15h51

Envoyé par 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().

Hum, j'avoue être assez troublé car je ne vois pas l'intérêt de ne pas être statique ici. Oui, on appelle cree_fils() sur this. Mais dans les appels de creer_generation, le paramètre fournit est toujours l'objet sur lequel on appelle la fonction (arbre.creer_generation(arbre)).

Bon, là n'est pas le problème que rencontre Nono Sto, mais ça me perturbe un peu dans la lecture ^^

Pour ton problème, j'ai l'impression que dans la boucle for de la focntion creer_generation, tu ne prend en compte que n_node ou n_node->fils_haut. Donc forcément, tu n'ira pas après la seconde génération. Il faudrait a mon avis que tu parcours l'arbre en profondeur pour trouver le fils de la génération avec le nombre le plus grand.

**Nono Sto** · 07/01/2011, 10h28

Merci

La fonction creer_generation creer une seule generation, la boucle for parcours tous les noeud d'une generation et chaque noeud creer le fils haut et le fils bas.

Pour creer une seconde, troisieme,.....,Nieme generation j'utilise creer arbre, c'est là que l'on "empile" les generation pour creer un arbre.

**Nono Sto** · 10/01/2011, 05h46

Cheres amies, amis du forum

J'ai enfin réussi à creer mon arbre avec le code suivant:

Noeud.cpp (pour le noeud.h voir message precedent il n'a pas changé)

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
#include "noeud.h"
 
void noeud::cree_generation(noeud *n_node) 
{
	noeud *pt;
	noeud *pt_sauv = NULL;
 
	for (pt = n_node; pt != NULL; pt = pt->frere_bas())
		{
			if ( pt_sauv == NULL)
			   {
					pt ->fils_haut = pt->cree_fils();
			   }
			else 
				{
					pt ->fils_haut = pt->frere_haut()->fils_bas;
					pt->fils_haut->pere_bas = pt;
				}
			pt->fils_bas = pt->cree_fils();
			pt_sauv = pt->fils_bas ;
		} ;
}
 
noeud* noeud::creer_arbre (int n) 
{
	int i ;
	noeud *pt;
	noeud *arbre;
	arbre = new noeud;
	pt = arbre;
 
	for ( i = 0 ; i < n ; i++) 
	{	
		arbre->cree_generation(pt);
		pt = pt->fils_haut;
	};
	return (arbre);
}

main

Code :

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

1
2
3
4
5
6
7
8
9
10
11
#include "noeud.h"
#include "Option.h"
 
int main()
{
	noeud *node;
	node = new noeud;
	node=node->creer_arbre(3);
	int a=0;
	return 0;
}

Cependant un nouveaux problème se pose à moi.

Je dois écrire une fonction init_arbre dont le prototype est le suivant :

Code :

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

1
2
 
void init_arbre ( t_noeud * const arbre , double x_0 , double a , double b ) ;

je dois ensuite tester cette fonction avec un programme qui construit l’arbre suivant :

100
110 90
121 99 81
133.1 108.9 8 9.1 72 .9
146.41 119.79 98.01 80.19 65.61
161.051 131.769 107.811 88.209 72.171 59.049

il est clair x_0=100, a = 1.1, b = 0.9 et le premier parametre l'arbre que je viens de creer.

En plus de n'avoir aucune idée de l'agoritme à utiliser,
impossible d'acceder au pointeur valeurs de chaque noeud, j'ai reussi à initier le pointeur valeurs du premiers noeud à x_0=100 avec une instruction du genre:

Code :

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

arbre->valeurs = &x_0;

mais par exemple les noeud suivant j'ai toujours un message d'erreur du type:

-noeud* arbre doit etre de type arithmétique ou enum

avec les instructions suivante:

Code :

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

1
2
3
4
5
6
7
if (arbre->fils_haut->valeurs==NULL) 
		 {	
			arbre->fils_haut->valeurs = arbre->valeurs*a;
		 }
	else {
			arbre->fils_bas->valeurs[0]	= arbre->valeurs[0]*a;					
		 }

Merci

Arbre Binomial en C++

C++

Discussions similaires

Partager

Partager