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