Discussion :

[scary]

Bonjour,

Voila j'essaie depuis un moment de faire une fonction qui me dit si deux ABR sont équivalents ou non (c'est à dire si tout les éléments de l'arbre A sont exactement les mêmes dans l'arbre B). Le seul soucis est que ma fonction me renvoie les 3/4 du temps vrai alors que ça ne l'est pas. Voici ce que j'ai fais:

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
booleen Equivalent (arbre A, arbre B)
{
      if (!EstVide (A) && !EstVide (B))
      {
           if (A->val != B->val)
           {
                 return faux;
           }
           Equivalent (A->sag, B->sag);
           Equivalent (A->sad, B->sad);
 
           return vrai;
      }
 
      return faux;
}

booleen est une enumeration qui contient les valeurs vrai ou faux et EstVide est une fonction qui me dit si un arbre est vide ou non. Merci d'avance

[diogene]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
           Equivalent (A->sag, B->sag);
           Equivalent (A->sad, B->sad);

il faut utiliser les valeurs de retour de ces appels.


Le schéma de la fonction me semble être le suivant :

- SI A est vide ET B est vide, ils sont équivalents.
- SINON SI A est vide ET B n'est pas vide OU si A n'est pas vide ET B est vide, ils ne sont pas équivalents
-------- SINON SI A->val est égal à B->val ET A->sag est équivalent à B->sag ET A->sad est équivalent à B->sad, ils sont équivalents
---------------SINON ils ne sont pas équivalents

[scary]

En effet tu avais raison j'utilisais mal ma récurrence. Merci beaucoup