Discussion :

[slim_java]

salut,
si on souhaite enregistrer un ABR dans un fichier séquentiel,
quel est le meilleur parcour(infixé , préfixé ou postfixé) a adopter lors de l'écriture de l'arbre afin de pouvoir la reconstruire par la suite ?

[ChipsAlaMenthe]

Le fait que ce soit un arbre binaire aide beaucoup ! ^^

Ensuite pour que ce soit plus simple à reconstituer, il faut inscrire dans le fichier toutes les feuilles vides de l’arbre, par exemple :



Ce sera plus simple pour reconstruire l’arbre.

Je pense sinon que le plus simple serait le parcours préfixé, voilà mon explication :

Si on ne tient pas compte des feuilles vides, le rendu du parcours préfixé donne ceci :
1, 2, 4, 5, 7, 8, 3, 6, 9.

Maintenant l’idée est d’inscrire les feuilles vides, ce qui donnera :
1, 2, 4, V, V, 5, 7, V, V, 8, V, V, 3, V, 6, 9, V.

Du coup, pour la reconstitution, dès que tu rencontres une feuille à gauche Vide, tu passes sur son frère de droite. Si le frère de droite n’est pas vide, alors tu descends dans sa hiérarchie, sinon ça veut dire que tu es arrivé à une feuille terminale et tu dois donc remonter dans la hiérarchie.

J'espère avoir été assez clair ^^.

[dinobogan]

Juste une précision sur la solution de ChipsAlaMenthe : l'ajout des noeuds vides est virtuel : tu ne vas pas réellement ajouter des noeuds vides dans ton arbre. Les noeuds vides sont des marqueurs pour savoir ou ajouter les données lors de la reconstruction.
Ces marqueurs sont indispensables si ton arbre n'est pas complet.

[picodev]

Bonjour,

Pour aider notre ami à construire sa solution …
Un parcours préfixe commence toujours par la racine.
Comme il s'agit d'un abr on sait que la liste de tous les nœuds plus petits que la racine sont le parcours préfixe de son sous arbre gauche et que la liste de tous les nœuds plus grands que la racine sont le parcours préfixe de son sous-arbre droit. Cela mène à un algorithme récursif pas forcément optimisé en O(n²), pas optimisé mais simple à implémenter.