somme des noeuds d'un arbre

somme des noeuds d'un arbre - Java - Programmation

Marsh Posté le 03-11-2007 à 16:20:46    

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:
http://images2.hiboox.com/images/4407/baqlsv5d.jpg
je galère!!
merci d'avance pour tout...

Reply

Marsh Posté le 03-11-2007 à 16:20:46   

Reply

Marsh Posté le 03-11-2007 à 17:16:45    

91, facile

Reply

Marsh Posté le 03-11-2007 à 18:09:47    

tu m'aides pas trop...

Reply

Marsh Posté le 03-11-2007 à 18:51:06    

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.


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 03-11-2007 à 19:15:43    

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 ?

Reply

Marsh Posté le 03-11-2007 à 19:24:05    

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


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 03-11-2007 à 19:47:20    

Code :
  1. public Noeud<T> rac; //racine de l'arbre
  3. protected static class Noeud<U>() {
  4. public U val;
  5. public Noeud<U> fg;
  6. public Noeud<U> fd;
  8.  Noeud() {
  9.  this.val = null;
  10.  this.fg = null;
  11.  this.fd = null;
  12.  }
  13. }
  15.     ArbinCh()
  16.     {
  17.         this.rac = null;
  18.     }
  20.     ArbinCh(T v)
  21.     {
  22.         this.rac = new Noeud();
  23.         this.rac.val = v;
  24.     }
  26.     ArbinCh(T v, Arbin<T> ag, Arbin<T> ad)
  27.     {
  28.         this.rac = new Noeud();
  29.         this.rac.val = v;
  30.         this.rac.fg = (ArbinCh) ag.rac;
  31.         this.rac.fd = (ArbinCh) ad.rac;
  32.     }
  34.     public ArbinCh<T> ag()
  35.     {
  36.         ArbinCh<T> res = new ArbinCh();
  37.         res.rac = this.rac.fg;
  38.         return res;
  39.     }
  41.     public ArbinCh<T> ad()
  42.     {
  43.         ArbinCh<T> res = new ArbinCh();
  44.         res.rac = this.rac.fd;
  45.         return res;
  46.     }
  48.     public boolean avide()
  49.     {
  50.         return this.rac == null;
  51.     }
  53.     public Noeud<T> racine()
  54.     {
  55.         return this.rac;
  56.     }
  58. --------------------------------------------------------
  60. public abstract class Arbin<T> {
  61.     public abstract T racine();
  62.     public abstract Arbin<T> ad();
  63.     public abstract Arbin<T> ag();
  64.     public abstract boolean estVide();
  65.     public abstract Arbin<T> initArbre(T v, Arbin<T> g, Arbin<T> d);
  66.     public abstract Arbin<T> initArbre();

Reply

Marsh Posté le 03-11-2007 à 20:05:09    

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

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 03-11-2007 à 20:16:55    

Code :
  1. public abstract class Arbin<T> {
  2.     public abstract T racine();
  3.     public abstract Arbin<T> ad();    //sous-arbre droit
  4.     public abstract Arbin<T> ag();    //sous-arbre gauche
  5.     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 :
  1. static int somme(Arbin<Integer> a ) {
  2. if(!a.estVide()) {
  3.       return a.racine().intValue() + ag.somme(a.ag()); }
  4. }


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

Marsh Posté le 03-11-2007 à 20:20:33    

non


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 03-11-2007 à 20:20:33   

Reply

Marsh Posté le 03-11-2007 à 20:31:23    

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
Reply

Marsh Posté le 03-11-2007 à 20:37:09    

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]


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 03-11-2007 à 20:43:48    

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
Reply

Marsh Posté le 03-11-2007 à 20:51:03    

bibi182 a écrit :

ben oui mais que proposes-tu comme code alors ?


Code :
  1. data Tree a = Node (Tree a) a (Tree a) | None 
  2.               deriving Show 
  3. foldTree _ None init = init 
  4. foldTree f (Node left value right) init = 
  5.     f (Node left value right) (foldTree f left init) (foldTree f right init) 
  6.  
  7. addLeft (Node None _ _) _ right = right 
  8. 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.


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 04-11-2007 à 11:03:30    

Code :
  1. static int somme(Arbin<Integer> a)
  2. {
  3.     int res;
  4.     if (a.estVide())
  5.     {
  6.         res = 0;
  7.     }
  8.     else
  9.     {
  10.         res = a.ag().intValue() + a.ad().ag().intValue() + somme(a.ag()) + somme(a.ad());
  11.       // 1ère feuille gauche + 1ère feuille g. du sous-arbre droit + récursivité pour appliquer à tout l'arbre
  12.     }
  13. }


 
qu'en pensez-vous ?

Reply

Marsh Posté le 04-11-2007 à 12:16:56    

Code :
  1. 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 :
  1. 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 :
  1. somme(a.ag()) + somme(a.ad())


bien


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

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 04-11-2007 à 13:27:34    

Code :
  1. static int somme(Arbin<Integer> a)
  2.       {
  3.          int res;
  4.          if (a.estVide())
  5.          {
  6.              res = 0;
  7.          }
  8.          else
  9.          {
  10.      if(!a.ag().estVide())
  11.      {
  12.                  res = a.ag().intValue() + somme(a.ag()) + somme(a.ad());
  13.      }
  14.      else
  15.      {
  16.          res = 0;
  17.      }
  18.          }
  19.  return res;
  20.       }


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

Reply

Marsh Posté le 04-11-2007 à 13:54:22    

À 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?


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 04-11-2007 à 14:06:08    

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
Reply

Marsh Posté le 04-11-2007 à 14:19:27    

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 :
  1. if(!a.ag().estVide()) {
  2.     res = a.ag().intValue();
  3. }
  4. res += somme(a.ag()) + somme(a.ad());


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 04-11-2007 à 14:28:38    

Code :
  1. static int somme(Arbin<Integer> a)
  2. {
  3.               int res;
  4.               if (a.estVide())
  5.               {
  6.                   res = 0;
  7.               }
  8.               else
  9.               {
  10.                   if(!a.ag().estVide())
  11.                   {
  12.                       res = a.ag().intValue();
  13.                   }
  14.                   res = res + somme(a.ag()) + somme(a.ad());
  15.               }
  16.               return res;
  17. }


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

Reply

Marsh Posté le 04-11-2007 à 14:41:02    

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


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 04-11-2007 à 14:44:08    

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

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed