Créer un arbre récursivement

**KiitKaate** · 02/05/2017, 12h30

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** · 02/05/2017, 15h46

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** · 02/05/2017, 16h17

À 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** · 02/05/2017, 17h37

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 ?

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'
Nom : arbr.png
Affichages : 303
Taille : 4,6 Ko

Nom : arbr.png
Affichages : 303
Taille : 4,6 Ko

**Sve@r** · 02/05/2017, 18h45

Envoyé par KiitKaate

Pour faire simple, si je tape '+ * 1 2 3'
Nom : arbr.png
Affichages : 303
Taille : 4,6 Ko

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** · 02/05/2017, 18h58

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 :

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** · 02/05/2017, 20h21

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.

**KiitKaate** · 02/05/2017, 20h37

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

**Médinoc** · 02/05/2017, 20h56

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.

**KiitKaate** · 02/05/2017, 21h20

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 :

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

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

**picodev** · 02/05/2017, 21h48

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

**Médinoc** · 02/05/2017, 21h49

Code que tu viens de poster :

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

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

**Sve@r** · 02/05/2017, 22h52

Envoyé par KiitKaate

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

Code :

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

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

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

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

**KiitKaate** · 03/05/2017, 11h24

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

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

**picodev** · 04/05/2017, 19h32

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 :

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

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 :

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

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.

**KiitKaate** · 05/05/2017, 16h37

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

Créer un arbre récursivement

C

Discussions similaires

Partager

Partager