Bonjour,
 
Je dois réaliser un code en java qui test l'équivalence de deux arbres binaires.
Pour les cas triviaux (arbre de taille 0,1, ...) le code semble assez évident ...
Cependant lorsque la taille vient à augmenter, je n'arrive pas à déterminer un algorithme qui me renvoie des résultats correct.
Pourriez-vous m'aider à trouver cet algo pour que je puisse continuer à coder ?
Ou m'indiquer des liens ? Sur google je ne trouve pas vraiment ce que je souhaite en cherchant cet algo ...
 
Merci  

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:
 

boolean estEgal(Noeud noeud1, Noeud noeud2) {
   if(noeud1 == null) {
      return (noeud2 == null);
   }
   if(noeud2 == null) {
      return false;
   }
   return (noeud1.valeur == noeud2.valeur) && estEgal(noeud1.filsGauche, noeud2.filsGauche) && estEgal(noeud1.filsDroit, noeud2.filsDroit);
}

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

En fait j'ai une expression du genre
 
E1 = -(A+B)*(C+D)/(C-D)  
E2 = (A*C + A*D + B*C + B*D) / (D – C)
 
Je dois construire deux arbres avec, et créer une méthode qui détermine si les deux arbres sont équivalents.
Par exemple A1.estEquivalent(Arbre A2) doit renvoyer true dans ce cas là.
 
Merci !

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

Pour E1 = -(A+B)*(C+D)/(C-D) par exemple on a ça (désolé pour la mise en page, c'est capricieux ce truc) :

 
Et pour la définition justement ! Rien dans mon cours ! Sans parler de google ...

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.

C'est déjà fait mais je n'obtient rien.
AMHA le sujet est erroné/incohérent mais je voulais d'autres avis ...    
Merci
 
EDIT : Et si on développe tout en NPI tu crois que ça semble faisable ?

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

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

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.

Ce qui me gêne dans touts les algo que je trouve c'est que :

 
OR pour les 2 expressions, à la base 1ere racine n'est pas la même, donc 2 n'est pas vérifié, mais les arbres sont équivalents ...

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