Arbre Binaire
Freaks
-
Freaks -
Freaks -
Bonjour,
J'essaye de faire un programme en Scheme, qui me permet de tester si deux arbres binaires ont la même forme ou non. J'ai réussi à faire un programme qui me permettait de tester si deux arbres binaires étaient égaux en utilisant l'étiquette.
J'aimerai avoir de l'aide pour ce programme, celui qui teste si deux arbres binaires ont la même forme ou non.
Merci d'avance.
Freaks.
J'essaye de faire un programme en Scheme, qui me permet de tester si deux arbres binaires ont la même forme ou non. J'ai réussi à faire un programme qui me permettait de tester si deux arbres binaires étaient égaux en utilisant l'étiquette.
J'aimerai avoir de l'aide pour ce programme, celui qui teste si deux arbres binaires ont la même forme ou non.
Merci d'avance.
Freaks.
A voir également:
- Arbre Binaire
- Binaire - Guide
- Arbre généalogique famille michelin - Télécharger - Généalogie
- Editeur binaire - Télécharger - Édition & Programmation
- Ouvrir fichier binaire - Guide
- Arbre qui parle dessin animé ✓ - Forum Cinéma / Télé
4 réponses
Principe de récursion sur les arbres :
Si deux arbres sont vides, ils ont la même forme.
Si l'un des deux est vide, et pas l'autre, ils n'ont pas la même forme.
Sinon, ils ont la même forme quand leurs sous-arbres ont la même forme.
Si deux arbres sont vides, ils ont la même forme.
Si l'un des deux est vide, et pas l'autre, ils n'ont pas la même forme.
Sinon, ils ont la même forme quand leurs sous-arbres ont la même forme.
KX
Messages postés
19031
Statut
Modérateur
3 020
C'est le même principe que l'égalité des arbres, sauf que tu ne compares pas les "étiquettes"
Mon programme sur l'égalité de deux arbres binaires est:
(define (ab-egal? B1 B2)
(if (and (ab-noeud? B1)(ab-noeud? B2))
(if (equal? (ab-etiquette B1)(ab-etiquette B2))
(if (ab-egal? (ab-droit B1)(ab-droit B2))
(ab-egal? (ab-gauche B1)(ab-gauche B2))
#f)
#f)
#t))
Mais je vois pas comment écrire le programme pour voir si ils ont même forme...
(define (ab-egal? B1 B2)
(if (and (ab-noeud? B1)(ab-noeud? B2))
(if (equal? (ab-etiquette B1)(ab-etiquette B2))
(if (ab-egal? (ab-droit B1)(ab-droit B2))
(ab-egal? (ab-gauche B1)(ab-gauche B2))
#f)
#f)
#t))
Mais je vois pas comment écrire le programme pour voir si ils ont même forme...
Je ne sais pas trop à quoi sert ab-noeud? mais si ça test si un arbre est non-vide, il te manque un cas, en effet, si B1 ou B2 est vide, tu arrives sur #t, or si un des deux arbres est forcément vide, l'autre ne l'est pas forcément auquel cas les deux arbres ne sont pas égaux.
Sinon, quand ab-egal? sera correct, il te suffira d'enlever le test d'égalité des étiquettes pour avoir ce que tu veux, car finalement les deux arbres ont la même forme s'ils sont égaux quand on "efface" toutes les valeurs qu'il contient.
Remarque : ces deux codes sont équivalents et permettrai d'enlever des if à ton code.
Sinon, quand ab-egal? sera correct, il te suffira d'enlever le test d'égalité des étiquettes pour avoir ce que tu veux, car finalement les deux arbres ont la même forme s'ils sont égaux quand on "efface" toutes les valeurs qu'il contient.
Remarque : ces deux codes sont équivalents et permettrai d'enlever des if à ton code.
(if (condition_booleenne) calcul_booleen #f) (and condition_booleenne calcul_booleen)
Oui effectivement ab-noeud? teste si un arbre est non-vide.
C'est vraie que j'ai pas mis le cas où, si un des deux arbres est non vide et l'autre l'est, ils ne sont pas égaux...
Par contre, j'ai déjà essayer juste d'enlever le teste d'égalité des étiquettes mais quand je fais un jeux de test avec deux arbres qui ont pas la même forme, ça me renvoie #t alors qu'il devrait me renvoyait #f :s
C'est vraie que j'ai pas mis le cas où, si un des deux arbres est non vide et l'autre l'est, ils ne sont pas égaux...
Par contre, j'ai déjà essayer juste d'enlever le teste d'égalité des étiquettes mais quand je fais un jeux de test avec deux arbres qui ont pas la même forme, ça me renvoie #t alors qu'il devrait me renvoyait #f :s
