abr.c
1.94 KB
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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "abr.h"
bool recherche_abr_iter (int x, struct abr* A0)
{ struct abr* A; // curseur pour se déplacer dans A0
bool trouve;
A = A0;
trouve = false;
while (A != NIL && !trouve)
{
if (A->valeur == x)
trouve = true;
else if (A->valeur < x)
A = A->droit;
else
A = A->gauche;
}
return trouve;
}
bool recherche_abr_rec (int x, struct abr* A)
{
if (A == NIL)
return false;
else if (A->valeur == x)
return true;
else if (A->valeur < x)
return recherche_abr_rec (x, A->droit);
else
return recherche_abr_rec (x, A->gauche);
}
static struct abr* new_feuille (int x)
{ struct abr* F;
F = (struct abr*)malloc (sizeof (struct abr));
F->gauche = NIL;
F->valeur = x;
F->droit = NIL;
return F;
}
struct abr* ajout_abr_iter (int x, struct abr* A0)
{
if (A0 == NIL)
return new_feuille (x);
else
{ struct abr* prec = NIL;
struct abr* cour = A0;
while (cour != NIL)
{ prec = cour;
if (cour->valeur < x)
cour = cour->droit;
else
cour = cour->gauche;
}
if (prec->valeur < x)
prec->droit = new_feuille (x);
else
prec->gauche = new_feuille (x);
return A0;
}
}
struct abr* ajout_abr_rec (int x, struct abr* A)
{
if (A == NIL)
return new_feuille (x);
else if (x < A->valeur)
A->gauche = ajout_abr_rec (x, A->gauche);
else
A->droit = ajout_abr_rec (x, A->droit);
return A;
}
void clear_abr (struct abr* A)
{
if (A != NIL)
{ clear_abr (A->gauche);
clear_abr (A->droit);
free (A);
}
}
void imprime_abr (struct abr* A)
{
if (A != NIL)
{ imprime_abr (A->gauche);
printf ("%d\n", A->valeur);
imprime_abr (A->droit);
}
}