Algorithme de test sur arbre binaire parfait [Résolu]

tapas64 33 Messages postés vendredi 27 février 2004Date d'inscription 14 novembre 2004 Dernière intervention - 12 nov. 2004 à 16:42 - Dernière réponse : cs_roolio 2 Messages postés jeudi 17 novembre 2005Date d'inscription 10 mars 2006 Dernière intervention
- 10 mars 2006 à 14:45
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
Afficher la suite 

5 réponses

Répondre au sujet
vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 12 nov. 2004 à 17:33
+3
Utile
Parfait... tu veux dire équilibré? Si c'est ca je vois pas ce qui est compliqué
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de vecchio56
MetalDwarf 241 Messages postés mardi 29 octobre 2002Date d'inscription 23 janvier 2006 Dernière intervention - 12 nov. 2004 à 18:41
+3
Utile
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.
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de MetalDwarf
tapas64 33 Messages postés vendredi 27 février 2004Date d'inscription 14 novembre 2004 Dernière intervention - 14 nov. 2004 à 14:30
+3
Utile
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
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de tapas64
kossistus 2 Messages postés lundi 24 février 2003Date d'inscription 14 février 2006 Dernière intervention - 14 févr. 2006 à 13:24
0
Utile
kossistus
Commenter la réponse de kossistus
cs_roolio 2 Messages postés jeudi 17 novembre 2005Date d'inscription 10 mars 2006 Dernière intervention - 10 mars 2006 à 14:45
0
Utile

Commenter la réponse de cs_roolio

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.