Version imprimable
Bonjour,
Malgré toute mes recherches sur différents cours sur les arbres binaires il y a certaines fonctions que j'arrive pas à trouver.Les fonctions basiques tel que définir la taille de l'arbre,chercher l'occurrence d'une valeur ou bien la trouver la valeur max sont facile à trouver et comprendre mais des fonctions comme par exemple définir si un arbre binaire est symétrique sont introuvables.Est-ce que vous avez des tuyaux la dessus?
Une fonction "compliquée" sur un arbre binaire est souvent un agrégat de fonctions "simples".
Exprime ce que représente la symétrie dans un arbre binaire et tente de découper la fonction en différents traitements, tu vas retomber sur des fonctions que tu connais.
Exactement! ^^Citation:
Envoyé par dinobogan
Pour faire simple, tu dois découper ton problème en sous problèmes.
Tu as de la chance, il s’agit d’un arbre binaire ^^. Et même si ce n’était pas un arbre binaire, tu peux transformer n’importe quel arbre en arbre binaire pour simplifier ton problème (bref ce n’est pas le sujet ^^).
Un arbre symétrique est un arbre de la forme :
Ou bien :Code:
2
3
4
Donc tu n'as plus qu'à faire une fonction simple qui prend un arbre en paramètre et qui regarde si ses deux fils sont identiques ^^.Code:
2
3
4
Après une plus grosse fonction va englober celle là, etc... ^^
As-tu cherché une implémentation pour voir comment celle-ci est réalisé ?Citation:
Envoyé par Caidriq
Sans allez très loin (google : binary tree search python ):
http://www.laurentluce.com/posts/bin...ary-in-python/
Tu peux remplacer python par un autre langage, même avec Haskell il y a des résultats correctes...
Cordialement,
Patrick Kolodziejczyk.
Bonjour,
Comme le type arbre est une structure de donnée récursive tu as souvent intérêt à penser récursivement. Dans ton exemple d'arbre binaire symétrique tu pars de la définition :
un arbre binaire A est symétrique ssi :
- A est un arbre vide
- ou si son fils gauche et son fils droit sont miroirs l'un de l'autre
Il te faut ensuite trouver une expression pour «miroir» ...
deux arbres binaires A et B sont miroirs l'un de l'autre ssi :
- A et B sont tous les deux des arbres binaires vides
- ou, ni A ni B ne sont des arbres binaires vides et le fils gauche de l'un est le miroir du fils droit de l'autre
Penser récursivement sur les arbres binaires consiste donc en général à dégager une propriété récursive sur les fils et à ne pas oublier les conditions d'arrêts (arbre vide, feuille, ...).
Bonjour :coucou:
Ce serait bien de s'appliquer à soi-même les conseils. Ta définition n'a pas de condition d'arrêt.Citation:
Penser (...) à ne pas oublier les conditions d'arrêts
Ben justement, tu ne parles pas des feuilles (arbre avec 1 branche). Par contre tu parles des arbres vides et des arbres à 2 branches.Citation:
(arbre vide, feuille, ...)
En plus, ta définition est redondante. Et elle déplace de "symétrique" vers "miroir", ce qui ne fait pas avancer.
Bonjour,Citation:
Envoyé par Flodelarab
Une feuille est un arbre dont le fils gauche et le fils droit sont des arbres vides et non pas un arbre à une branche. On pourrait compliquer les définitions en y ajoutant des conditions d'arrêt supplémentaires pour éventuellement éviter une descente récursive ...
Mes définitions me semblent tout à fait correctes.
«symétrique» est une propriété définie sur un arbre, une fonction qui prend un arbre en argument et qui renvoie un booléen. Elle ne renvoie vrai soit si l'arbre passé en argument est un arbre vide soit le résultat de la fonction miroir appliquée à ses deux fils. Il n'y a pas de récursivité ici, et si tu prends le temps d'essayer cela sur une feuille tu verras que cela fonctionne parfaitement.
«miroir» est une relation liant deux arbres, une fonction qui prend deux arbres en arguments et qui renvoie un booléen. Cette fonction s'implémente élégamment de manière récursive. Elle ne renvoie vrai que dans deux cas : soit les deux arguments sont des arbres vides, soit aucun des deux ne l'est et dans ce cas il faut que le fils gauche de l'un soit le miroir du fils droit de l'autre. Dans tous les autres cas cette fonction renvoie faux. Cela fonctionne correctement pour les feuilles, tu pourras t'en rendre compte facilement en essayant de le faire manuellement.
Tu t'aperçois également que ces deux fonctions ne font pas du tout la même chose et suivent simplement une définition.
En disant tout cela, je pense que le primo postant pourra aisément créer les algo correspondant et appliquer cela à d'autres problèmes sur les arbres.
Et bien merci,je sais pas si je vais y arriver mais ça me fais bien avancer en tout cas!