Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1827 connectés 

  FORUM HardWare.fr
  Programmation
  Java

  [JAVA] Equivalence d'arbres

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[JAVA] Equivalence d'arbres

n°1937780
cbeyls
Hail to the King, Baby
Posté le 04-11-2009 à 18:33:54  profilanswer
 

Quand tu dis équivalence, tu veux dire égalité totale, les 2 arbres ayant une structure et des données identiques?
 
Si oui cela doit être un algorithme récursif dans ce style:
 

Code :
  1. boolean estEgal(Noeud noeud1, Noeud noeud2) {
  2.   if(noeud1 == null) {
  3.      return (noeud2 == null);
  4.   }
  5.   if(noeud2 == null) {
  6.      return false;
  7.   }
  8.   return (noeud1.valeur == noeud2.valeur) && estEgal(noeud1.filsGauche, noeud2.filsGauche) && estEgal(noeud1.filsDroit, noeud2.filsDroit);
  9. }


 
Et tu l'appelles en lui passant le noeud racine des deux arbres à comparer.

mood
Publicité
Posté le 04-11-2009 à 18:33:54  profilanswer
 

n°1937848
cbeyls
Hail to the King, Baby
Posté le 04-11-2009 à 23:01:22  profilanswer
 

OK mais ça ne répond pas à mes questions:
 
1) Comment ton arbre binaire représente-il ces formules? Que contiennent les feuilles?
2) Quelle est la définition de "équivalent"?

n°1937880
cbeyls
Hail to the King, Baby
Posté le 05-11-2009 à 07:26:44  profilanswer
 

Bizarre comme technique. Donc les noeuds contiennent des opérations et les feuilles contiennent des constantes. Déjà, ça autorise plusieurs représentations de la même formule. En fait cette représentation sous forme d'arbre binaire est plus adaptée aux NPI (notations polonaises inverses).
 
Pour moi deux arbres binaires équivalents ce sont deux arbres qui contiennent exactement les mêmes éléments, mais ça ne répond pas à ton énoncé (renvoyer true pour les représentation de E1 et E2)... tu devrais demander plus d'informations.

n°1938028
charly007
Posté le 05-11-2009 à 15:22:35  profilanswer
 

cbeyls a écrit :

Bizarre comme technique. Donc les noeuds contiennent des opérations et les feuilles contiennent des constantes. Déjà, ça autorise plusieurs représentations de la même formule.


Ce n'est pas bizarre, j'ai appris la même représentation.

cbeyls a écrit :

En fait cette représentation sous forme d'arbre binaire est plus adaptée aux NPI (notations polonaises inverses).


C'est le parcours de l'arbre (préfixe, infixe, postfixe) qui engendrera la notation.
 
Concernant l'équivalence (égalité ?) tu trouveras peut-être des informations ici :
http://web2.uqat.ca/lerene/Webcour [...] 0-3405.pdf


Message édité par charly007 le 05-11-2009 à 15:34:14
n°1938145
cbeyls
Hail to the King, Baby
Posté le 05-11-2009 à 21:20:09  profilanswer
 

D'accord mais comme c'est un arbre binaire, la représentation d'un arbre bien précis en parcours inordre gauche ne peut pas être, par exemple:
 
A+B+C
 
Mais devrait être:
 
A+(B+C)
 
ou  
 
(A+B)+C.
 
Or dans son énoncé il a des expressions qui contiennent des additions de plus de 2 termes ou des multiplications de plus de 2 facteurs, sans parenthèses, ce qui fait qu'on peut représenter ces expressions par différents arbres binaires.
 
Dans ton document PDF ils parlent d'égalité de 2 arbres et la décrivent de la même façon que moi, donc si c'est bien ça la définition d'équivalence, l'algorithme que j'ai écrit est correct. Il faut évidemment l'adapter pour que la méthode puisse être appelée sur un noeud, avec le deuxième noeud passé en paramètre.

n°1938446
cbeyls
Hail to the King, Baby
Posté le 06-11-2009 à 16:57:51  profilanswer
 

Je n'ai jamais entendu parler d'un tel algorithme, il faudrait commencer à factoriser les membres de l'arbre, ça doit être super compliqué (à supposer que ça soit possible bien sûr).


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Java

  [JAVA] Equivalence d'arbres

 

Sujets relatifs
Afficher mon image (php/java)calculatrice flottante en java
MSN sous javaexpression reguliere java / ant
[Java] binding objet JAVA -> XML pour Datasource GWTDebutant Struts2 - Eclipse for Java EE ou Lomboz ?
Interop C# - Java via Com4jInterop C# - Java via Com4j
Ecrire un client qui se connecte a une socket & java.nio[JAVA] Random dans un pattern
Plus de sujets relatifs à : [JAVA] Equivalence d'arbres


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR