Discussion :

[rune93]

Bonjour,
J'ai essayé d'implémenter un parcours en largeur sur un arbre binaire de recherche :
Avec une file (liste simplement chaînée) et un arbre.
Cependant mon programme boucle infiniment , j'ai recherché de fond en comble sans rien trouver.

Voici le code :
parcours_en_largeur.c

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>
#include "parcours_en_largeur.h"
 
void insert_char(ABR *pa, char c) {
	if (pa == NULL) {
		exit(1);
	}
	if ((*pa) == NULL) { /* Arbre vide */
		Noeud *pn = (Noeud*)malloc(sizeof(Noeud));
		if (pn == NULL) {
			fprintf(stderr, "Erreur d'allocation m�moire\n");
			exit(1);
		}
		(*pn).val = c;
		(*pa) = pn;
	} else {
		if (c <= (**pa).val) {
			insert_char(&(**pa).gauche, c);
		} else {
			insert_char(&(**pa).droite, c);
		}
	}
 
}
 
int est_Feuille(ABR a) {
	if (a==NULL) return 0;
	if ((a->gauche == NULL)&&(a->droite == NULL)) return 1;
	return 0;
}
 
void affichage(ABR a) {
	if(a==NULL) return;
	printf("(");
	affichage(a->gauche);
	printf("%d ", a->val);
	affichage(a->droite);
	printf(")");
}
 
/*
 * Parcours en largeur :
 */
 
void put(Noeud *n, File *Fifo) {
	Liste f = (Liste) malloc(sizeof(Cellule));
	if (f == NULL) {
		printf("Erreur d'allocation m�moire\n");
		exit(1);
	}
	f->noeu = n;
	f->suivant = NULL;
 
	if (Fifo->input == NULL) {
		Fifo->input = f;
		Fifo->output = f;
	} else {
		Fifo->output->suivant = f;
		Fifo->output = f;
	}
}
 
Noeud* take(File *FiFo) {
	if ((FiFo->output == NULL)) {
		printf("Erreur! Plus rien à retirer\n");
		exit(1);
	}
	Noeud *noeu = FiFo->input->noeu;
	Liste tmp = FiFo->input;
 
	if (FiFo->input == NULL) {
		FiFo->output = NULL;
	} else {
		FiFo->input = FiFo->input->suivant;
	}
	free(tmp);
	return noeu;
}
 
void parcours_largeur(ABR a) {
	if (a == NULL) return;
	File f = {NULL, NULL};
	put(a, &f);
 
	while(f.input != NULL) {
		ABR tmp = take(&f);
		printf("%d ", tmp->val);
		if (!est_Feuille(tmp)) {
			if (a->gauche != NULL) {
				put(a->gauche, &f);
			}
			if (a->droite != NULL) {
				put(a->droite, &f);
			}	
		}
	}
}
 
/*
* Test du parcours en largeur :
*/
int main(void) {
	int i;
	ABR a = NULL;
 
	for (i=0; i<15; i++) {
		 insert_char(&a, i);
	}
 
	affichage(a);
	printf("\nParcours en largeur :\n");
 
	/* parcours_largeur(a); */
	return 0;
}

parcours_en_largeur.h

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
#ifndef PARCOURS_L_
#define PARCOURS_L_
 
typedef struct _noeud {
	char val;
	struct _noeud *gauche;
	struct _noeud *droite;
}Noeud, *ABR;
 
typedef struct cel {
	struct _noeud *noeu;
	struct cel *suivant;
}Cellule, *Liste;
 
typedef struct file {
	struct cel *input;
	struct cel *output;
}File;
 
#endif /* PARCOURS_L_*/

Ca m'affiche :

(0 (1 (2 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 (14 )))))))))))))))
Parcours en largeur :
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 à l'infini ...

Je ne sais pas pourquoi, la file a pourtant l'air de bien être implémentée,
Merci,

[Trap D]

Tu as un bug dans la création de l'arbre :

Code :

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

Noeud *pn = malloc(sizeof(Noeud));

Tu crèes bien le noeud, mais tu n'initialises pas gauche ni droite à NULL, ce qui fait que ça plante sous Visual C.
D'autre part, en C, il n'est pas utile et même c'est parfois nuisible, de caster le retour de malloc.

pour le reste, observe bien ce bout de code :

Code :

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

1
2
3
4
5
6
7
8
		if (!est_Feuille(tmp)) {
			if (a->gauche != NULL) {
				put(a->gauche, &f);
			}
			if (a->droite != NULL) {
				put(a->droite, &f);
			}	
		}