Créer un arbre récursivement

Bonjour,
je cherche à créer un arbre en rajoutant un élément à chaque tour de ma boucle. Le problème que je rencontre est que je n'arrive pas à remonter dans mon arbre pour rajouter certaines valeurs.
Je pense que la conception de ma fonction qui ajoute l'élément n'est pas bonne.
Voici une partie de mon code :

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 39

//ma structure typedef struct s_noeud { char *op; double nb; struct s_noeud *fg,*fd; }noeud,*arbre;   //fonction qui ajoute l'élément arbre enrac(arbre a,char *x) { if (a->op==NULL) { a->op=x; a->fg=NULL; a->fd=NULL; return a; }   if (a->fg==NULL) { a->fg=enrac(a->fg,x); return a->fg; }   if( a->fd==NULL) { a->fd=enrac(a->fd,x); return a; }   }   //la boucle qui me permet de créer l'arbre while( bout != NULL ) { a=enrac(a,bout); bout = strtok(NULL, espace); }

---

Merci d'avance pour votre aide

Ton algorithme est faux, ou plus exactement mal implémenté. Que se passe-t-il dans la fonction enrac lorsqu'aucune des trois conditions testées n'est vérifiée ?

Peux-tu déjà nous décrire ton algo en français (pas en C) ?

À aucun moment tu ne gères le cas où a est NULL, alors que tu fais des appels où c'est forcément le cas!

Citation:

---

Envoyé par Matt_Houston

Ton algorithme est faux, ou plus exactement mal implémenté. Que se passe-t-il dans la fonction enrac lorsqu'aucune des trois conditions testées n'est vérifiée ?

---

Je pense que quand aucune des conditions n'est vérifiée, il faudrait avancer dans l'arbre et faire a=a->fg ?

Citation:

---

Envoyé par Matt_Houston

Peux-tu déjà nous décrire ton algo en français (pas en C) ?

---

bout peut avoir 3 valeurs différentes et suivant les valeurs, il va soit constituer une feuille, soit un noeud avec deux fils, soit un noeud avec 1 seul fils gauche.
Je pensais renvoyer avec enrac le noeud où je rajouterai au prochain appel récursif, mais je n'arrive pas à remonter dans mon arbre de cette manière.

Exemple pour mieux me faire comprendre :
bout prend les valeurs :
bout=1;
-> créer noeud1 avec fg et fd
bout=1
-> créer noeud2 à partir de fg et faire 2 branches (comme précédement)
bout=3
->créer feuille à partir de fg du noeud2
bout=3
->créer feuille à partir de fd du noeud2
bout=3
->créer feuille à partir de fd du noeud1 (je ne vois pas comment je pourrais remonter jusque là)

Pour faire simple, si je tape '+ * 1 2 3'
Pièce jointe 270499

Citation:

---

Envoyé par KiitKaate

Pour faire simple, si je tape '+ * 1 2 3'
Pièce jointe 270499

---

Bonjour

Ton dessin est une illustration de l'opération "1 * 2 + 3". J'aurais plutôt tendance alors à penser que c'est dans cet ordre qu'on devrait taper cette expression non ??? Surtout que l'algorithme pour la lire et la traiter (en respectant les priorités) existe déjà (Backus-Naur Form) et a été discuté ici.

En revanche, si on entre "+ * 1 2 3" mais qu'on la lit en partant de la fin pour revenir au début, alors cela correspond à une "Polonaise Inversée" mais qui n'a pas besoin d'arbre pour être traitée car ça se gère avec une simple pile

Code:

---

1 2 3 4 5 6 7 8

Pour chaque entrée, faire si entrée est chiffre alors empilement sinon dépiler 2 derniers chiffres calculer l'opération avec l'entrée comme opérateur empiler le résultat fin si fin faire

---

Et ça marche aussi si on l'entre ainsi: "+ 3 * 2 1" (toujours en partant de la fin vers le début)

Citation:

---

Envoyé par Sve@r

Bonjour

Ton dessin est une illustration de l'opération "1 * 2 + 3". J'aurais plutôt tendance alors à penser que c'est dans cet ordre qu'on devrait taper cette expression non ??? Surtout que l'algorithme pour la lire et la traiter (en respectant les priorités) existe déjà (Backus-Naur Form) et a été discuté ici.

En revanche, si on entre "+ * 1 2 3" mais qu'on la lit en partant de la fin pour revenir au début, alors cela correspond à une "Polonaise Inversée" mais qui n'a pas besoin d'arbre pour être traitée car ça se gère avec une simple pile

Code:

---

1 2 3 4 5 6 7 8

Pour chaque entrée, faire si entrée est chiffre alors empilement sinon dépiler 2 derniers chiffres calculer l'opération avec l'entrée comme opérateur empiler le résultat fin si fin faire

---

Et ça marche aussi si on l'entre ainsi: "+ 3 * 2 1" (toujours en partant de la fin vers le début)

---

Oui en fait je cherche à faire une calculatrice polonaise, mais pas inversée, donc les opérandes se situent avant. Et je ne souhaite pas utiliser de piles non plus

Dans tous les cas, tu vas avoir besoin de quelque chose pour "remonter" dans ton arbre:

• Soit dans l'arbre lui-même (pointeur vers le nœud parent)
• Soit dans une pile explicite (genre une liste chaînée)
• Soit dans la pile système.

Citation:

---

Envoyé par Médinoc

