Arbres binaires (MP)

Représenter, parcourir et exploiter les arbres binaires, les arbres binaires de recherche et les tas.

MP · Séquence 3 sur 10 · Thèmes : Structures de données, Algorithmique et preuve de programmes

Notions abordées

• Vocabulaire des arbres
• Implémentation d'un arbre binaire
• Parcours d'arbres
• Arbres binaires de recherche
• Tas binaire
• Arbres AVL

Ressources de la séquence

Ces ressources sont réservées aux élèves et professeurs inscrits :

• Un cours rédigéSe connecter pour ouvrir
• Une présentationSe connecter pour ouvrir
• Une série d'exercicesSe connecter pour ouvrir
• Un notebook Python à compléter, exécutable dans le navigateurSe connecter pour ouvrir

Dans le programme MP

• Séquence précédente : Algorithmes de tri
• Séquence suivante : Algorithmes gloutons
• Toutes les séquences de MP

Thèmes liés dans l'autre année

• MPSI · Séquence 3

  Récursivité

  Écrire et analyser des fonctions récursives, comprendre la pile d'appels et la démarche « diviser pour régner ».

• MPSI · Séquence 4

  Correction et terminaison des programmes

  Spécifier une fonction, la tester et prouver qu'elle termine et qu'elle est correcte, grâce aux variants et aux invariants de boucle.

• MPSI · Séquence 5

  Types de données composés

  Manipuler les listes, chaînes de caractères, tuples, ensembles et dictionnaires de Python, avec les algorithmes de recherche et de tri associés.