Discussion :

[lynaranya]

bonsoir;
je veux utiliser le principe de création d'arbre binaire pour créer un arbre binaire de recherche,
le principe c'est que j'ai une valeur seuil=4, et un tableau contenant des valeurs de type réel, je veux créer l'arbre en comparant chaque valeur du tableau avec la valeur du seuil, si la valeur du tableau est inférieure au seuil, alors on ajoute l'indice tab[1] coté gauche sinon on l'ajoute coté droit, et ainsi de suite; sachant que la racine doit contenir l'indice tab[0].

voici un exemple d'arbre:


exemple de code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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