Dans tous les cas, tu vas avoir besoin de quelque chose pour "remonter" dans ton arbre:

• Soit dans l'arbre lui-même (pointeur vers le nœud parent)
• Soit dans une pile explicite (genre une liste chaînée)
• Soit dans la pile système.

---

Oui j'avais pensé à utiliser un pointeur sur le père, mais je me demande s'il faut à chaque fois renvoyer le noeud qu'on vient de créer ou l'arbre lui même

Je dirais selon que le nœud soit une feuille ou non. Lors de l'ajout d'un nœud:

• renvoyer le nœud créé si ce n'est pas une feuille,
• renvoyer son père si c'en est une.

Citation:

---

Envoyé par Médinoc

Je dirais selon que le nœud soit une feuille ou non. Lors de l'ajout d'un nœud:

• renvoyer le nœud créé si ce n'est pas une feuille,
• renvoyer son père si c'en est une.

---

On aurait quelque que chose comme ça quand a est nul ?

Code:

---

1 2 3 4 5 6 7 8 9

if (a->fg==NULL) { a->fg->op=x; if (opbin(x)==1) //je teste si c'est un opérateur, donc un noeud return a->fg; else return a; }

---

Bonsoir,
mouais, enfin un moment donné quand on dit créer il faut aussi penser malloc ...

Code:

---

1 2 3 4 5 6 7 8

if (a->fg==NULL) //Bzzt! Si a est NULL, c'est un comportement indéfini! { a->fg->op=x; //Bzz! Comportement indéfini, tu utilises fg alors qu'il est NULL! if (opbin(x)==1) //je teste si c'est un opérateur, donc un noeud return a->fg; else return a; }

---

Citation:

---

Envoyé par KiitKaate

On aurait quelque que chose comme ça quand a est nul ?

Code:

---

1 2 3 4 5 6 7 8

if (a->fg==NULL) { a->fg->op=x; if (opbin(x)==1) //je teste si c'est un opérateur, donc un noeud return a->fg; else return a; }

---

---

Mouais. Si a->fg est à null alors a->fg->op=x. Je vois mal comment aller remplir a->fg->op puisque a->fg est à null !!!

Ensuite si opbin(x)==1 alors return a->fg (on a toujours a->fg qui est à null non ?)
Et enfin, (rappel: tout ça se passe dans le cas quand a est nul) ben en final on retourne a. Bref on retourne que du null quoi...

Citation:

---

Envoyé par KiitKaate

Oui j'avais pensé à utiliser un pointeur sur le père,

---

C'est obligatoire si tu veux pouvoir remonter d'un noeud...

Citation:

---

Envoyé par KiitKaate

mais je me demande s'il faut à chaque fois renvoyer le noeud qu'on vient de créer ou l'arbre lui même

---

A quoi cela sert-il de renvoyer l'arbre (info déjà connue) alors qu'on ne connait pas le noeud qui a été créé ???

j'ai pensé à quelque chose comme ça, mais je n'arrive à voir comment transmettre le parent d'un noeud :

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

arbre enracnb(arbre a,char *x) {   if (a==NULL) { a=(arbre)malloc(sizeof(noeud)); a->op=x; a->fg=NULL; a->fd=NULL; return a; }   while(a!=NULL) { if(a->fg==NULL) { a->pere=a; a=a->fg; enrac(a,x); }   else if (a->fg!=NULL && a->fd==NULL) { a->pere=a; a=a->fd; enrac(a,x); }   else if (a->fg!=NULL && a->fd!=NULL) { if((opbin(a->fg->op)==1) && (opbin(a->fd->op)==1)) // Dans le cas ou c'est une feuille, je veux remonter a=a->pere; //Je sais que c'est faux mais je ne sais pas où le placer } }   }

---

Commence par faire des fonctions, définir ce que tu parses, ce que tu reçois (un token quiest soit un opérateur soit un nombre), …

Ensuite l'algo est tout simple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

créer_AST( ref chaine ) : AST début token = parser( chaine ) si token est opérateur alors fg = créer_AST( chaine ) fd = créer_AST( chaine ) renvoyer nouveau_noeud( tokem.opérateur, fg, fd ) sinon si token est nombre alors renvoyer nouvelle_feuille( token.nombre ) sinon gérer l'erreur fin si fin.

---

où ref signifie passage par référence, si la chaîne est modifiée dans la fonction alors les modifications seront visibles de l'extérieur = utilisation d'un pointeur
parser est une fonction qui modifie chaine et renvoie un token qui est une structure du genre

Code:

---

1 2 3 4 5 6

enum token_type { TOKEN_OP, TOKEN_NUM, TOKEN_ERR }; struct token { enum token_type_t type; int num; char op; };

---

nouveau_noeud et nouvelle feuille sont les primitives qui renvoie un AST (abre syntaxique abstrait = Abstract Syntaxic Tree). Il y aura plusieurs primitives à écrire, et un conseil : en C ne cache pas un pointeur dans un typedef. Pas la peine de caster les malloc non plus.

Ça ne sert à rien d'essayer de faire tomber un truc en marche si tu n'as pas l'algo d'abord.
Remarque, tu disais ne pas vouloir utiliser de pile mais implicitement tu utilise la pile d'exécution.

Merci beaucoup !
Oui c'est vrai avec l'algo c'est plus simple mais je n'arrivais pas à passer du dessin à un algo