Discussion :

[hindou90]

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é]

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]

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]

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é]

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]

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.

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]

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 ...