Reconstruction d'après les parcours préfixe et infixe
Type d'arbre binaire particulier
Dans cet exercice, on considère des arbres binaires dont les étiquettes sont distinctes et immuables.
Quitte à créer une liste des étiquettes et un dictionnaire associant chaque étiquette à son indice, on peut supposer que les étiquettes sont les entiers de 0 à n - 1, où n est la taille de l'arbre.
- Objectif
- On donne le parcours préfixe et infixe, retrouver l'arbre !
Prérequis
Il vaut mieux avoir fait avant de nombreux exercices débranchés sur ce thème.
Exemple
graph TB
classDef Nil stroke:none,fill:none,color:none;
R("2")
Rg("4")
R --- Rg
Rd("5")
R --- Rd
Rgg("3")
Rg --- Rgg
Rgd(" ")
Rg -.- Rgd:::Nil
Rdg("1")
Rd --- Rdg
Rdd("6")
Rd --- Rdd
Rggg(" ")
Rgg -.- Rggg:::Nil
Rggd(" ")
Rgg -.- Rggd:::Nil
Rdgg("0")
Rdg --- Rdgg
Rdgd(" ")
Rdg -.- Rdgd:::Nil
Rddg(" ")
Rdd -.- Rddg:::Nil
Rddd(" ")
Rdd -.- Rddd:::Nil
Rdggg(" ")
Rdgg -.- Rdggg:::Nil
Rdggd(" ")
Rdgg -.- Rdggd:::Nil- Parcours préfixe :
[2, 4, 3, 5, 1, 0, 6] - Parcours infixe :
[3, 4, 2, 0, 1, 5, 6]
On souhaite reconstruire l'arbre donné à l'aide de la classe Noeud.
ab = Noeud(
2,
Noeud(
4,
Noeud(3),
None
),
Noeud(
5,
Noeud(
1,
Noeud(0),
None
),
Noeud(6),
)
)
Exercice
Coder une fonction reconstruction qui prend en paramètres deux listes : préfixe puis infixe et qui renvoie l'arbre binaire associé aux deux parcours donnés.
On garantit que les deux listes sont de même taille, composées des entiers de 0 à n - 1 où n est la taille de l'arbre binaire à reconstruire. On garantit également que ces listes permettent effectivement une reconstruction.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)