Reconstruction d'un arbre binaire ABR
Fermé
SlimJ
-
20 août 2015 à 00:42
lefilsdelaterre Messages postés 11 Date d'inscription vendredi 21 août 2015 Statut Membre Dernière intervention 27 août 2015 - 22 août 2015 à 11:17
lefilsdelaterre Messages postés 11 Date d'inscription vendredi 21 août 2015 Statut Membre Dernière intervention 27 août 2015 - 22 août 2015 à 11:17
A voir également:
- Reconstruction d'un arbre binaire ABR
- Codage binaire - Guide
- Arbre généalogique famille michelin - Télécharger - Généalogie
- Alphabet binaire ✓ - Forum Programmation
- Réponse binaire - Forum Bases de données
- Lire un fichier binaire avec notepad++ - Forum Téléchargement
1 réponse
lefilsdelaterre
Messages postés
11
Date d'inscription
vendredi 21 août 2015
Statut
Membre
Dernière intervention
27 août 2015
1
22 août 2015 à 11:17
22 août 2015 à 11:17
Bonjour,
À mon avis, la principale question n'est pas tellement le choix du parcours. Il faudrait connaître les règles exactes de ton arbre, pour savoir quelles ambiguïtés pourraient subsister si on stockait simplement par exemple :
20
15
9
2
1
12
7
25
21
etc...
Imaginons que ceci soit un parcours préfixe, avec la seule règle que le fils de gauche soit de valeur inférieur au parent, et celui de droite de valeur supérieure. Alors il n'y a aucune ambiguïté jusqu'à 1. Mais le 12 ?
Si c'est toute la partie de gauche qui doit avoir des valeurs inférieures, et la partie de droite des valeurs supérieures, alors là c'est plus simple et le 12 est forcément le fils de droite de 9.
Si c'est supérieure ou égal et non strictement supérieur, c'est déjà plus compliqué. On peut imaginer le cas extrême où toutes les valeurs sont identiques.
Enfin, si l'arbre est complet, alors il suffit de savoir quel type de parcours pour reconstruire.
À mon avis, la principale question n'est pas tellement le choix du parcours. Il faudrait connaître les règles exactes de ton arbre, pour savoir quelles ambiguïtés pourraient subsister si on stockait simplement par exemple :
20
15
9
2
1
12
7
25
21
etc...
Imaginons que ceci soit un parcours préfixe, avec la seule règle que le fils de gauche soit de valeur inférieur au parent, et celui de droite de valeur supérieure. Alors il n'y a aucune ambiguïté jusqu'à 1. Mais le 12 ?
Si c'est toute la partie de gauche qui doit avoir des valeurs inférieures, et la partie de droite des valeurs supérieures, alors là c'est plus simple et le 12 est forcément le fils de droite de 9.
Si c'est supérieure ou égal et non strictement supérieur, c'est déjà plus compliqué. On peut imaginer le cas extrême où toutes les valeurs sont identiques.
Enfin, si l'arbre est complet, alors il suffit de savoir quel type de parcours pour reconstruire.
