Recherche dans ABR

Version imprimable

Recherche dans ABR

Salut à touus !
Je dois faire une méthode recherche(int n) dans un arbre binaire de recherche , qui retourne le sous-arbre de this dont la racine a pour valeur, n. J'ai fait ça :

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
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Noeud {
   private int etiquette;
   private Noeud gauche;
   private Noeud droit;
 
   public Noeud(int etiquette, Noeud gauche, Noeud droit) {
      this.etiquette = etiquette;
      this.gauche = gauche;
      this.droit = droit;
   }
 
   public Noeud(int etiquette) {
      this(etiquette,null,null);
   }
 
   public Noeud recherche(int x) {
      if(this.etiquette == x) {
         return this;
      }
      if(this.etiquette <= x) {
         if(this.droit != null) {  
            if(this.droit.etiquette == x) {
               return this.droit;
            }
            else this.droit.recherche(x);        
         }    
      }
      if(this.etiquette >= x) {
         if(this.gauche != null) {  
            if(this.gauche.etiquette == x) {
               return this.gauche;
            }
            else this.gauche.recherche(x);        
         }
      }
      return null;
   }
}

Apparemment ça fonctionne mais quand je veux rechercher une feuille dans l'abre, j'ai une erreur du style nullpointer, pourquoi, ai-je oublier des cas ?
voila merci :mrgreen:

Bonjour,
il manque des return:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
if(this.etiquette <= x) {
         if(this.droit != null) {  
            if(this.droit.etiquette == x) {
               return this.droit;
            }
            else return this.droit.recherche(x);        //ICI
         }    
      }
      if(this.etiquette >= x) {
         if(this.gauche != null) {  
            if(this.gauche.etiquette == x) {
               return this.gauche;
            }
            else return this.gauche.recherche(x);        //ET LA
         }
      }

Ça compile parce que c'est syntaxiquement correct mais ça ne fait pas ce que tu voudrais.
D'ailleurs tu peux le simplifier avec le même résultat en:

Code:

1
2
3
4
5
6
7
8
9
10
11
 
if(this.etiquette <= x) {
         if(this.droit != null) {  
            return this.droit.recherche(x);
         }    
      }
else if(this.etiquette > x) {
         if(this.gauche != null) {  
            return this.gauche.recherche(x);
         }
      }

Ceci dit ça ne provoquerai pas de NullPointerException.
Le mieux serait de donner le code qui lance tout ça, et surtout de donner la stacktrace complète de l'erreur (en gros le numéro de ligne où survient l'erreur).

31/03/2014, 19h59
tamerla

Merci de ton intervention . Le code que tu as mis n'est pas tout a fait ce que je veux vu que je dois retourner un sous - arbre qui a pour racine l'argument, avec ses fils, pas juste la valeur du noeud en argument !
Mon truc a l'air de marcher, je crois que le probleme est au niveau du dernier return, je ne sais ce qu'il faut retourner (l'erreur nullpointer vient de là, j'avais mis return null à la fin et quand je mettais la valeur d'une feuille en argument, il m'affichait cette erreur)

Probleme résolu, je suis tete en l'air parfois :mrgreen:

Code:

1
2
3
4
5
6
7
8
9
10
   public Noeud recherche(int x) {
      if(this.etiquette == x) return this;
      else if(this.etiquette <= x) {
         if(this.droit != null) {  
            return this.droit.recherche(x);
         }    
      }
      return this.gauche.recherche(x);
   }
}