Discussion :

[KiitKaate]

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 :

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
 
//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

[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 ?

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

[Médinoc]

À 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!

[KiitKaate]

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 ?

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'

[Sve@r]

Pour faire simple, si je tape '+ * 1 2 3'

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 :

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

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)

[KiitKaate]

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 :

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

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

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