Bonjour,
je cherche un algorithme qui me permettrait de tester si un arbre binaire est parfait. Je n'ai rien trouvé en surfant sur le net ou e essayant seule. Est-ce que quelqu'un pourrait m'aider svp, merci.

tapas64

Réponse acceptée !
Parfait... tu veux dire équilibré? Si c'est ca je vois pas ce qui est compliqué

Réponse acceptée !
Si c est simplement tester si l arbre est equilibre c est pas tres dur en effet. Il suffit de tester recursivement la profondeur des deux fils de l arbre et de renvoyer un booleen (c est un peu brutal, et il est plus intelligent de renvoyer aussi la profondeur du fils en meme temps pour diminuer la complexite).
Si c est pour verifier si un arbre est bien un arbre binaire de recherche par exemple c est un tout petit peu plus complique, mais pas trop quand meme.

Réponse acceptée !
En fait on nous demande d'implémenter 2 fonctions sur l'arbre binaire qui sont est_complet et est_parfait, et on dispose déjà de la fonction qui teste si l'arbre est équilibré.
Ici, arbre parfait veut dire arbre quasi-complet, cad que l'arbre est complètement rempli à l'exception de l'avant dernier niveau. Cependant les feuilles représentant le dernier niveau sont "le plus à gauche possible".



tapas64

kossistus