Bonsoir,
En ayant 2 listes de nœuds selon 2 parcours différents d'un arbre binaire, est-il possible de reconstruire l'arbre initial? Si oui, quelles sont les paires de parcours ou cette reconstruction est possible.
Version imprimable
Bonsoir,
En ayant 2 listes de nœuds selon 2 parcours différents d'un arbre binaire, est-il possible de reconstruire l'arbre initial? Si oui, quelles sont les paires de parcours ou cette reconstruction est possible.
Dans l'absolu je te dirai non, sauf si ton arbre possède un seul niveau.
Si tu as 2 niveau, donc 4 parcours possible, en ayant seulement le listing de 2 parcours tu obtient que la moité de l'arbre.
Maintenant si tu augmentes le nombre de niveaux tu auras une partie de ton arbre encore plus réduite..
:salut:
Autre cas particulier intéressant : l'arbre binaire complet, aussi appelé tas, un arbre binaire dont chaque nœud a un degré deux (exactement deux enfants) ou est une feuille, qui peut s'implémenter avec un vecteur (voir https://fr.wikipedia.org/wiki/Tas_binaire).
:google: propose une solution à ce problème, par ailleurs, mais uniquement dans le cas d'arbres binaires de recherche (soit avec un ordre dans les nœuds de l'arbre).