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

Langage Java Discussion :

somme des noeuds d'un arbre binaire


Sujet :

Langage Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2007
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2007
    Messages : 4
    Par défaut somme des noeuds d'un arbre binaire
    Bonjour,
    je dois écrire une fonction récursive static int somme(Arbin<Integer> a ) qui calcule et retourne la somme des valeurs des nœuds de l’arbre binaire a qui sont fils gauches d’un nœud de a. Par exemple la somme des noeuds en gras sur cet arbre:

    je galère!!
    merci d'avance pour tout...

    voici la classe Arbin:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     public abstract class Arbin<T> {
        public abstract T racine();
        public abstract Arbin<T> ad();    //sous-arbre droit
        public abstract Arbin<T> ag();    //sous-arbre gauche
        public abstract boolean estVide(); }

  2. #2
    Membre éprouvé
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Janvier 2007
    Messages : 121
    Par défaut
    Quelque chose du genre...

    Code : 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
     
    public abstract class ArBin<T> {
    	public abstract T racine();
    	public abstract ArBin<T> ad(); //sous-arbre droit
    	public abstract ArBin<T> ag(); //sous-arbre gauche
    	public abstract boolean estVide(); 
     
     
    	public abstract T zero(); 
    	public abstract T somme(T n1,T n2); 
     
    	public T sommeGauche(ArBin<T> g) {
    		if (g == null) return zero(); // Est vide à gauche
    		T s = g.racine(); 
    		s =	somme(s, sommeGauche(g.ag()));
    		s = somme(s, sommeDroite(g.ad()));
    		return s;
    	}
     
    	public T sommeDroite(ArBin<T> d) {
    		if (d == null) return zero(); // Est vide à droite
    		return somme(sommeGauche(d.ag()),sommeDroite(d.ad()));
    	}
     
     
    }

    Il faut définir zero() et somme(T,T)
    Puis appeler sommeDroite()...

  3. #3
    Membre expérimenté
    Inscrit en
    Mai 2007
    Messages
    335
    Détails du profil
    Informations forums :
    Inscription : Mai 2007
    Messages : 335
    Par défaut
    C'est une fonction statique, pas besoin de généricité avec un fonction zéro etc.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    public static int somme(Arbin<Integer> a){
    if(a==null) return 0;
    return racine+somme(a.ag)+somme(a.ad));
    }

  4. #4
    Membre éprouvé
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Janvier 2007
    Messages : 121
    Par défaut
    D'accord, deltree, mais il ne faut cumuler que les racines de gauche...
    Avec ton code celà donne :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static int somme(Arbin<Integer> a){
    if(a==null) return 0;
    return racineGauche(a.ag) + somme(a.ag) + somme(a.ad));
    }
    
    public static int racineGauche(Arbin<Integer> a){
    if(a==null) return 0;
    return a.racine;
    }

  5. #5
    Membre expérimenté
    Inscrit en
    Mai 2007
    Messages
    335
    Détails du profil
    Informations forums :
    Inscription : Mai 2007
    Messages : 335
    Par défaut
    ah oui, j'ai mal lu l'énoncé
    et j'avais oublié aussi le a.racine.

    par contre là tu va sur encore le fils droit, il faut enlever le "+somme(a.ad)"

    il fallait bien laisser un peu de travail à l'auteur du topic

  6. #6
    Membre éprouvé
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Janvier 2007
    Messages : 121
    Par défaut
    Non deltree...
    Il faut aussi cumuler réccursivement les racine gauches de la sous-branche de droite.

    Le code peut être encore plus court:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    public static int somme(Arbin<Integer> a){
    if(a==null) return 0;
    return (a.ag==null ? 0:a.ag.racine) + somme(a.ag) + somme(a.ad));
    }

Discussions similaires

  1. Echange des noeuds d'un Arbre de Huffman
    Par tompote dans le forum C
    Réponses: 2
    Dernier message: 21/01/2011, 10h26
  2. [AC-2003] Créer des Noeud dans un arbre
    Par sassene dans le forum IHM
    Réponses: 0
    Dernier message: 01/07/2010, 10h41
  3. [Xpath]somme des noeuds et soustraction
    Par lenoil dans le forum XSL/XSLT/XPATH
    Réponses: 5
    Dernier message: 13/05/2010, 23h00
  4. Réponses: 2
    Dernier message: 07/12/2009, 11h43
  5. edition ou modification des noeuds d'une arbre JTREE
    Par foufoulina2007 dans le forum Composants
    Réponses: 1
    Dernier message: 30/11/2007, 21h52

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