Arbres Binaires — Parcours et Hauteur
Préfixe, infixe, postfixe, largeur
Enonce
Implémenter une classe Noeud puis les 5 fonctions suivantes qui renvoient une liste (ou un entier pour la hauteur) :
- prefixe(racine) — parcours préfixe (R, G, D)
- infixe(racine) — parcours infixe (G, R, D)
- postfixe(racine) — parcours postfixe (G, D, R)
- largeur(racine) — parcours en largeur (BFS itératif avec une file)
- hauteur(racine) — hauteur de l'arbre (−1 pour l'arbre vide)
Signature attendue
class Noeud:
def prefixe(racine) -> list:
def infixe(racine) -> list:
def postfixe(racine) -> list:
def largeur(racine) -> list:
def hauteur(racine) -> int:Exemples
prefixe(Noeud(1, Noeud(2, Noeud(4), Noeud(5)), Noeud(3)))→[1, 2, 4, 5, 3]hauteur(Noeud(1, Noeud(2, Noeud(4), Noeud(5)), Noeud(3)))→2
📖 Rappel de cours
Un arbre binaire est soit vide, soit un nœud possédant une valeur, un sous-arbre gauche et un sous-arbre droit (définition récursive).
Les 4 parcours :
- Préfixe (racine, G, D) — utile pour sérialiser un arbre
- Infixe (G, racine, D) — donne les valeurs triées dans un ABR
- Postfixe (G, D, racine) — utile pour libérer la mémoire
- Largeur (BFS, niveau par niveau) — nécessite une file
Les parcours préfixe / infixe / postfixe sont naturellement récursifs. Le parcours en largeur nécessite une structure de file (FIFO).
Hauteur : $h(\text{vide}) = -1$, $h(n) = 1 + \max(h(n.g), h(n.d))$.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Sac à dos (Programmation Dynamique)
- Plus Longue Sous-séquence Commune (LCS)
- Détection de Cycle (Floyd)
- Arbre Binaire de Recherche (ABR)
- Tri par Tas (Heap Sort)
- Algorithme de Kadane
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.