Arbre binaire Java

Bonsoir, j’essaye d’implémenter une structure d’arbre binaire en Java ainsi que ses fonctions principales. J’ai un petit soucis lors de l’implémentation d’une fonction de recherche d’un élément n dans l’arbre binaire qui si il le trouve, le programme return true sinon false.

 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

public class Arbre {
    private int valeur;
    private  Arbre gauche;
    private  Arbre droit;


    public Arbre(int x) {
        this.valeur = x;
    }

    public Arbre(int x, Arbre g, Arbre d) {
        this.valeur = x;
        this.gauche = g;
        this.droit = d;
    }

    public int getValeur() {
        return valeur;
    }
    public Arbre getSousArbreGauche() {
        return gauche;
    }
    public Arbre getSousArbreDroit() {
        return droit;
    }

    public static void afficheNoeud(Arbre a)
    {
        if(a != null)
        {
            System.out.println(a.valeur);
            afficheNoeud(a.gauche);
            afficheNoeud(a.droit);

        }
    }
    public static boolean trouveElem(Arbre a, int n) {;
        if(a != null)
        {   
            System.out.println(1);
            if(a.valeur == n) {
                System.out.println(2);
                return true ;
            }
            else
            {
             System.out.println(3);
             trouveElem(a.gauche, n);
             trouveElem(a.droit, n);
            }
        }
        System.out.println(4);
        return false; 

}

    public static void main(String[] args) {
        Arbre b = new Arbre(2);
        Arbre c = new Arbre(10);
        Arbre a = new Arbre(5,b,c);
        afficheNoeud(a);
        System.out.println(trouveElem(a, 2));
        //System.out.println(trouveElem(a, 5));
    }

}

`

Le résultat donne ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

5 //
2 // affichage de l'arbre
10 // 
1
3
1
2 // On voit qu'il passe dans le if mais ne return rien
4
1
3
4
4
4
4
false

Dans cet arbre il y a 3 sommets, la racine est 5 et a deux fils 2 et 10. Dans mon main je cherche l’élément 2 donc la fonction devrait return true. Ce que je comprends pas c’est qu’on voit bien qu’il passe dans mon deuxième if (affichage du 2) mais il ne return rien.

Merci d’avance !

Bonsoir,

Je pense que ton problème se trouve aux lignes 48 et 49. Que l’appel à trouveElem renvoie true ou false, tu ne va pas utiliser cette valeur : elle n’est ni affectée, ni renvoyer (à l’aide d’un return). Une possibilité serait d’utiliser à la place de ces deux lignes (48 et 49) la ligne suivante :

return (trouveElem(a.gauche, n) || trouveElem(a.droit, n));

Bonne soirée.

En effet c’était bien ça le problème, merci beaucoup !

Lorsque tu dis qu’on ne va pas utiliser ou renvoyer cette valeur, c’est à cause des appels récursifs et que les appels sont "empilés" et puis "dépilés" ?

Non il veut tout simplement dire que tu n’utilise pas la valeur retourné par les appelles récursifs (ligne 48 et 49).

En fait il faut se demander ce qu’il va se passer avec l’appel récursif et comment tu utilises la valeur retourner. En particulier que fait la ligne 47 ? Elle appelle trouveElem qui va déterminer si l’élément est présent dans le sous-arbre gauche et va renvoyer le résultat à la fonction qui l’a appelé. Dans ton cas que fait la fonction qui l’a appelé de ce résultat ? Rien du tout : il faudrait de nouveau renvoyer ce résultat !

1
2
3
4
5
6
7
8

boolean f() {
   g();
   return false;
}

boolean g() {
   return true;
}

Que se passe-t-il dans la fonction f() ci-dessus ? g() est appelé mais le résultat n’est pas utilisé et c’est systématiquement false qui va être renvoyé. C’est un peu ce qu’il se passait dans ton code initialement : la seule possibilité de renvoyer true était de propager le return true jusqu’à l’appel initial et cela n’était possible que s’il n’y avait aucun appel récursif. Dès qu’il y a plus d’un appel récursif (c’est en particulier le cas pour chercher 2), la valeur true était retournée à l’appelant mais celui-ci n’en fait rien, il continue à s’exécuter lui-même (et va renvoyer false avec la ligne 53).

Plus généralement une fonction récursive a souvent la forme suivante :

1
2
3
4
5
6
7

ma_fonction_recursive() {
   if {
      // Cas simple sans appel récursif
   } else {
      // Cas avec des appels récursifs
   }
}

Et il n’y a pas besoin d’autre chose. Dans ton code si tu n’avais pas la ligne 53, le compilateur aurait détecté un problème : dans les cas où tu rentrais dans le else tu ne renvoyais rien et donc la signature de la fonction n’aurait pas été respectée.

Si tu veux t’entraîner à faire des fonctions récursives simples. Tu peux essayer essayer d’implémenter plusieurs choses : 1) Compter le nombre d’éléments dans ton arbre. 2) Les parcours infixes, préfixes et postfixes (choisis l’un des trois car les solutions sont proches).

Avec l’arbre suivant : 

Le parcours préfixe : la racine est traitée avant les appels récursifs sous le sous-arbre gauche puis le sous-arbre droit (donc racine puis sous-arbre gauche puis sous-arbre droit). 10 8 3 15 20 5 4 dans notre cas.

Le parcours infixe : sous-arbre gauche puis racine puis sous-arbre droit. 3 8 20 15 10 4 5 dans notre cas.

Le parcours suffixe : sous-arbre gauche puis sous-arbre droit puis racine. 3 20 15 8 4 5 10 dans notre cas.

J’espère t’avoir aidé, si tu as d’autres questions n’hésite pas !

D’autre part, pourquoi des méthodes de classe public static void afficheNoeud(Arbre a) et public static boolean trouveElem(Arbre a, int n) au lieu de méthodes d’instances public void afficheNoeud() et public boolean trouveElem(int n) ? Ça paraîtrait plus logique et simplifierait le code.

(D’ailleurs, trouveElem(int n) est bizarrement nommée, c’est plutôt quelque chose comme contientElem(int n)).

Merci beaucoup pour vos conseils !