Problème suppression et MAJ dans un arbre

**scary** · 20/06/2009, 20h31

Bonsoir,

J'essaie de faire un code qui supprime une valeur dans un ABR et le met à jour afin qu'après la suppression il respecte la spécification que je veux lui donner. L'arbre est constitué comme suit:
- chaque nœuds contient une lettre et le nombre qu'il a de fils gauche
- les lettre sont ordonnés dans l'arbre suivant leur ordre dans l'alphabet

Voici donc le code que j'ai fais:

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct noeud *arbre;
 
typedef struct noeud
{
      char lettre;
      int ng;
      struct noeud *fg;
      struct noeud *fd;
} Noeud;
 
int EstVide (arbre A);
void InsererDansArbre (arbre *A, int ng, char lettre);
arbre Supprimer (arbre A, char lettre);
arbre SupprimerNoeud (arbre A);
arbre Predecesseur (arbre A);
void Affiche_pref (arbre A);
 
int main (void)
{
    arbre A = NULL;
    char lettre;
 
    InsererDansArbre (&A, 8, 'p');
    InsererDansArbre (&A, 3, 'g');
    InsererDansArbre (&A, 1, 'd');
    InsererDansArbre (&A, 0, 'a');
    InsererDansArbre (&A, 0, 'f');
    InsererDansArbre (&A, 0, 'h');
    InsererDansArbre (&A, 0, 'l');
    InsererDansArbre (&A, 3, 'n');
    InsererDansArbre (&A, 1, 'j');
    InsererDansArbre (&A, 0, 'r');
    InsererDansArbre (&A, 1, 'v');
    InsererDansArbre (&A, 0, 'u');
    InsererDansArbre (&A, 0, 'x');
    Affiche_pref (A);
    printf ("Quelle lettre voulez-vous supprimer ?: ");
    scanf ("%c", &lettre);
    Supprimer (A, lettre);
    Affiche_pref (A);
 
    return 0;
}
 
void Affiche_pref (arbre A)
{
      if (!EstVide (A))
      {
          printf ("lettre: %c et nb fg: ", A->lettre);
          printf ("%d\n", A->ng);
          Affiche_pref (A->fg);
          Affiche_pref (A->fd);
      }
 
      return ;
}
 
int EstVide (arbre A)
{
      if (A == NULL)
      {
            return 1;
      }
 
      return 0;
}
 
void InsererDansArbre (arbre *A, int ng, char lettre)
{
	if (EstVide (*A))
	{
		*A = malloc (sizeof (Noeud));
        if (A == NULL)
        {
            fprintf (stderr, "Impossible d'allouer le noeud");
            exit (0);
        }
        (*A)->lettre = lettre;
        (*A)->ng = ng;
        (*A)->fg = NULL;
        (*A)->fd = NULL;
	}
	else
	{
		if (lettre < (*A)->lettre)
		{
			InsererDansArbre (&(*A)->fg, ng, lettre);
		}
		else
		{
			InsererDansArbre (&(*A)->fd, ng, lettre);
		}
	}
 
	return ;
}
 
arbre Supprimer (arbre A, char lettre)
{
	if (EstVide (A))
	{
		return NULL;
	}
	else if (A->lettre == lettre)
	{
	    return SupprimerNoeud (A);
	}
	else if (A->lettre > lettre)
	{
	    (A->ng)--;
 
		return Supprimer (A->fg, lettre);
	}
	else
	{
		return Supprimer (A->fd, lettre);
	}
}
 
arbre SupprimerNoeud (arbre A)
{
    if ((A->fg == NULL) && (A->fd == NULL))
    {
        return NULL;
    }
    else if (A->fg == NULL)
    {
        return A->fd;
    }
    else if (A->fd == NULL)
    {
        return A->fg;
    }
    else
    {
        arbre f = Predecesseur (A->fg);
        A->lettre = f->lettre;
        A->fg = Supprimer (A->fg, f->lettre);
    }
 
    return A;
}
 
arbre Predecesseur (arbre A)
{
    if (A->fd == NULL)
    {
        return A;
    }
 
    return Predecesseur (A->fd);
}

Le problème est que la mise à jour du nombre de fils gauche ne ce fait pas toujours et aussi parfois le noeud n'est pas supprimé. Et je ne comprend vraiment pas pourquoi...

