Valeurs de retours de fonctions en paramètre d'une autre fonction
Bonjour,
Aujourd'hui en structure de données, nous avons vu une fonction de suppression de nœuds d'un arbre trié:
Code:
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:
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:
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:
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:
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)); ?
