Parcours en largeur sur un ABR

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:

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:

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 :

Citation:

(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,