Java

somme des noeuds d'un arbre

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : somme des noeuds d'un arbre

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

Publicité

Taz

bisounours-codeur

91, facile

bibi182

tu m'aides pas trop...

masklinn

í dag viðrar vel til loftárása

En même temps, t'as pas posté de code, t'as pas posté la structure de l'arbre, t'as pas posté où tu bloquais exactement et tu nous a pas dit quelles pistes tu avais déjà explorées...

Donc il peut difficilement t'aider plus que ça, à part à la limite en te disant qu'un arbre ça s'explore récursivement.

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?

bibi182

Ben l'arbre c'est un arbre binaire quelconque...
et j'ai quelques pistes:

static int somme(Arbin<Integer> a ) {
if(!a.estVide()) {
return a.racine.intValue() + ag.somme(a.ag()); }
}
qu'en pensez-vous ?

masklinn

í dag viðrar vel til loftárása

J'en pense que j'ai oublié ma boule de crystal ce matin

bibi182

Code :

public Noeud<T> rac; //racine de l'arbre
protected static class Noeud<U>() {
public U val;
public Noeud<U> fg;
public Noeud<U> fd;
Noeud() {
this.val = null;
this.fg = null;
this.fd = null;
}
}
ArbinCh()
{
this.rac = null;
}
ArbinCh(T v)
{
this.rac = new Noeud();
this.rac.val = v;
}
ArbinCh(T v, Arbin<T> ag, Arbin<T> ad)
{
this.rac = new Noeud();
this.rac.val = v;
this.rac.fg = (ArbinCh) ag.rac;
this.rac.fd = (ArbinCh) ad.rac;
}
public ArbinCh<T> ag()
{
ArbinCh<T> res = new ArbinCh();
res.rac = this.rac.fg;
return res;
}
public ArbinCh<T> ad()
{
ArbinCh<T> res = new ArbinCh();
res.rac = this.rac.fd;
return res;
}
public boolean avide()
{
return this.rac == null;
}
public Noeud<T> racine()
{
return this.rac;
}
--------------------------------------------------------
public abstract class Arbin<T> {
public abstract T racine();
public abstract Arbin<T> ad();
public abstract Arbin<T> ag();
public abstract boolean estVide();
public abstract Arbin<T> initArbre(T v, Arbin<T> g, Arbin<T> d);
public abstract Arbin<T> initArbre();

masklinn

í dag viðrar vel til loftárása

Comment tu fais pour avoir besoin de 3 classes différentes pour un pauvre arbre [:petrus dei]

Et c'est quoi l'intérêt d'utiliser des noms aussi cryptique que 'ad' et 'ag', peur de s'user les doigts [:petrus dei]

Et pourquoi il en manque des bouts [:petrus dei]

Message édité par masklinn le 03-11-2007 à 20:05:23

bibi182

Code :

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

aidez-moi svp... c'est un arbre binaire équilibré (l'exemple n'était que pour vous montrez les noeuds que l'on cherchent)
si e est un Integer, alors e.intValue() donne la valeur de type int correspondante.
j'ai écris ça, est-ce que ça convient ?

Code :

static int somme(Arbin<Integer> a ) {
if(!a.estVide()) {
return a.racine().intValue() + ag.somme(a.ag()); }
}

Message édité par bibi182 le 03-11-2007 à 20:21:02

masklinn

í dag viðrar vel til loftárása

non

Publicité

bibi182

si tu dis non c'est que t'as une idée alors...
aide moi sinon passe ton chemin car tu ne fais que de me remballer

Message cité 1 fois

masklinn

í dag viðrar vel til loftárása

bibi182 a écrit :

si tu dis non c'est que t'as une idée alors...

oui

bibi182 a écrit :

aide moi sinon passe ton chemin car tu ne fais que de me remballer

Je t'ai déjà dit qu'un arbre ça s'explorait récursivement, et demandé pourquoi tu avais besoin de 3 classes pour construire un arbre d'entiers alors qu'une seule suffit [:spamafote]

bibi182

ben oui mais que proposes-tu comme code alors ?
j'ai appliqué ce que tu m'as dis mais ça ne convient toujours pas alors aide moi encore plus ?

Message cité 1 fois

masklinn

í dag viðrar vel til loftárása

bibi182 a écrit :

ben oui mais que proposes-tu comme code alors ?

Code :

data Tree a = Node (Tree a) a (Tree a) | None
              deriving Show
