suppression arbre ABR

**hindou90** · 02/06/2010, 12h24

Bonjour toutes et tous
Si l'ajout et l'affichage d'un arbre(ABR) est facile,par contre la suppression est très difficile !!
bon j'ai essaye de le faire et mais je n'arrive pas à avancer.
pour supprimer un nœud dans un ABR, 3 conditions sont possible:
*si le nœud qui contient la valeur ,est une feuille donc la suppression est facile =>free
*si le nœud possède un seul fils,alors la suppression est équivalent à celle d'une liste chainée(et c'est là où je bloque

)
*si le nœud possède 2 fils alors on lui remplace par son prédécesseur et ce dernier va être libérer.

voici mon essai:

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
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
                 /*PROGRAMME DE REVISION DE ABR (COURS)*/
/*DEFINITION DE L'ARBRE*/
typedef struct noeud
{
        int info;
        struct noeud* sag;
        struct noeud* sad;
}noeud;
void creation(noeud **r,int x)//creation d'un noeud 
{
     if((*r)==NULL)
     {
                   (*r)=(noeud*)malloc(sizeof(noeud));
                   (*r)->info=x;
                   (*r)->sag=NULL;
                   (*r)->sad=NULL; 
     }
     else
     {
                   if(x>(*r)->info)
                             creation(&((*r)->sad),x);      
                   else
                             if(x<(*r)->info)
                             creation(&((*r)->sag),x); 
                             else
                             printf("la valeur existe deja ");
     }
}
noeud* predecesseur(noeud *r)//la fonction qui permet de retourner l'@ de son predecesseur
{
    if(r->sad!=NULL)
       predecesseur(r->sad);
    else
        return (r);
}  
 
noued* recherche(noeud *r,int x)//C la recherche dichatomique
{
               if(r==NULL)
                          return NULL;/*on est arrivé à la fin et qu'on a pas trouvé x,ou bien l'arbre est vide*/
               if(r->info==x)
                          return r;
               if(r->info>x)/*on va chercher dans la partie gauche*/
                  return         recherche(r->sag,x);
               else
                  return         recherche(r->sad,x);
 
}
int estFeuille(noeud *r)
{
    return(r->sag==NULL&&r->sad==NULL);
 
 
}   
 
 
int main()
{
     noeud *r=NULL;
     int rech;
     creation(&r,5);
     creation(&r,10);
     creation(&r,46);
     creation(&r,6);
     printf("Taper la valeur à chercher \n");
     scanf("%d",&rech);
 
     if(recherche(r,46)==NULL)
                              printf("la valeur n'existe pas");
     else 
     {
          noeud *x=recherche(r,46);/*recupere les le noeud qui porte la valeur chercher */
 
          if(estFeuille(x)==1)//si c'est unr freuille =>free.
                              free(x);
          else 
          {
               if(x->sag!=NULL&&x->sad!=NULL)//s'il posséde 2 fils 
               {
                                                    noeud *p=predecesseur(x);//récupere le predecesseur
                                                    x->info=p->info; //passer l'information
                                                    free(p);//et enfin liberer le predecesseur
               }
               else
               {
                   if(x->sag!=NULL) // il a un seul fils=>gauche
               //C LA où je me bloque !
               }             
          } 
 
 
      }
 
     getch();
     return 0;
}

je serais très reconnaissante si quelqu'un peut m'aider à faire ce qui reste.

a+

Invité · 02/06/2010, 14h17

Bonjour,

Quant on crée l'arbre, à tout moment on sait d'où on vient, donc facile

.
Quand on doit le libérer, on ne sait pas où on va, donc difficile

L'astuce, c'est de se souvenir de là où on doit continuer lorsqu'on a libéré une branche.
Essayez d'écrire le code et relancez moi.
Bon courage.

**hindou90** · 02/06/2010, 15h12

merci pour votre réponse
donc je dois créer une fct qui permet de retourner le père du noeud à supprimer,non?
je vais essayer de le faire et je poste le résultat.

a+

**diogene** · 02/06/2010, 16h46

donc je dois créer une fct qui permet de retourner le père du noeud à supprimer,non?

Pour supprimer un noeud, il va falloir modifier les pointeurs du père, donc situer le père. Ce n'est pas très économique puisqu'il va falloir parcourir l'arbre depuis la racine. Si les suppressions peuvent être nombreuses, il est possible d'ajouter à chaque noeud un pointeur sur son père mis à jour au moment de l'insertion dans l'arbre. L'inconvénient est que le noeud sera un peu plus gros et utilisera plus de mémoire.

*si le nœud possède 2 fils alors on lui remplace par son prédécesseur et ce dernier va être libérer.

??? Le prédécesseur pour toi c'est le père ?

La procédure habituelle est plus complexe à décrire :

- A partir du noeud N à supprimer, parcourir l'arbre une fois à gauche (ou à droite) puis toujours vers la droite (resp vers la gauche) jusqu'au dernier noeud D. Remplacer les données du noeud N par celles du noeud D. Supprimer physiquement le noeud D (qui lui n'a au plus qu'un seul fils)

Exemple : supprimer 50 dans la portion d'arbre suivant (le chemin à suivre est montré par un double lien) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
             100                100
           /     \             /   \
         50(N)    ..          45    ..
       //    \               /   \
     30       60           30    60
    /  \\    /..\         /  \   /..\
   ..   40              ..   40
       /  \\                 / \
      ..   45(D)            .. 42
           /                   / \
          42                  .. ..
         /  \
        ..  ..

Invité · 02/06/2010, 18h01

