Bonjour à tous,

mon problème est le suivant: à partir d'une valeur a, je souhaite savoir si cette valeur apparaît dans un arbre binaire. J'ai donc une méthode avec en entrée la valeur a. Je souhaite ressortir un booléen de valeur true, si a apparaît. Voici mon code, en gros:

public boolean cherche(int a) {

     if ( this.getAttribut() == a) {
          return true;
     }

     if(this.getFG() != null) 
          this.getFG().cherche(a);
     }

     if(this.getFD() != null) 
          this.getFD().cherche(a);
     }

     return false;
}

Je vois où est mon problème: à la sortie de l'exécution au noeud qui correspond à la valeur a, la méthode retourne dans le noeud précédent, et reprend la valeur false.
Par contre, je ne sais pas comment l'implémenter en Java. J'ai essayé en enregistrant une variable globale, mais sans succès.

Si quelqu'un pouvez m'aider?
Merci.

Salut,

Tu peux par exemple trier ton arbre binaire en arbre binaire de recherche (si c'est pas déjà le cas), et ensuite l'algo est tout simple.

En voici un qui devrait alors marcher (avec un objet Noeud composé d'un élément, d'un fils gauche et d'un fils droit), et qui retourne null si l'élément n'est pas présent dans l'arbre, et le Noeud sinon :

private Noeud trouve( int valeur, Noeud noeud ) {
    while( noeud != null ) {
        if( valeur.compareTo( noeud.element ) < 0 )
        	noeud = noeud.filsGauche;
        else if( valeur.compareTo( noeud.element ) > 0 )
        	noeud = noeud.filsDroit;
        else
            return noeud;    // Trouvé
    }
    return null;         // Non trouvé
}

Et pour l'utiliser, un simple :

boolean existe = ( trouve(a, racine) != null );

Oui merci, c'est pas une mauvaise idée, mais mon arbre n'était pas encore trié au début.

Sinon, j'ai trouvé une solution, pour ce que ça pourrait intéresser:

public boolean cherche(int a) {

     if ( this.getAttribut() == a) {
          return true;
     }

     if(this.getFG() != null) {
          if (this.getFG().cherche(a)) {
                  return true;
          }
     }

     if(this.getFD() != null) {
          if (this.getFG().cherche(a)) {
                  return true;
          }
     }

     return false;
}

Et là, chaque boucle retourne true.

Merci.