Discussion :

[bibi182]

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(); }

[rebel64]

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()...

[deltree]

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));
}

[rebel64]

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;
}

[deltree]

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

[rebel64]

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));
}

[deltree]

Ah c'est exact, merci.
j'ai enfin compris, tes solutions sont justes. J'ai une préférence pour la plus courte, c'est aussi simple à comprendre.