Bonjour,

Aujourd'hui en structure de données, nous avons vu une fonction de suppression de nœuds d'un arbre trié:
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
 
typedef maillon
{
   struct maillon *d; //sous-arbre à droite du nœud
   int x
   struct maillon *g; //sous-arbre à gauche du nœud
}Nœud, *Arbre;
 
Arbre sup (Arbre a, int x) //supprime le nœud ayant la valeur x de l'arbre a
{
	if(vide(a)) return a; //si a non-vide
	if(x == r(a)) //r(Arbre a) retourne la valeur contenu dans la racine (= a->x)
	{
		if(vide(ag(a)) return ad(a);//ag(arbre a) retourne le sous-arbre à gauche de la racine
		if(vide(ad(a)) return ag(a);//ad(arbre a) retourne le sous-arbre à droite de la racine
		return e(otermax(ag(a)), r(ed(ag(a))), ad(a));
		//ed(arbre a) retourne un pointeur sur le nœud contenant la valeur maximale (=extrémité droite)
	}
	if(x < r(a))
	{
		a->g = sup(a->g, x);
		return a;
	}
	a->d = sup(a->d, x);
	return a;
}

avec :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
 
Arbre otermax(Arbre a)
{
	if(vide(a)) return a;
	if(vide(ad(a)) return ag(a);
	a->d = otermax(a->d);
	return a;
}
Passons sur le fait qu'il n'y ai pas de free....

Mais avec un arbre a:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
 
Droite
                           ________ 30
    _______ 60            /
   /            ______ 25-
51-            /          \________ 21
   \_______ 20-          
               \______ 10
 
Gauche
Je souhaite supprimer le nœud ayant la valeur 51.
donc sup(a, 51);
a, n'est pas vide et 51 == r(a)
De plus la partie gauche et droite de l'arbre ne sont pas vides.
Donc je dois faire :
return e(otermax(ag(a), r(ed(ag(a)), ad(a));


ag(a) va donc retourner un arbre ie un pointeur sur le maillon contenant la valeur 20
donc j'ai : e(otermax(b), r(ed(b)), ad(a));

avec arbre b :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
 
               ________ 30
              /
    ______ 25-
   /          \________ 21
20-          
   \______ 10
Or la fonction otermax va modifier le pointeur "d" (sous-arbre de droite) du Nœud contenant la valeur 25 et on va se retrouver avec :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
 
    ______ 25-
   /          \________ 21
20-          
   \______ 10
Donc ed(b) va retourner un pointeur vers le maillon 25 et non vers le maillon 30!

Mais le prof persiste à dire que ed(b) retournera tout de même un pointeur vers le maillon 30.
Si j'ai bien compris ce qu'il a dit, avant de lancer la fonction e, les paramètres vont être enregistré sous forme de copie (->pile d'appel des fonctions)
Mais si ed(b) retourne bel et bien un pointeur vers le maillon contenant la valeur 30,
cela voudrait dire que ed a été exécuté avant otermax???

Pourriez-vous me donner votre avis et si possible me dire comment les fonctions sont exécutées dans e(otermax(ag(a), r(ed(ag(a)), ad(a)); ?