Informatique · Terminale · 1 exercice vérifié
S’entraîner : Algorithmes sur les arbres binaires et les arbres binaires de recherche
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Calculer récursivement la taille et la hauteur d'un arbre binaire ; parcours en profondeur dans les ordres préfixe (racine, gauche, droite), infixe (gauche, racine, droite) et suffixe (gauche, droite, racine), et parcours en largeur ; dans un arbre binaire de recherche, rechercher et insérer une clé en descendant à gauche ou à droite selon la comparaison ; coût proportionnel à la hauteur, logarithmique si l'arbre est équilibré ; le parcours infixe d'un arbre binaire de recherche donne les clés dans l'ordre croissant.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Arbres binaires : vocabulaire et mesures — Structure hiérarchique : nœuds, racine, feuilles, sous-arbre gauche et sous-arbre droit ; taille (nombre de nœuds) et hauteur (avec une convention à préciser : un arbre réduit à sa racine a pour hauteur 1, l'arbre vide 0) ; encadrement h ⩽ n ⩽ 2^h − 1 entre la hauteur h et la taille n d'un arbre binaire non vide ; situations nécessitant une structure arborescente (arborescence de fichiers, expression arithmétique).
- Programmes récursifs — Une fonction récursive s'appelle elle-même sur une donnée plus petite ; elle comporte au moins un cas de base, traité sans appel récursif, qui garantit l'arrêt ; analyser un appel par la pile des appels ou l'arbre des appels ; compter les appels effectués ; écrire une version récursive d'un calcul (factorielle, puissance, somme des chiffres).
Comment se déroule la séance
Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Remise en ordre (1). Difficulté 3 sur 5. Environ 5 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 3 sur 5 · ≈ 5 minutes
Énoncé
Un arbre binaire a pour racine F. Le tableau donne, pour chaque nœud, son fils gauche et son fils droit (« — » : pas de fils).
| Nœud | Fils gauche | Fils droit |
|---|---|---|
| A | — | E |
| B | — | A |
| C | — | G |
| D | C | B |
| E | — | — |
| F | D | — |
| G | — | — |
Nœuds à ranger :
B ; F ; E ; C ; D ; G ; A
Rangez les nœuds dans l'ordre où ils sont visités par le parcours suffixe (le sous-arbre gauche, puis le sous-arbre droit, puis la racine).
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.