Bonjour,
Je révisais mon cours sur les arbres et il y a quelquechose que je n'arrive pas à comprendre.
Voici la structure d'arbre :
Et voila l'algo de suppression d'un élément :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 typedef struct Noeud Noeud; struct Noeud { int info; struct Noeud* sag; struct Noeud* sad; }; typedef struct Noeud* Ptr_noeud;
Donc en gros on commence par chercher l'élément et après on le supprime en fonction du nombre de fils qu'il a. Le problème c'est quand il en a deux, on est obligé de chercher le plus grand élément de son sous arbre gauche et de remplacer les deux éléments. Ce que je comprends pas c'est cette ligne : *pp = max->sag; En gros on met dans pp l'adresse de max->sag et après fait : supprimer(pp, max->info); Mais lors de la suppression, max->info se trouve 'au desus', donc il va jamais le trouver, donc jamais le supprimer ?
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 int supprimer(Ptr_noeud *tete, int x) { Ptr_noeud tmp = NULL, max = NULL; Ptr_noeud *pp = NULL; int ok = 0; if ((*tete) != NULL) { if ((*tete)->info < x) { supprimer(&((*tete)->sad), x); } else if ((*tete)->info > x) { supprimer(&((*tete)->sag), x); } else { ok = 1; if ((*tete)->sag == NULL) { tmp = (*tete); (*tete) = (*tete)->sad; free(tmp); } else if ((*tete)->sad == NULL) { tmp = (*tete); (*tete) = (*tete)->sag; free(tmp); } else { pp = &((*tete)->sag); while ((*pp)->sad != NULL) { pp = &((*pp)->sad); } max = *pp; //A partir de la je comprends pas! *pp = max->sag; (*tete)->info = max->info; supprimer(pp, max->info); } } } return ok; }
Merci de votre aide.
PS : Cet algo fonctionne, c'est juste que je comprends pas pourquoi !
Partager