Ajout dans les arbres binaires de recherche

Version imprimable

Bonjour, voila le code qui permet d'ajouter dans un ABR quand je rajoute un element ça marche pas, je teste par la fonction taille si le resultat augmente de 1 c'est que l'elt est ajouté

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
 
public class B {
 
	int val;
	B gauche;
	B droite;
 
	B(int i, B gauche, B droite){
		val=i;
		this.gauche=gauche;
		this.droite=droite;
	 }
 
	public static B ajouter(B a,int i){
		if (a==null)
			return new B(i,null,null);
 
		else if (i>a.val)
			return ajouter(a.droite,i);
		else
			return ajouter(a.gauche,i);
	}
 
	static int taille(B a){
		if(a==null)
			return 0;
		else
			return 1+taille(a.gauche)+taille(a.droite);
	}
 
	public static void main(String[] args) {
		B amina1= new B(12,null,null);
		ajouter(amina1,8);
		System.out.println (taille (amina1));
	}
}

19/12/2008, 22h19
pseudocode

Bonsoir,

Les attributs B.gauche et B.droite ne sont jamais modifiés, sauf dans le constructeur. Ils restent donc toujours avec les valeurs passées lors du new => ils sont toujours "null"

Je ne saurais trop te conseiller de NE PAS utiliser les "static" (à part pour le "main", bien sur). ;)
28/12/2008, 12h40
chouki

Toujours le méme resultat , quand je fais le debug il parcours correctement , j'ai retiré le static mais toujours rien :roll:

Citation:

Envoyé par chouki

Toujours le méme resultat , quand je fais le debug il parcours correctement , j'ai retiré le static mais toujours rien :roll:

Retirer le static c'est une chose, mais comme je te l'ai dit tu dois aussi affecter la valeur des attributs "gauche" et "droite".
Code:

1 2 3 4 5 6 7 8 9 10 11 public B ajouter(int i){ if (i>this.val) { if (this.droite!=null) return this.droite.ajouter(i); this.droite = new B(i,null,null); return this.droite; } else { if (this.gauche!=null) return this.gauche.ajouter(i); this.gauche = new B(i,null,null); return this.gauche; } }
Vu que c'est une récursion terminale, il serait plus avantageux en Java d'utiliser une boucle. Et également penser à ne pas stocker les doublons.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 public B ajouter(int i){ B b = this; while(b.val!=i) { if (i>b.val) { if (b.droite==null) b.droite=new B(i,null,null); b=b.droite; } else { if (b.gauche==null) b.gauche=new B(i,null,null); b=b.gauche; } } return b; }