Merci d'avance pour toute indication

**souviron34** · 21/06/2009, 14h52

plusieurs problèmes, à propos des pointeurs...

Tout d'abord : de manière générale, dès que tu as une structure, passe l'adresse , même si tu ne modifies rien... C fonctionne par défaut par copie, donc si tu passes la structure, ça s'occupe uniquement de la copie. Et ça peut être gros sur la pile..

Donc au lieu de :

Code :

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

1
2
3
4
5
6
7
void Affiche_pref (arbre A)
{
      if (!EstVide (A))
....
 
int EstVide (arbre A)
{

Faire :

Code :

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

1
2
3
4
5
6
void Affiche_pref (arbre *A)
{
      if (!EstVide (A))
...
int EstVide (arbre *A)
{

Ensuite :

Si on modifie un pointeur, on doit passer l'adresse de ce pointeur pour pouvoir le récupérer dans la routine appelante..

Donc

Code :

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

1
2
3
4
5
void InsererDansArbre (arbre *A, int ng, char lettre)
{
	if (EstVide (*A))
	{
		*A = malloc

Ne renverra pas l'adresse de l'arbre..

Il faudrait mettre :

Code :

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

1
2
3
4
5
void InsererDansArbre (arbre **A, int ng, char lettre)
{
	if (EstVide (**A))
	{
		*A = malloc

(ceci en gardant ton interface de fonction EstVide)

Dans ce cas, tu déclarerais dans ton main :

Code :

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

    arbre *A = NULL;

en gardant le même appel :

Code :

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

   InsererDansArbre (&A, 8, 'p');

D'autre part, là tu écrases ton arbre à chaque appel, car tu lui fais un alloc.. Il faudrait utiliser realloc, pour pouvoir continuer à stocker ...

**scary** · 21/06/2009, 15h32

Bon j'ai donc fait un nouveau code et dans ce nouveau code j'y ai apporté les quelques modif que tu m'as conseillé. Seulement j'ai maintenant un petit soucis dans "insererArbre ()", le compilo me met ce warning:

Code :

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

1
2
abr.c:238: warning: passing arg 1 of `InsererDansArbre' from incompatible pointer type
abr.c:242: warning: passing arg 1 of `InsererDansArbre' from incompatible pointer type

Voici le nouveau 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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#include <stdio.h>
#include <stdlib.h>
 
typedef struct noeud *arbre;
 
typedef struct noeud
{
      char lettre;
      int ng;
      struct noeud *fg;
      struct noeud *fd;
} Noeud;
 
int EstVide (arbre *A);
void InsererDansArbre (arbre **A, int ng, char lettre);
int Suppression (arbre A, char lettre);
void Affiche_pref (arbre *A);
arbre Sup (arbre current);
 
int main (void)
{
    arbre *A = NULL;
    char lettre;
    int test = 0;
 
    InsererDansArbre (&A, 8, 'p');
    InsererDansArbre (&A, 3, 'g');
    InsererDansArbre (&A, 1, 'd');
    InsererDansArbre (&A, 0, 'a');
    InsererDansArbre (&A, 0, 'f');
    InsererDansArbre (&A, 0, 'h');
    InsererDansArbre (&A, 0, 'l');
    InsererDansArbre (&A, 3, 'n');
    InsererDansArbre (&A, 1, 'j');
    InsererDansArbre (&A, 0, 'r');
    InsererDansArbre (&A, 1, 'v');
    InsererDansArbre (&A, 0, 'u');
    InsererDansArbre (&A, 0, 'x');
    if (!EstVide (A))
    {
        Affiche_pref (A);
        printf ("Quelle lettre voulez-vous supprimer ?: ");
        scanf ("%c", &lettre);
        test = Suppression (*A, lettre);
        switch (test)
        {
            case 0:
            {
                printf ("Le caractere %c n'est pas present dans l'arbre", lettre);
                break;
            }
            case 1:
            {
                printf ("L'arbre ne contenait qu'une racine et est maintenant vide");
                break;
            }
            default:
            {
                Affiche_pref (A);
                break;
            }
        }
    }
    else
    {
        printf ("L'arbre est vide");
    }
 
    return 0;
}
 
int Suppression (arbre A, char lettre)
{
    int res = 0;
 
    if (EstVide (&A))
    {
        res = 0;
 
        return res;
    }
    if (((A->fg == NULL) && (A->fd == NULL)) && (A->lettre == lettre))
    {
        A = NULL;
        res = 1;
 
        return res;
    }
    if (A->fd)
    {
        if (A->fd->lettre == lettre)
        {
            A->fd = Sup (A->fd);
            res = 2;
 
            return res;
        }
    }
    if (A->fg)
    {
        if (A->fg->lettre == lettre)
        {
            (A->ng)--;
            A->fg = Sup (A->fg);
            res = 2;
 
            return res;
        }
    }
    if (A->lettre == lettre)
    {
        A->lettre = A->fg->lettre;
        (A->ng)--;
        A->fg = Sup (A->fg);
        res = 2;
 
        return res;
    }
    if (lettre < A->lettre)
    {
        (A->ng)--;
 
        return Suppression (A->fg, lettre);
    }
    if (lettre > A->lettre)
    {
        return Suppression (A->fd, lettre);
    }
 
    return 0;
}
 
arbre Sup (arbre A)
{
    arbre n;
    arbre p;
 
    /* Si un des sous arbre est vide, on remplace le noeud */
    /* par le sous arbre existant. */
    if (A->fg == NULL)
    {
        n = A->fd;
    }
    else
    {
        if (A->fd == NULL)
        {
            n = A->fg;
        }
        else
        {
            /* Recherche du plus petit element du sous arbre droit */
            n = A->fd;
            p = A;
            while (n->fg)
            {
                p = n;
                n = n->fg;
            }
            n->fg = A->fg;
            if (p != A)
            {
                p->fg = n->fd;
                n->fd = A->fd;
            }
        }
    }
    free (A);
 
    return n;
}
 
/*void Affiche_pref (arbre A)
{
      if (!EstVide (A))
      {
          printf ("lettre: %c et nb fg: ", A->lettre);
          printf ("%d\n", A->ng);
          Affiche_pref (A->fg);
          Affiche_pref (A->fd);
      }
 
      return ;
}*/
 
void Affiche_pref (arbre *A)
{
    if (!EstVide (&(*A)))
    {
        printf ("lettre: %c et nb fg: ", (*A)->lettre);
        printf ("%d\n", (*A)->ng);
        Affiche_pref (&(*A)->fg);
        Affiche_pref (&(*A)->fd);
    }
 
    return ;
}
 
/*int EstVide (arbre A)
{
      if (A == NULL)
      {
            return 1;
      }
 
      return 0;
}*/
 
int EstVide (arbre *A)
{
    if (*A == NULL)
    {
        return 1;
    }
 
    return 0;
}
 
void InsererDansArbre (arbre **A, int ng, char lettre)
{
	if (EstVide (*A))
	{
		*A = malloc (sizeof (Noeud));
        if (A == NULL)
        {
            fprintf (stderr, "Impossible d'allouer le noeud");
            exit (0);
        }
        (**A)->lettre = lettre;
        (**A)->ng = ng;
        (**A)->fg = NULL;
        (**A)->fd = NULL;
	}
	else
	{
		if (lettre < (**A)->lettre)
		{
			InsererDansArbre (&(**A)->fg, ng, lettre);
		}
		else
		{
			InsererDansArbre (&(**A)->fd, ng, lettre);
		}
	}
 
	return ;
}

Et aussi je ne vois pas comment utiliser realloc pour cette fonction...

Par contre j'ai toujours mon problème de mise à jour du nombre du fils gauche

Merci de ton aide

**souviron34** · 21/06/2009, 16h25

tu ne te sers pas correctement de **....

On ne rajoute pas juste une étoile pour faire plaisir.. Il faut en comprendre la signification..

Un pointeur est désigné par une *.

Si tu fais une fonction qui modifie un entier, tu mettras :

Code :

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

void Fonction ( int *Val)

et dans la fonction, tu mettras une valeur dans l'entier par : *Val = X.

Si tu fais une fonction qui modifie un pointeur, tu mettras :

Code :

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

void Fonction (Arb **MyArb )

et dans la fonction, quand tu lui assigneras une valeur, tu lui mettras *MyArb.

Donc à, dans ton cas, au lieu d'avoir :

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
 
void InsererDansArbre (arbre **A, int ng, char lettre)
{
	if (EstVide (*A))
	{
		*A = malloc (sizeof (Noeud));
        if (A == NULL)
        {
            fprintf (stderr, "Impossible d'allouer le noeud");
            exit (0);
        }
        (**A)->lettre = lettre;
        (**A)->ng = ng;
        (**A)->fg = NULL;
        (**A)->fd = NULL;
	}
	else
	{
		if (lettre < (**A)->lettre)
		{
			InsererDansArbre (&(**A)->fg, ng, lettre);
		}
		else
		{
			InsererDansArbre (&(**A)->fd, ng, lettre);
		}
	}
 
	return ;
}

Il faudrait avoir :

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
 
void InsererDansArbre (arbre **A, int ng, char lettre)
{
	if (EstVide (*A))
	{
		*A = malloc (sizeof (Noeud));
        if (*A == NULL)
        {
            fprintf (stderr, "Impossible d'allouer le noeud");
            exit (0);
        }
        (*A)->lettre = lettre;
        (*A)->ng = ng;
        (*A)->fg = NULL;
        (*A)->fd = NULL;
	}
	else
	{
		if (lettre < (*A)->lettre)
		{
			InsererDansArbre (&((*A)->fg), ng, lettre);
		}
		else
		{
			InsererDansArbre (&((*A)->fd), ng, lettre);
		}
	}
 
	return ;
}

**scary** · 21/06/2009, 22h08

Ok mais le problème est encore pire puisque:

Code :

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

1
2
3
4
5
6
7
8
abr.c: In function `InsererDansArbre':
abr.c:229: error: request for member `lettre' in something not a structure or union
abr.c:230: error: request for member `ng' in something not a structure or union
abr.c:231: error: request for member `fg' in something not a structure or union
abr.c:232: error: request for member `fd' in something not a structure or union
abr.c:236: error: request for member `lettre' in something not a structure or union
abr.c:238: error: request for member `fg' in something not a structure or union
abr.c:242: error: request for member `fd' in something not a structure or union

**jeroman** · 21/06/2009, 23h17

Je pense qu'il faut virer une étoile dans le 1er argument de :

Code :

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

void InsererDansArbre (arbre **A, int ng, char lettre)

car arbre correspond déjà à un pointeur sur noeud :

Code :

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

typedef struct noeud *arbre;

**scary** · 21/06/2009, 23h29

Haa je me disais bien aussi que dès le début c'était bon

parce que je ne voyais pas l'intérêt de manipuler un:

Code :

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

noeud ***A = arbre **A

puisque:

Code :

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

arbre *A = noeud **A

Donc mis à part cette petite chose quelqu'un aurait une idée pour mon véritable soucis car à chaque fois je ne met à jour que la racine de l'arbre et pas les autres avec le nombre de fils gauche

**souviron34** · 22/06/2009, 09h20

Envoyé par scary

quelqu'un aurait une idée pour mon véritable soucis car à chaque fois je ne met à jour que la racine de l'arbre et pas les autres avec le nombre de fils gauche

pour ça, je t'ai djà répondu :

Envoyé par souviron34

D'autre part, là tu écrases ton arbre à chaque appel, car tu lui fais un alloc.. Il faudrait utiliser realloc, pour pouvoir continuer à stocker ...

ce qui revient à dire que si tu regardes ton mai, à chaque fois tu te sers de A, que tu écrases à chaque malloc, cela devient donc le dernier à chaque fois..

ton véritable souci est un souci de conception....

Qu'est-ce qu'un arbre ?

Un arbre est un ensemble de noeuds identiques, ayant chacun 0 enfants, 1 à gauche, 1 à droite, ou les 2.

Donc, une conception claire amène à :

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
 
typedef struct pnoeud
{
      char lettre;
      struct pnoeud *fg;
      struct pnoeud *fd;
} Noeud;
 
Noeud *InsererDansArbre (Noeud *Pere, char lettre);
 
int main (void)
{
    Noeud *A = NULL, *p=NULL;
    char lettre;
    int test = 0;
 
    A = InsererDansArbre (NULL, 'a');
    p = InsererDansArbre (A, 'g');
    p = InsererDansArbre (A, 'd');
    p = InsererDansArbre (A, 'u');
    p = InsererDansArbre (A, 'b');
  ....
 
    return 0;
}
 
 
Noeud *InsererDansArbre (Noeud *Pere, char lettre)
{
      Noeud *A=NULL, *p=NULL, *p0=NULL ;
 
        A = malloc (sizeof (Noeud));
        if (A != NULL)
        {
            A->lettre = lettre;
            A->fg = NULL;
            A->fd = NULL;
        }
      else
        {
            fprintf (stderr, "Impossible d'allouer le noeud");
            exit (0);
        }
 
      if ( Pere != NULL )
         {
             p0 = Pere ;
             if ( lettre > Pere->lettre )
               {
                  while ( (p = p0->fd) != NULL )
                      p0 = p0->fd ;
 
                  p0->fd = A ;
               }
             else
               {
                  while ( (p = p0->fg) != NULL )
                      p0 = p0->fg ;
 
                  p0->fg = A ;
               }
        }
 
   return A ;
}

**Climoo** · 22/06/2009, 09h37

Ton erreur est avant tout une erreur d'algorithme...
En particulier, ta fonction Predecesseur, n'est pas correcte.
Sur un arbre (je prends des nombre pour simplifier)
5
/ \
1 8

Le predecesseur de 8 est 5, et ta fonction, telle qu'elle est actuellement, renverra "NULL". Elle devrait renvoyer NULL uniquement pour 1.
Pour implémenter correctement cette fonction, tu auras parfois besoin de remonter dans l'arbre (je te laisse chercher dans quel cas). Il te faut donc dans ta structure, un pointeur vers le pere du noeud.

Ensuite, il ne faut pas oublier, dans ton main, de remplacer :

Code :

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

1
2
 
Supprimer (A, lettre);

par

Code :

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

1
2
 
A = Supprimer (A, lettre);

Car la racine de ton arbre peut éventuellement changer, vu la tête de tes fonctions.

Et aussi, pour faire plus propre, tu pourrais ajouter des free(A) sur tes noeuds, car sinon, la mémoire utilisé par un noeud est perdue à tout jamais...

Si tu ne veux pas ajouter de champ "pere" dans ton arbre, c'est possible de faire sans. Mais l'algorithme de suppression est un peu différent, il faut raccorder les branches de manières différentes.
En espérant que ces petites pistes t'aideront....

EDIT :
Je n'avais pas regardé ta fonction d'insertion...
Elle a un gros soucis aussi ! Pourquoi passer "ng" en paramètre? On dirait que là, tu as dessiné ton arbre à la main, puis que tu as regardé combien chaque noeud avait de noeud à sa gauche, et que tu as voulu passer ce nombre. Maintenant si je te demande de créer un arbre avec encore 10 lettres de plus, tu vas les redessiner, et voir quel valeur de "ng" il faut passer ? Non, ça ne va pas ... La valeur de ng doit etre incrémentée automatiquement dans les noeuds, quand tu pars sur la gauche. Sur le même principe que quand tu le décrémentes lors de la suppression.

**scary** · 22/06/2009, 10h40

Envoyé par souviron34

Qu'est-ce qu'un arbre ?

Un arbre est un ensemble de noeuds identiques, ayant chacun 0 enfants, 1 à gauche, 1 à droite, ou les 2.

Donc, une conception claire amène à :

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
 
typedef struct pnoeud
{
      char lettre;
      struct pnoeud *fg;
      struct pnoeud *fd;
} Noeud;
 
Noeud *InsererDansArbre (Noeud *Pere, char lettre);
 
int main (void)
{
    Noeud *A = NULL, *p=NULL;
    char lettre;
    int test = 0;
 
    A = InsererDansArbre (NULL, 'a');
    p = InsererDansArbre (A, 'g');
    p = InsererDansArbre (A, 'd');
    p = InsererDansArbre (A, 'u');
    p = InsererDansArbre (A, 'b');
  ....
 
    return 0;
}
 
 
Noeud *InsererDansArbre (Noeud *Pere, char lettre)
{
      Noeud *A=NULL, *p=NULL, *p0=NULL ;
 
        A = malloc (sizeof (Noeud));
        if (A != NULL)
        {
            A->lettre = lettre;
            A->fg = NULL;
            A->fd = NULL;
        }
      else
        {
            fprintf (stderr, "Impossible d'allouer le noeud");
            exit (0);
        }
 
      if ( Pere != NULL )
         {
             p0 = Pere ;
             if ( lettre > Pere->lettre )
               {
                  while ( (p = p0->fd) != NULL )
                      p0 = p0->fd ;
 
                  p0->fd = A ;
               }
             else
               {
                  while ( (p = p0->fg) != NULL )
                      p0 = p0->fg ;
 
                  p0->fg = A ;
               }
        }
 
   return A ;
}

Je ne comprend pas pourquoi tu veux absolument que je change ma fonction insérer car avant tu me dis qu'il faut passer un:

Code :

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

arbre **A

En utilisant realloc, et maintenant tu fais une fonction en passant un:

Code :

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

arbre A

Sans utiliser realloc, et ta fonction ne marche pas lorsque je veux supprimer pour les 3/4 des noeuds ça me dit que le noeud n'existe pas alors qu'avant pour supprimer un noeud je n'avais aucun problème.
Je suis vraiment désolé je sais que tu essais de m'aider

mais je ne comprend pas ta démarche

Sinon Climoo je n'utilise plus ma fonction prédecesseur j'ai décider de faire autrement (voir la dernière MAJ du code) et ça fonctionne bien à chaque que je supprime j'ai toujours un ABR bien formé.
Ensuite pour ma fonction insertion c'est vrai que je ne devrais pas passer le nombre en paramètre mais ce que je cherche à faire en fait c'est juste de supprimer mais c'était ce qui étais prévu une fois que la suppression marchait.
Sinon pour le raisonnement que j'utilise c'est:

Code :

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

1
2
3
4
5
6
7
SI lettre < A->lettre ALORS /*lettre est donc un fils gauche donc je décrémente et je refais récursivement avec le fils gauche*/
              A->ng--
              Suppression (A->fg)
          SINON
               /*c'est un fils droit donc je ne décrémente pas*/
               Suppression (A->fd)
          FIN SI

En très gros c'est comme ça que j'ai résonné, je te laisse pour plus de détails voir la fonction "suppression()" dans le code. Serais-ce faux ? et pourquoi si oui car je ne vois pas

**souviron34** · 22/06/2009, 13h06

Envoyé par scary

Je ne comprend pas pourquoi tu veux absolument que je change ma fonction insérer car avant tu me dis qu'il faut passer un:

Code :

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

arbre **A

En utilisant realloc, et maintenant ....

Parce que j'étais parti pour t'aider avec ta solution

qui me semble extrêmement compliquée (et du coup pour laquelle tu te compliques la vie avec des pointeurs de pointeurs), alors que ce que tu veux faire est nettement plus simple...

Envoyé par scary

Sans utiliser realloc, et ta fonction ne marche pas lorsque je veux supprimer pour les 3/4 des noeuds ça me dit que le noeud n'existe pas alors qu'avant pour supprimer un noeud je n'avais aucun problème.

Je n'ai pas dit que je résolvais ton problème : c'est à toi de le faire.

Je te donnais une piste...

**souviron34** · 22/06/2009, 13h07

Envoyé par scary

En très gros c'est comme ça que j'ai résonné

si tu résonnes comme ça, tu es une cloche

Si par contre tu raisonnes mieux, alors on se comprend

**scary** · 22/06/2009, 17h12

Envoyé par souviron34

Parce que j'étais parti pour t'aider avec ta solution

qui me semble extrêmement compliquée (et du coup pour laquelle tu te compliques la vie avec des pointeurs de pointeurs), alors que ce que tu veux faire est nettement plus simple...

Je suis bien d'accord mais j'ai préféré faire comme ça plutôt que d'une autre manière, du moment que l'insertion marche

Envoyé par souviron34

Je n'ai pas dit que je résolvais ton problème : c'est à toi de le faire.

Je te donnais une piste...

Je n'ai jamais dit non plus que tu devais résoudre mon problème

mais seulement je ne comprenais pas pourquoi tu essayais de modifier "insertion" alors que le problème vient de "suppression" c'est pour ça

Envoyé par souviron34

si tu résonnes comme ça, tu es une cloche

Si par contre tu raisonnes mieux, alors on se comprend

Je suis d'accord

et donc mon raisonnement pour la mise à jour est-il correct ou non ? (parce que il n'y a vraiment que cela qui ne marche pas

et c'est vraiment frustrant

)