IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Ajout dans les arbres binaires de recherche


Sujet :

Algorithmes et structures de données

  1. #1
    chouki
    Invité(e)
    Par défaut Ajout dans les arbres binaires de recherche
    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 java : 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
     
    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));
    	}
    }
    Dernière modification par pseudocode ; 19/12/2008 à 23h15. Motif: indentation du code

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    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).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    chouki
    Invité(e)
    Par défaut
    Toujours le méme resultat , quand je fais le debug il parcours correctement , j'ai retiré le static mais toujours rien

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par chouki Voir le message
    Toujours le méme resultat , quand je fais le debug il parcours correctement , j'ai retiré le static mais toujours rien
    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 java : Sélectionner tout - Visualiser dans une fenêtre à part
    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 java : Sélectionner tout - Visualiser dans une fenêtre à part
    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;
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Suppression dans un arbre binaire de recherche
    Par allomona dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 06/12/2014, 09h51
  2. modifier une valeur dans un arbre binaire de recherche?
    Par paco_the_king dans le forum Langage
    Réponses: 2
    Dernier message: 04/02/2012, 21h26
  3. Algorithme de suppression d'un élément dans un arbre binaire de recherche
    Par mohsenuss91 dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 24/12/2011, 13h05
  4. Réponses: 2
    Dernier message: 07/12/2009, 12h43
  5. Suppression dans un arbre binaire de recherche
    Par zeine77 dans le forum Langage
    Réponses: 1
    Dernier message: 11/05/2007, 21h40

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo