Discussion :

[ypcman]

Bonjour.
Je pars d'un arbre binaire non trié (ce n'est pas un abr). Chaque nœud contient une valeur entière et les adresses de ses fils gauche et droit.
Je cherche à trouver l'adresse du nœud contenant une valeur donnée. J'ai codé une fct récursive censé renvoyer cette adresse.

La fct trouve bien la bonne adresse mais ne renvoie pas celle-ci :

20 ( 9 ( 15 ( 1 , 8 ) , 3 ( 4 , 6 ) ) , 16 ( 14 ( 12 , 7 ) , )
valeur testée : 20
valeur testée : 9
valeur testée : 15
valeur testée : 1
valeur testée : 8
valeur testée : 3
valeur testée : 4
Trouvé valeur 4 en 0x18caef0
valeur testée : 6
valeur testée : 16
valeur testée : 14
valeur testée : 12
valeur testée : 7

Le pb vient probablement de la façon de sortir de la récursive mais je sèche ...

Voici mon code :

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
57
58
59
60
61
62
63
64
65
66
#include <iostream>
using namespace std;
 
typedef struct noeud noeud;
struct noeud {
	int valeur;
	noeud *fils_gauche;
	noeud *fils_droite;
};
using arbreBinaire = noeud *;
 
void affiche(arbreBinaire);
noeud* getPtrNoeud(int, arbreBinaire);
int main() {
	noeud *n1 = new noeud { 1, nullptr, nullptr };
	noeud *n2 = new noeud { 8, nullptr, nullptr };
	noeud *n3 = new noeud { 4, nullptr, nullptr };
	noeud *n4 = new noeud { 6, nullptr, nullptr };
	noeud *n5 = new noeud { 12, nullptr, nullptr };
	noeud *n6 = new noeud { 7, nullptr, nullptr };
	noeud *n7 = new noeud { 15, n1, n2 };
	noeud *n8 = new noeud { 3, n3, n4 };
	noeud *n9 = new noeud { 14, n5, n6 };
 
	noeud *n10 = new noeud { 9, n7, n8 };
	noeud *n11 = new noeud { 16, n9, nullptr };
	noeud *n12 = new noeud { 20, n10, n11 };
	arbreBinaire ab = n12;
	affiche(ab);
	cout << endl;
	noeud *n = new noeud;
	n = getPtrNoeud(4, ab);
	cout << "Résultat : " << n->valeur << endl;
	return 0;
}
 
void affiche(arbreBinaire ab) {
	if (ab != nullptr) {
		cout << ab->valeur << " ";
		if (ab->fils_gauche != nullptr) {
			cout << " ( ";
			affiche(ab->fils_gauche);
		}
		if (ab->fils_gauche != nullptr || ab->fils_droite != nullptr) {
			cout << ", ";
		}
		if (ab->fils_droite != nullptr) {
			affiche(ab->fils_droite);
			cout << " ) ";
		}
	}
}
 
noeud* getPtrNoeud(int v, arbreBinaire ab) {
	cout << "valeur testée : " << ab->valeur << endl;
	if (ab->valeur == v) {
		cout << "Trouvé valeur " << ab->valeur << " en " << ab << endl;
		return ab;
	}
	if (ab->fils_gauche != nullptr) {
		getPtrNoeud(v, ab->fils_gauche);
	}
	if (ab->fils_droite != nullptr) {
		getPtrNoeud(v, ab->fils_droite);
	}
}

[Flodelarab]

Bonjour

Ligne 61 et 64, tu appelles la fonction mais quand elle elle renvoie une valeur, tu n'en fais rien. Ne serait-ce pas plutôt return getPtrNoeud(...) ?
Et encore, il faudrait tester si le retour est non nul.

[ypcman]

Bonjour

Ligne 61 et 64, tu appelles la fonction mais quand elle elle renvoie une valeur, tu n'en fais rien. Ne serait-ce pas plutôt return getPtrNoeud(...) ?
Et encore, il faudrait tester si le retour est non nul.

j'ai déjà testé et si j'ajoute ces 2 return, la fct descend l'arbre du coté gauche jusqu'en bas et s’arrête ...

[tbc92]

Comme Flodelarab, ta fonction communique avec l'extérieur via l'instruction Return. Si l'extérieur n'écoute pas ce que la fonction dit, ça ne sert à rien. Il faut récupérer la valeur renvoyer par le return, et voir ce qu'on en fait.

Autre point : Quand on trouve la valeur cherchée, le traitement doit s'arrêter. Le traitement ne devrait pas aller lire la suite de l'arbre.

Je pense que si tu veux garder la même logique, ta fonction récursive ne doit pas renvoyer une structure de type noeud, mais une structure de type noeud+booleen
Le booleen étant à Vrai ou Faux.
Tant que l'élément cherché n'a pas été trouvé, on renvoyer Faux. Et quand il est trouvé on renvoie Vrai.

Quelque chose plus ou moins comme ça :

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
 
noeud* getPtrNoeud(int v, arbreBinaire ab) {
	cout << "valeur testée : " << ab->valeur << endl;
	if (ab->valeur == v) {
		cout << "Trouvé valeur " << ab->valeur << " en " << ab << endl;
		return ab, True ;
	}
	if (ab->fils_gauche != nullptr) {
		(newNoeud, NewBool) = getPtrNoeud(v, ab->fils_gauche);
                if NewBool {
                   return newNoeud, NewBool
                }
	}
	if (ab->fils_droite != nullptr) {
		(newNoeud, NewBool) = getPtrNoeud(v, ab->fils_droite);
                if NewBool {
                   return newNoeud, NewBool
                }
	}
}

Dès que ce Booléen est Vrai, on fait en sorte de n'exécuter que des instruction RETURN, en renvoyant à la fois l'adresse du noeud, et le flag 'True'.


Edit :je vois que le problème a été résolu entre temps, je suis vraiment trop lent.

[ypcman]

C'était bien dans la récursive :

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
using namespace std;
*
typedef struct noeud noeud;
struct noeud {
	int valeur;
	noeud *fils_gauche;
	noeud *fils_droite;
};
using arbreBinaire = noeud *;
*
void affiche(arbreBinaire);
noeud* getPtrNoeud(int, arbreBinaire);
int main() {
	noeud *n1 = new noeud { 1, nullptr, nullptr };
	noeud *n2 = new noeud { 8, nullptr, nullptr };
	noeud *n3 = new noeud { 4, nullptr, nullptr };
	noeud *n4 = new noeud { 6, nullptr, nullptr };
	noeud *n5 = new noeud { 12, nullptr, nullptr };
	noeud *n6 = new noeud { 7, nullptr, nullptr };
	noeud *n7 = new noeud { 15, n1, n2 };
	noeud *n8 = new noeud { 3, n3, n4 };
	noeud *n9 = new noeud { 14, n5, n6 };
*
	noeud *n10 = new noeud { 9, n7, n8 };
	noeud *n11 = new noeud { 16, n9, nullptr };
	noeud *n12 = new noeud { 20, n10, n11 };
	arbreBinaire ab = n12;
	affiche(ab);
	cout << endl;
	noeud *n = new noeud;
	n = getPtrNoeud(4, ab);
	cout << "Résultat : " << n->valeur << endl;
	return 0;
}
*
void affiche(arbreBinaire ab) {
	if (ab != nullptr) {
		cout << ab->valeur << " ";
		if (ab->fils_gauche != nullptr) {
			cout << " ( ";
			affiche(ab->fils_gauche);
		}
		if (ab->fils_gauche != nullptr || ab->fils_droite != nullptr) {
			cout << ", ";
		}
		if (ab->fils_droite != nullptr) {
			affiche(ab->fils_droite);
			cout << " ) ";
		}
	}
}
*
noeud* getPtrNoeud(int v, arbreBinaire ab) {
	cout << "valeur testée : " << ab->valeur << endl;
	if (ab->valeur == v) {
		cout << "Trouvé valeur " << ab->valeur << " en " << ab << endl;
		return ab;
	}
	if (ab->fils_gauche != nullptr) {
            if(noeud * gauche = getPtrNoeud(v, ab->fils_gauche)){
                return gauche;
            } 
	}
	if (ab->fils_droite != nullptr) {
            if (noeud * droite = getPtrNoeud(v, ab->fils_droite)){
                return droite;
            }
	}
    return nullptr;
}