suppression d'un arbre binaire

**NomUtilisateurDejaPris** · 14/02/2004, 16h45

Bonjour,
je manipule un arbre binaire et, à mon grand regret, je n'arrive pas à en supprimer une partie. Voila mon 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
 
//voila le type de l'arbre:
struct noeud
    {
    int val;
    struct noeud * G;
    struct noeud * D;
    };
typedef struct noeud Noeud;
typedef struct noeud * ptr;
 
//voila ma fonction SupprArbre:
void SupprArbre (ptr *A)
{
  ptr x=*A;
  if(!ptrVide(*A))
    { 
      ptr p;
      p=FilsGauche(*A);SupprArbre(&p);
      p=FilsDroit(*A);SupprArbre(&p);
      free(x);
     x=NULL;
    }
}
 
//voila la partie de code ki me turlupine: 
 
    printf("r avant:\n");
    AffArbre(r);
    getchar();
    SupprArbre(&r);
    printf("r apres:\n");
    AffArbre(r);
    getchar();

En effet, lors de l'affichage de l'arbre r, ben c'est exactement la même chose qui est affichée! Moi, je souhaiterais qu'après l'appel de la fonction SupprArbre, l'arbre r soit à NULL et que l'espace mémoire qui était alloué à partir de r soit libéré bien sur.
Merci.

gl · 14/02/2004, 16h53

Dans la fonction de suppression tu ne travaille pas sur l'arbre, mais sur un autre arbre qui pointe au meme endroit. En clair tu libere bien l'espace memoire avec free(x) (puisque x et *A pointe au meme endroit), mais jamais tu ne remet A a NULL, c'est x que tu mets a NULL, il faudrait faire *A = NULL.
D'ailleurs les variables x et p ne sont pas utiles.

**khayyam90** · 14/02/2004, 16h55

j'espère ne pas me tromper, mais ça me gène de voir que tu déclares A comme un ptr* alors que ptr est déjà un pointeur. essaie de mettre simplement ptr x=A; et non ptr x=*A;

remplace tous tes *A par des A

de même fais un supprarbre(p) et pas &p.

aussi, dans l'appel, fais supprarbre(r) car r est déjà une adresse.

gl · 14/02/2004, 17h39

Envoyé par khayyam90

j'espère ne pas me tromper, mais ça me gène de voir que tu déclares A comme un ptr* alors que ptr est déjà un pointeur. essaie de mettre simplement ptr x=A; et non ptr x=*A;

remplace tous tes *A par des A

de même fais un supprarbre(p) et pas &p.

aussi, dans l'appel, fais supprarbre(r) car r est déjà une adresse.

Non comme il souhaite modifier l'adresse et non le contenu de r (il veut le mettre a NULL dans sa suppression), il faut bien passer un pointeur sur pointeur.

**NomUtilisateurDejaPris** · 14/02/2004, 17h39

La solution de gl fonctionne et me convient tout à fait.
Maintenant, un autre problème.
J'ai une fonction CreaCorresp telle que :
void CreaCorresp (ptr p, int nb)

Dans cette fonction, je parcours l'arbre p et le modifie (je supprime une partie de cet arbre à l'aide de la fonction SupprArbre). Ainsi, lorsque j'arrive au niveau d'une feuille j'effectue un traitement et, supprime le pointeur de cette feuille. Je boucle ceci tant que je ne suis pas passé par toutes les feuilles. Alors, au debut de la boucle, j'ai une declaration telle que :
ptr r=p; //où p est l'arbre passé en paramètre
//et r se deplace dans p
Cette initialisation me permet donc de revenir à la racine au debut de la boucle.
Le truc, c'est qu'apparemment, r est supprimé correctement, mais dans l'arbre p (au niveau de r), le pointeur n'est pas à NULL. Pourtant lors de l'initialisation, p et r pointe sur le même objet, alors si je modifie r un peu plus loin , p devrait être modifié de la même facon nan?

gl · 15/02/2004, 12h03

Envoyé par NomUtilisateurDejaPris

Le truc, c'est qu'apparemment, r est supprimé correctement, mais dans l'arbre p (au niveau de r), le pointeur n'est pas à NULL. Pourtant lors de l'initialisation, p et r pointe sur le même objet, alors si je modifie r un peu plus loin , p devrait être modifié de la même facon nan?

Peux-tu poster le code de cette fonction ainsi que l'appel, que l'on puisse voir ce qui se passe.

**NomUtilisateurDejaPris** · 15/02/2004, 12h40

Voila le code de la fonction CreaCorresp :

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
 
void CreaCorresp (ptr p, int nb)
{
int i=0;
t_cor tab;
while(i != nb)
    {
    ptr r=p; //r: pointeur ki bouj ds larbre
    while(!Feuille(r))
       if(!ptrVide(FilsGauche(r)))
          r=FilsGauche(r);
       else 
          r=FilsDroit(r);
    tab.tablo[i].c=CaracArbre(r);
    SupprArbre(&r);
    i++;
    }
}
 
//L'appel de cette fonctoin se fait tout simplement comme il suit:
CreaCorresp(pt,lg);

Grâce à différent tests, je sais qu'après l'appel de SupprArbre(&r), r est à NULL. Pourtant, il semblerait que dans p, cette même partie n'est pas à NULL.
Comme je l'ai dit dans un précedent message, je fais l'initialisation r=p pour remettre l'arbre r au niveau de la racine de l'arbre.

gl · 15/02/2004, 12h57

Tu as le meme probleme que precedement, la fonction SupprArbre modifie le pointeur r, mais pas le contenu de p. En effet, lorsque tu fais r=p, les deux pointeurs designe la meme zone memoire, ensuite tu te promene dans ton arbre et tu supprimme des elements, ces elements sont effectivement supprimmer, mais quand tu mets ensuite r a NULL, tu modifie ce sur quoi pointe r, mais aucunement le contenu de p. Generalement lorsque l'on supprimme des elements de la sorte, on ne supprimme pas l'element sur lequel on se trouve, mais un de ces fils, ensuite lorsque tu mets le fils en question a NULL, la modification est visible depuis r ET depuis p puisque tu modifie le contenu de la memoire pointe par r et, indirectement, par p.