Récursive parcours d'arbre

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:

---

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); }   }

---

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.

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:

---

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

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

Citation:

---

Envoyé par trollichinelle

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:

---

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.

Citation:

---

Envoyé par 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

---

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.

Citation:

---

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:

---

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); }   }

---

Merci à vous deux pour votre aide cela me permet de nourrir ma reflexion,

Gastiflex ta solution ne me renvoie pas les resultats corrects, je ne suis pas sûr mais je crois qu'elle renvoie le fils le plus a gauche (avant je renvoyait le dernier fils, le plus à droite)

je suis déçu de pas trouver plus d'info sur le net, je pensais qu'un tel parcours par valeur était un classique des fonctions d'arbres binaires

je pense comme vous le soulignez qu'il y a un problème de propagation dans la récursive, je vais essayer différentes solutions , même si la recursive me semble incontournable dans un pareil parcours d'arbre.

merci encore

Je n'ai pas résolu mon problème mais je suis parvenu à mes fins avec un parcours itératif avec une pile, je ne sais pas si cela est faisable en récursif mais ça ne me semble pas le plus judicieux.

Si jamais quelqu'un connait la façon récursive de le faire qu'il n'hésite pas à la donner, cela peut être intéressant.

Je crois que ceci fonctionne :

Code:

---

1 2 3 4 5 6 7 8 9 10

NODE* parcoursVal (NODE * ptrNod, int valName) { NODE* ptrRd = ptrNod; if (ptrRd != NULL && ptrRd->name != valName ) { ptrRd = parcoursVal (ptrNod->filsg, valName); if (ptrRd == NULL)ptrRd = parcoursVal (ptrNod->filsd, valName); } return ptrRd ; }

---

Effectivement cela fonctionne, félicitations, merci.