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;

Problème suppression et MAJ dans un arbre

C

Vue hybride

Discussions similaires

Partager

Partager