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

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

Votre réponse

5 réponses

Meilleure réponse
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
- 12 nov. 2004 à 17:33
3
Merci
Parfait... tu veux dire équilibré? Si c'est ca je vois pas ce qui est compliqué

Merci vecchio56 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 94 internautes ce mois-ci

Commenter la réponse de vecchio56
Meilleure réponse
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Dernière intervention
23 janvier 2006
- 12 nov. 2004 à 18:41
3
Merci
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.

Merci MetalDwarf 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 94 internautes ce mois-ci

Commenter la réponse de MetalDwarf
Meilleure réponse
tapas64
Messages postés
33
Date d'inscription
vendredi 27 février 2004
Dernière intervention
14 novembre 2004
- 14 nov. 2004 à 14:30
3
Merci
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

Merci tapas64 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 94 internautes ce mois-ci

Commenter la réponse de tapas64
kossistus
Messages postés
2
Date d'inscription
lundi 24 février 2003
Dernière intervention
14 février 2006
- 14 févr. 2006 à 13:24
0
Merci
kossistus
Commenter la réponse de kossistus
cs_roolio
Messages postés
2
Date d'inscription
jeudi 17 novembre 2005
Dernière intervention
10 mars 2006
- 10 mars 2006 à 14:45
0
Merci

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.