Bonjour,
Cette organisation de suppression n'est pas forcément celle que l'on souhaite toujours.
Si on veut supprimer le noeud 50, c'est donc que tous les noeuds descendants ne doivent plus exister donc sont à supprimer.
Dans l'exemple, le noeud 45(D) est un descendant de 50(E), donc il doit être supprimé, or, il est maintenant un fils direct de 100, donc on ne sait plus qu'il doit être supprimé.
Je pense plutôt qu'il faut supprimer tous les descendants de 50, c'est à dire en commençant par la fin, les feuilles, jusqu'à ce que 50 n'ai plus de fils, il pourra donc être supprimé.
Je crois que dans une organisation d'arbre, il faut distinguer les noeuds qui ne possèdent aucune autre information que d'avoir 2 fils, et le feuilles, extrémité sans descendant qui contiennent une information, justement celle que l'on veut atteindre avec l'arboresnce.
Concernant l'utilisation de l'arbre, l'intérêt est que lorsqu'on veut utiliser l'objet 100, il est facile de trouver tous les objets feuille.

C'est ce qui la différencie d'une liste chainée. Une liste chainée est une liste dont tout les membres sont au même niveau d'intérêt. Si on supprime un objet de la liste, le pointeur précédent va pointer sur le pointeur suivant, c'est particulièrement rapide.

gl · 02/06/2010, 18h45

Envoyé par Pierre Dolez

Si on veut supprimer le noeud 50, c'est donc que tous les noeuds descendants ne doivent plus exister donc sont à supprimer.

Dans un ABR, généralement on cherche à supprimer un élément. Rarement tous les éléments fils d'un élément.

Envoyé par Pierre Dolez

Je crois que dans une organisation d'arbre, il faut distinguer les nœuds qui ne possèdent aucune autre information que d'avoir 2 fils, et le feuilles, extrémité sans descendant qui contiennent une information, justement celle que l'on veut atteindre avec arborescence.

Mais tous les nœuds d'un ABR transporte une information (autre que l'info de chaînage des fils).

Certains peuvent en plus posséder un ou deux fils.

**diogene** · 02/06/2010, 19h02

Pierre Dolez :

Si on veut supprimer le noeud 50, c'est donc que tous les noeuds descendants ne doivent plus exister donc sont à supprimer.
Dans l'exemple, le noeud 45(D) est un descendant de 50(E), ...

La question est de savoir si on veut supprimer un noeud ou un sous-arbre. Le posteur parlait de la suppression d'un noeud. Supprimer un sous-arbre ne demande d'ailleurs pas d'écrire un code particulier puisqu'on peut utiliser le code qui a été obligatoirement (si on est sérieux) écrit pour supprimer l'arbre entier et récupérer la mémoire.

Pierre Dolez :

Je crois que dans une organisation d'arbre, il faut distinguer les noeuds qui ne possèdent aucune autre information que d'avoir 2 fils, et le feuilles, extrémité sans descendant qui contiennent une information, justement celle que l'on veut atteindre avec l'arboresnce

C'est une possibilité d'organisation, mais dans le cas de cet arbre binaire de recherche, chaque noeud, et pas seulement les feuilles, possède une information. Je cite hindou90 :

*si le nœud qui contient la valeur ,est une feuille donc ...
*si le nœud possède un seul fils...
*si le nœud possède 2 fils ...

**NoIdea** · 07/06/2010, 22h38

Il me semble qu'il faudrait que ta struct noeud soit plutôt du type :

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
struct noeud
{
    int info;
    noeud*parent;
    noeud*enfant_1;
    noeud*enfant_2;
};
 
//ou encore, en plus générique :
 
struct noeud
{
    Information info;
    noeud*parent;
    noeud**enfants;//Tableau de noeuds
};

En espérant que sa puisse t'aider

gl · 07/06/2010, 23h33

Envoyé par NoIdea

Code :

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

1
2
3
4
5
6
7
8
//ou encore, en plus générique :
 
struct noeud
{
    Information info;
    noeud*parent;
    noeud**enfants;//Tableau de noeuds
};

En espérant que sa puisse t'aider

L'utilisation d'un tableau de nœuds dans le cas d'un arbre quelconque est effectivement à envisager. Mais dans le cas d'un arbre binaire de recherche ce n'est pas franchement utile puisqu'il faudra de tout manière limité la taille de ce tableau à 2.

**ironzorg** · 08/06/2010, 07h59

Ajouter un pointeur vers le noeud parent dans chaque noeud peut simplifier les choses. Apres tout un arbre fonctionne de la meme maniere qu'une liste, ce qui compte c'est de ne pas se perdre et bien free() tous les noeuds !

**koala01** · 08/06/2010, 11h34

Salut,

Envoyé par ironzorg

Ajouter un pointeur vers le noeud parent dans chaque noeud peut simplifier les choses. Apres tout un arbre fonctionne de la meme maniere qu'une liste, ce qui compte c'est de ne pas se perdre et bien free() tous les noeuds !

Et encore...

Grace à la récursivité, il est souvent possible de se passer de cette référence vers le noeud parent.

Je sais que la récursivité a souvent mauvaise presse, en partie à cause d'un effet de dépassement de pile toujours possible, mais aussi en grande partie à cause de la difficulté qu'éprouvent beaucoup de gens à la gérer correctement.

Or, une fois que l'on en a compris le principe et que l'on sait qu'il faut impérativement tester le cas de base, le reste va "tout seul"

suppression arbre ABR

C

Discussions similaires

Partager

Partager