Bonsoir,

Je dois faire une bibliothèque de manipulation d'arbres binaires de recherche. Tout se passe bien (test effectués) sauf au moment de la suppression d'une feuille. En effet la fonction free ne libère pas l'objet pointé retourné par la fonction de recherche dans l'arbre. Je suis vraiment coincé et j'apprécirai toute aide. De plus si vous avez d'autres idées pour cette fonction ou mêmes les autres, elles sont les bienvenues.

Le fichier d'en-tête abr.h :

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
#ifndef ABR_H
#define ABR_H
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef struct abr *abr;
 
abr creer_abr(int cle, void *objet);
 
bool abr_vide(abr a);
 
void inserer_abr(abr a, void *objet, int cle);
 
void *chercher_abr_obj(int cle, abr a);
 
bool supprimer_abr(int cle, abr a);
 
#endif /*ABR_H*/
Et le fichier abr.c sans la fonction suppression :
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
 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "abr.h"
 
struct abr
{
  void *objet;
  int cle;
  abr gauche;
  abr droit;
};
 
abr
creer_abr(int cle, void *objet)
{
  abr a = malloc(sizeof(struct abr));
  a->objet = objet;
  a->gauche = NULL;
  a->droit = NULL;
  a->cle = cle;
 
  return a;
}
 
bool
abr_vide(abr a)
{
  return (a == NULL);
}
 
static void
inserer_abr_aux(abr noeud, abr a)
{
  if(abr_vide(a))
    a = noeud;
  if(noeud->cle <= a->cle)
    {
      if(a->gauche == NULL)
	a->gauche = noeud;
      else
	inserer_abr_aux(noeud, a->gauche);
    }
  else
    {
      if(a->droit == NULL)
	a->droit = noeud;
      else
	inserer_abr_aux(noeud, a->droit);
    }
}
 
void
inserer_abr(abr a, void *objet, int cle)
{
  abr noeud = creer_abr(cle, objet);
  inserer_abr_aux(noeud, a);
}
 
static abr
chercher_abr(int cle, abr a)
{
  if(abr_vide(a))
    return NULL;
  if(a->cle == cle)
    return a;
  if(cle <= a->cle)
    {
      if(a->gauche != NULL)
	return chercher_abr(cle, a->gauche);
      else
	return NULL;
    }
  else
    {
      if(a->droit != NULL)
	return chercher_abr(cle, a->droit);
      else
	return NULL;
    }
}
 
void *chercher_abr_obj(int cle, abr a)
{
     abr tmp = chercher_abr(cle, a);
     if(tmp != NULL)
       return tmp->objet;
     return NULL;
}
 
static abr
max_abr(abr a)
{
  assert(!abr_vide(a));
  if(a->gauche == NULL && a->droit == NULL)
    return a;
  else if(a->droit == NULL)
    return a->gauche;
  else
    return max_abr(a->droit);
}
Et voici la dernière fonction qui pose problème (la ligne de l'erreur est suivie d'un commentaire)

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
bool
supprimer_abr(int cle, abr a)
{
  if(abr_vide(a))
    return false;
  abr tmp3 = chercher_abr(cle, a);
  assert(tmp3 != NULL);
  if(tmp3->gauche == NULL && tmp3->droit == NULL)
    {
      free(tmp3->objet); //ceci est bien libéré
      tmp3->objet = NULL;
      free(tmp3);    //LE PROBLEME EST ICI, LE NOEUD POINTÉ PAR tmp3 N'EST PAS LIBERE, assert
      tmp3 = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }  
  if(tmp3->gauche == NULL)
    {
      abr tmp = tmp3->droit;
      free(tmp3->objet);
      tmp3->objet = tmp->objet;
      tmp3->cle = tmp->cle;
      tmp3->gauche = tmp->gauche;
      tmp3->droit = tmp->droit;
      free(tmp);
      tmp = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }
  else if(tmp3->droit == NULL)
    {
      abr tmp = tmp3->gauche;
      free(tmp3->objet);
      tmp3->objet = tmp->objet;
      tmp3->cle = tmp->cle;
      tmp3->gauche = tmp->gauche;
      tmp3->droit = tmp->droit;
      free(tmp);
      tmp = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }
  else
    {
      abr tmp = max_abr(tmp3);
      free(tmp3->objet);
      tmp3->objet = tmp->objet;
      tmp3->cle = tmp->cle;
      if(tmp->gauche != NULL)
	tmp3->gauche = tmp->gauche;
      free(tmp);
      tmp = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }
}