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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
| #include <stdlib.h>
# include <stdio.h>
/*
On définit un type pour les éléments et une fonction de comparaison
entre éléments
*/
typedef double element_t;
int comparer(element_t a){
if (a < 4) return 1;
if (a > 4) return -1;
return 0;
}
void affiche_element(element_t a) {
printf("%g ", a);
}
/*
On définit le type des arbres binaires, qui est utilisé ici pour
les arbres binaires de recherche (voir cours).
L'arbre vide est représenté par NULL (l'adresse mémoire 0).
*/
typedef struct noeud_s {
element_t e;
struct noeud_s * gauche;
struct noeud_s * droite;
struct noeud_s * parent;
} * ab_t;
/* nouveau_noeud(a), crée (allocation mémoire) et renvoie un arbre à
un seul noeud contenant l'élément a. */
ab_t nouveau_noeud(element_t a){
ab_t x;
x = malloc(sizeof(ab_t*));
if (!x) {
perror("Echec malloc");
}
x->parent = NULL;
x->gauche = NULL;
x->droite = NULL;
x->e = a;
return x;
}
/* inserer(&x, a) insere un élément a dans un arbre binaire de
recherche x. S'il existe déjà un élément b égal à a dans l'arbre
aucun noeud n'est créé (pas de répétition). La fonction inserer()
ne renvoie rien, l'arbre x est passé par adresse (px = adresse de
l'arbre) pour être directement modifié (argument-résultat). */
void inserer(ab_t *px, element_t a){
if (!(*px)) {
*px = nouveau_noeud(a);
}
else {
ab_t y, parent;
int cote;
y = *px;
/* Recherche de la place de a (parent et côté où le mettre) */
while (y) {
parent = y;
cote = comparer(a);
switch(cote){
case 1: /* côté gauche */
y = y->gauche;
break;
case -1: /* côté droit */
y = y->droite;
break;
case 0: /* on a déjà cet élément, pas d'insertion */
return;
}
}
/* parent sera le parent du nouveau noeud, la valeur de cote dit
de quel côté l'attacher à son parent. */
y = nouveau_noeud(a);
y->parent = parent;
if (1 == cote) {
parent->gauche = y;
}
else {
parent->droite = y;
}
}
}
/* vider(&x) : libère l'espace mémoire utilisé par l'arbre x, et met x
à NULL (arbre vide) */
void vider(ab_t *px){
ab_t x;
x = *px;
if (x) {
vider(&(x->gauche));
vider(&(x->droite));
free(x);
*px = NULL;
}
}
/* fonction auxilliaire pour l'affichage d'une ligne de traits
verticaux représentant la descendance à gauche. */
void afficher_arbre_aux1(ab_t x){
if (x->parent) {
afficher_arbre_aux1(x->parent);
if (x == (x->parent)->droite) {
if ((x->parent)->gauche) {
printf(" | "); /* 8 caractères */
}
else {
printf(" "); /* 8 caractères */
}
}
}
}
/* afficher_arbre(x) réalise l'affichage de x sur la sortie standard
comme décrit plus haut. */
void afficher_arbre(ab_t x){
if (x) { /* Si l'arbre n'est pas vide, on réalise l'affichage par
appels récursifs sur les sous-arbres non vides. */
affiche_element(x->e);
if (x->droite) { /* noeuds de droite sur la même ligne */
printf("-----");
afficher_arbre(x->droite);
}
else { /* plus rien à droite : fin de ligne */
printf("\n");
}
if (x->gauche) {
afficher_arbre_aux1(x->gauche);
printf(" | \n"); /* 8 caractères */
afficher_arbre_aux1(x->gauche);
afficher_arbre(x->gauche);
}
}
else { /* Si l'arbre est vide on le signale */
printf("\n (arbre vide)\n\n");
}
}
int main() {
ab_t x = NULL;
//element_t i;
int i;
element_t tab[] = {0.7, 0.8, 6.7, 6, 7, 8.3, 9, 7.6};
for (i = 0; i < 8; i++) {
inserer(&x, tab[i]);
}
afficher_arbre(x);
system("PAUSE");
return EXIT_SUCCESS;
} |
création d'un arbre binaire
Répondre avec citation
c'est quoi la question 
le code ne me semble pas incorrect (en regardant d'1 œil et de travers)
(* ->) Dans un arbre binaire de recherche, chaque nœud à exactement 2 fils sinon c'est une feuille (binaire veut dire 2, c'est fou 
)
)
ma propriété (*) correspond à un "full/ strict binary tree" (notamment les AVL). Et pour associer un arbre à un tableau C, il faut que l'arbre soit complet ("complete binary tree") soit parfait ("perfect binary tree") 
Envoyé par Sve@r
Partager