Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Parcours d'arbre : inordre, preordre, postordre
Il y a trois facons classiques de parcourir un arbre binaire. Imagine que tu visites une maison a trois etages. Tu peux :
1. Parcours inordre (gauche, racine, droite) : tu visites d'abord tout le cote gauche, puis la piece centrale, puis le cote droit. Pour un BST, ca donne les valeurs triees.
2. Parcours preordre (racine, gauche, droite) : tu commences par la piece centrale, puis le cote gauche, puis le droit. C'est utile pour copier un arbre.
3. Parcours postordre (gauche, droite, racine) : tu visites d'abord les enfants, puis le parent. C'est utile pour supprimer un arbre.
Chaque fonction prend une racine et retourne une liste Python des valeurs dans l'ordre du parcours.
Exemple avec un BST construit avec [5, 3, 7, 1, 4] : inordre donne [1, 3, 4, 5, 7] preordre donne [5, 3, 1, 4, 7] postordre donne [1, 4, 3, 7, 5]
Tests (2/4)
Inordre trie
racine = None
for v in [5, 3, 7, 1, 4]:
racine = insérer(racine, v)
assert inordre(racine) == [1, 3, 4, 5, 7]
Preordre
racine = None
for v in [5, 3, 7]:
racine = insérer(racine, v)
assert preordre(racine) == [5, 3, 7]
+ 0 tests cachés
Indices (3 disponibles)
Solution officielle
class Node:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def inserer(racine, valeur):
if racine is None:
return Node(valeur)
if valeur < racine.valeur:
racine.gauche = insérer(racine.gauche, valeur)
else:
racine.droite = insérer(racine.droite, valeur)
return racine
def inordre(racine):
if racine is None:
return []
return inordre(racine.gauche) + [racine.valeur] + inordre(racine.droite)
def preordre(racine):
if racine is None:
return []
return [racine.valeur] + preordre(racine.gauche) + preordre(racine.droite)
def postordre(racine):
if racine is None:
return []
return postordre(racine.gauche) + postordre(racine.droite) + [racine.valeur]