foldTree _ None init = init
foldTree f (Node left value right) init =
    f (Node left value right) (foldTree f left init) (foldTree f right init)

addLeft (Node None _ _) _ right = right
addLeft (Node (Node _ value _) _ _) left right = value + left + right

mais je suis pas persuadé que ça t'aide beaucoup

bibi182 a écrit :

j'ai appliqué ce que tu m'as dis

non

bibi182 a écrit :

mais ça ne convient toujours pas alors aide moi encore plus ?

je suggère que tu traces ce que ton code doit faire à la main et que tu te demandes ce dont tu as besoin à chaque étape.

bibi182

Code :

static int somme(Arbin<Integer> a)
{
int res;
if (a.estVide())
{
res = 0;
}
else
{
res = a.ag().intValue() + a.ad().ag().intValue() + somme(a.ag()) + somme(a.ad());
// 1ère feuille gauche + 1ère feuille g. du sous-arbre droit + récursivité pour appliquer à tout l'arbre
}
}

qu'en pensez-vous ?

masklinn

í dag viðrar vel til loftárása

Code :

a.ag().intValue()

Bien (si #intValue() renvoie la valeur stockée dans une node de ton arbre), mais il faudrait peut-être tester si tu as un ag().

Code :

a.ad().ag().intValue()

Non, ça c'est géré par les deux appels récursifs derrière, je vois pas ce que ça vient foutre ici

Code :

somme(a.ag()) + somme(a.ad())

bien

Message édité par masklinn le 04-11-2007 à 12:18:59

bibi182

Code :

static int somme(Arbin<Integer> a)
{
int res;
if (a.estVide())
{
res = 0;
}
else
{
if(!a.ag().estVide())
{
res = a.ag().intValue() + somme(a.ag()) + somme(a.ad());
}
else
{
res = 0;
}
}
return res;
}

#intValue() renvoie bien la valeur stockée dans un noeud de l'arbre

masklinn

í dag viðrar vel til loftárása

À part si tu es sûr que ton arbre est balancé, j'aurais séparé a.ag().intValue() et somme(a.ag()) + somme(a.ad()) (tu peux avoir un sous-arbre droit et pas de sous-arbre gauche).

Accessoirement, #estVide sert à quoi? À te dire si une node a une valeur? Ca a aussi un rapport avec les sous-arbres ou pas? Possible d'avoir son code?

bibi182

je ne vois ce que tu veux dire par

Citation :

séparé a.ag().intValue() et somme(a.ag()) + somme(a.ad())

pour #estVide(), c'est une fonction booléenne qui renvoie true si l'arbre est vide, false sinon. et elle peut s'appliquer aux sous-arbres

Message cité 1 fois
Message édité par bibi182 le 04-11-2007 à 14:08:56

masklinn

í dag viðrar vel til loftárása

bibi182 a écrit :

je ne vois ce que tu veux dire par

Citation :

séparé a.ag().intValue() et somme(a.ag()) + somme(a.ad())

pour #estVide(), c'est une fonction booléenne qui renvoie true si l'arbre est vide, false sinon. et elle peut s'appliquer aux sous-arbres

Code :

if(!a.ag().estVide()) {
    res = a.ag().intValue();
}
res += somme(a.ag()) + somme(a.ad());

bibi182

Code :

static int somme(Arbin<Integer> a)
{
int res;
if (a.estVide())
{
res = 0;
}
else
{
if(!a.ag().estVide())
{
res = a.ag().intValue();
}
res = res + somme(a.ag()) + somme(a.ad());
}
return res;
}

ça yé? dis moi que c'est bon stp... :ouch:

masklinn

í dag viðrar vel til loftárása

Teste le sur divers arbres, il n'y a que comme ça que tu sauras si ça a l'air bon [:petrus75]

bibi182

ok en tant cas un grand merci à toi!! :-*

Publicité

FORUM HardWare.fr

Programmation

Java

somme des noeuds d'un arbre

Sujets relatifs
Afficher un arbre	faire la somme des valeurs négatives dans une plage variable
Optimiser l'affichage d'un arbre/forum	Récupération des branches d'un arbre
Somme à plusieurs critère vba	somme sous vba
XSLT et noeuds vides en sortie (C# aussi)	[Excel] Mélange de somme.si et nb.si
[sql] somme d'un tableau sur les lignes	[DIVERS] Excel et somme de cellule sous conditions
Plus de sujets relatifs à : somme des noeuds d'un arbre

Page générée en 0.075 secondes