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
| t_arbre* reserver(t_arbre * arbre, float currenttime, float arrivee) {
/*TESTS*/
...
arbre=inserer_resa(arbre,arrivee); //allocation et insertion de la nouvelle réservation
printf("horaire valide :)!\n");
}
else {
printf("horaire invalide!\n");
}
}
else {
printf("horaire invalide!\n");
}
return arbre;
}
t_arbre *inserer_resa(t_arbre *arbre, float arrivee){ //inserer la réservation dans l'arbre
if(arbre==NULL)
return creer_noeud(arrivee); //si l'arbre est nul il suffit d'allouer et remplir le noeud
else{
if(arbre->aterrissage > arrivee) {
/*si la valeur à ajouter est plus grande que le noeud courant, on fait une récursion sur le fils gauche, sinon, sur le fils droit*/
arbre->g = inserer_resa(arbre->g, arrivee);
return arbre;
}
else {
arbre->d = inserer_resa(arbre->d, arrivee);
return arbre;
} //le cas "égal" ne pose pas de problème puisqu'il ne peut pas se produire
}
return arbre;
}
/////////////////
void suppress(t_arbre *arbre, float arrivee) {
t_arbre *courant=arbre;
t_arbre *pere=NULL;
while ((courant!=NULL) && (arbre->aterrissage!= arrivee)){
pere=courant; //on cherche toujours à avoir l'identité du père du noeud courant
if (arrivee<arbre->aterrissage) //si arrivee est plus petit, on cherche la valeur à supprimer dans le fils gauche
courant=courant->g;
else //si arrivee>arbre->aterrissage, on cherche dans le sous arbre droit
courant=courant->d;
} //on a donc normalement courant sur le noeud à supprimer
if (courant==NULL){ //cependant peut etre que l'arrivee saisie ne correspondait à aucune réservation
printf("erreur : l'heure saisie ne correspond à aucune réservation courante!\n");
return;
}
if ((courant->d==NULL) && (courant->g==NULL)){ //si le noeud considéré est une feuille
free(courant);
return;
}
if ((courant->d==NULL)&&(courant->g!=NULL)) { //s'il n'y a qu'un seul fils : le fils gauche
if (pere->aterrissage>courant->aterrissage) //si courant est le fils droit
pere->d=courant->g;
else //si c'est le fils gauche
pere->g=courant->g;
free(courant);
return;
}
if ((courant->g==NULL) && (courant->d!=NULL)) {
if (pere->aterrissage>courant->aterrissage)
pere->d=courant->d;
else
pere->g=courant->d;
free(courant);
return;
}
if ((courant->g!=NULL) && (courant->d!=NULL)){ //si le noeud à supprimer a 2 fils
float arr_pred=min(courant->g);
/*on stocke la valeur du plus petit prédécesseur du noeud considéré (à noter qu'on aurait aussi pu utiliser le "plus proche successeur" (le max du sous arbre droit)*/
suppress(arbre,arr_pred);
courant->aterrissage=arr_pred;
}
}
int main() {
t_arbre *arbre=malloc(sizeof(t_arbre));
...
if (saisie==1){
scanf(&arrivee);
arbre=reserver(arbre,currenttime,arrivee);
}
if (saisie==2)
suppress(arbre,arrivee);
...
} |
