Discussion :

[trollichinelle]

Bonjour à tous,

Voici mon problème: j'ai créé une fonction en C qui doit parcourir un arbre binaire et renvoyer un pointeur sur un noeud dès qu'il trouve une valeur que je lui donne en paramètre, cette fonction marche dans 80% des cas, mais dans 20% des cas elle me renvoie le pointeur sur le dernier noeud de l'arbre.
Je précise que j'effectue un parcours préfixe et qu'il s'agit d'un arbre binaire, je fais un controle dans la fonction (cf code: noeud cherché, noeud trouvé) et qu'il présente le pointeur sur le bon noeud, en faisant le même contrôle dans le main sur la valeur de retour je m'aperçoit que le pointeur n'est plus le bon.

Quelqu'un aurait-il une idée de la raison de ce comportement?

un grand merci pour vos réponses

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
 
NODE* parcoursVal (NODE * ptrNod, int valName) {
 
NODE* ptrRd;
 
 
 if (ptrNod->name == valName) 
 {
 printf("noeud cherché %i, noeud trouvé %i\n",valName,ptrNod->name);
 
 return ptrNod;
 }
 
 if (ptrNod->filsg != NULL) {
  parcoursVal (ptrNod->filsg, valName);
 }
 
 if (ptrNod->filsd != NULL) {
 parcoursVal (ptrNod->filsd, valName);
 }
 
}

[Invité]

Tu arrives en compiler ? Parce que ta fonction ne renvoie pas de valeurs dans tous les cas. Je pense qu'il faudrait renvoyer quelque chose si le fils gauche et le fils droit sont nuls.

[trollichinelle]

merci de ta réponse,

effectivement ça compile et ne plante pas, ton idée est intéressante mais comme il s'agit d'un parcours prefixe, la valeur est checkée et donc le return est avant les fils je pense, même si ils sont nuls

je complète en rajoutant l'appel dans le main:

Code :

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

1
2
3
4
 
ptrRandNode = parcoursVal (root, subT);
 
printf("verif: %i\n",ptrRandNode->name); //verif:

et un affichage typique de l'erreur:

noeud au hasard dans le sous arbre: 3
noeud cherché 3, noeud trouvé 3
verif: 9

[trollichinelle]

J'aimerais savoir également si ce genre de return dans une récursive est conforme, ce dont je commence à douter,
pour information si je lui demande de trouver une valeur qui n'existe pas dans l'arbre il me renvoie également le pointeur sur le dernier noeud de l'arbre mais il n'est pas rentré dans le if de la fonction dans ce cas

[je®ome]

J'aimerais savoir également si ce genre de return dans une récursive est conforme, ce dont je commence à douter,
pour information si je lui demande de trouver une valeur qui n'existe pas dans l'arbre il me renvoie également le pointeur sur le dernier noeud de l'arbre mais il n'est pas rentré dans le if de la fonction dans ce cas

Le cas d'arrêt est une des choses les plus importantes dans des fonctions récursives. Dans ton cas, s'il ne s'agit pas du bon noeud et que les fils sont nuls, que ce passe-t-il ??
C'est tout à fait normal que le résultat retourné est erroné si le nombre n'est pas trouvé, puisque tu imprimes le retour d'une fonction ne renvoyant rien.

[Invité]

Je ne comprends pas vraiment, à mon avis, Gastiflex a raison, il faut également renvoyer le résultat dans le cas des fils.

Oulah oui. C'est pas à ça que je pensais, mais c'est vrai qu'il faudrait que ce soit comme ça.
Ce que je pensais, c'est le return dans le cas où la valeur n'est pas trouvée et où il n'y a pas de fils gauche et droite. En résumé avec les ajouts de Jerome :

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
 
NODE* parcoursVal (NODE * ptrNod, int valName) {
 
NODE* ptrRd;
 
 
 if (ptrNod->name == valName) 
 {
 printf("noeud cherché %i, noeud trouvé %i\n",valName,ptrNod->name);
 
 return ptrNod;
 }
 
if(ptrNod->filsg == NULL && ptrNod->filsd == NULL)
  return NULL;
 
 if (ptrNod->filsg != NULL) {
  return parcoursVal (ptrNod->filsg, valName);
 }
 
 if (ptrNod->filsd != NULL) {
 return parcoursVal (ptrNod->filsd, valName);
 }
 
}

[je®ome]

comme il s'agit d'un parcours prefixe, la valeur est checkée et donc le return est avant les fils je pense, même si ils sont nuls

Je ne comprends pas vraiment, à mon avis, Gastiflex a raison, il faut également renvoyer le résultat dans le cas des fils.

Code :

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

1
2
3
4
5
6
7
if (ptrNod->filsg != NULL) {
  return parcoursVal (ptrNod->filsg, valName);
 }
 
 if (ptrNod->filsd != NULL) {
  return  parcoursVal (ptrNod->filsd, valName);
 }

Sinon le résultat ne sera pas propagé jusqu'à la fonction appelante de départ.