Arbre Binomial en C++

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:

---

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:

---

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)
http://www.developpez.net/forums/att...3&d=1294082560

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:

---

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

http://www.developpez.net/forums/att...5&d=1294086025

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:

---

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:

---

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 ; };

---

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

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.

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?

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.

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

Citation:

---

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.

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.

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:

---

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:

---

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:

---

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:

---

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:

---

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