Numérique et sciences informatiques (NSI) · Terminale

Exercices : arbres binaires et arbres binaires de recherche

22 exercices avec correction détaillée, en 3 séries. Aucune inscription : ta progression reste sur ton appareil.

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

Arbres binaires et arbres binaires de recherche — S’entraîner

Feuille d’exercices

Prénom : ……………………………Date : ……………………Score : ……… / 8

Sauf mention contraire, les questions portent sur l’arbre A du cours, rappelé dans les énoncés. Convention : un arbre réduit à sa racine a une hauteur 1.

Exercice 1 — Relie chaque élément de gauche à celui de droite.
Associe chaque terme à sa définition.
1. 1. Racine
2. 2. Feuille
3. 3. Taille
4. 4. Hauteur
- A. Nœud sans enfant
- B. Nombre total de nœuds
- C. Plus grande profondeur d’un nœud
- D. Unique nœud sans parent

Exercice 2

Quelle est la taille de l’arbre A ?

            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13

Texte

Écris tes calculs :

Réponse : ………………

Exercice 3
Quelle est la hauteur de l’arbre A (convention : racine seule = hauteur 1) ?
```
            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13
```
Texte
Écris tes calculs :
Réponse : ………………

Exercice 4

Écris les valeurs de A dans l’ordre du parcours préfixe, séparées par des espaces.

            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13

Texte

Exercice 5 — Coche la bonne réponse.
Quel parcours d’un arbre binaire de recherche donne ses clés dans l’ordre croissant ?
- Préfixe
- Infixe
- Suffixe
- En largeur
Exercice 6 — Coche « Vrai » ou « Faux ».
L’arbre ci-dessous est un arbre binaire de recherche.
```
        5
       / \
      3   8
       \
        7
```
Texte
VraiFaux
Exercice 7
Combien de nœuds sont examinés (y compris celui trouvé) lors de la recherche de 13 dans l’ABR A ?
```
            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13
```
Texte
Écris tes calculs :
Réponse : ………………
Exercice 8
Écris une fonction récursive nb_feuilles(a) qui renvoie le nombre de feuilles d’un arbre binaire a (implémenté avec la classe Noeud, l’arbre vide étant None).

ulumine.com — exercices corrigés gratuits

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

Arbres binaires et arbres binaires de recherche — S’entraîner

Corrigé détaillé — pour les parents et les enseignants

Exercice 1
Réponse : 1 → D · 2 → A · 3 → B · 4 → C
Dans l’arbre A : la racine est 8, les feuilles sont 1, 4, 7 et 13, la taille vaut 9 et la hauteur 4.
Exercice 2
Réponse : 9
On compte les nœuds : 8, 3, 10, 1, 6, 14, 4, 7, 13, soit 9 nœuds.
Exercice 3
Réponse : 4
Le plus long chemin depuis la racine est par exemple 8 → 3 → 6 → 4 : il compte 4 nœuds.
Exercice 4
Réponse : 8 3 1 6 4 7 10 14 13
Préfixe : on traite le nœud, puis tout le sous-arbre gauche, puis tout le sous-arbre droit.
1. 8, puis le sous-arbre gauche : 3 1 6 4 7
2. puis le sous-arbre droit : 10 14 13
3. Résultat : 8 3 1 6 4 7 10 14 13
Exercice 5
Réponse : Infixe
L’infixe traite le sous-arbre gauche (clés plus petites), puis le nœud, puis le sous-arbre droit (clés plus grandes) : on obtient l’ordre croissant.
Exercice 6
Réponse : Faux
7 est dans le sous-arbre gauche de 5 alors que 7 > 5. La condition doit être vérifiée pour toutes les clés d’un sous-arbre, pas seulement pour les enfants directs.
Exercice 7
Réponse : 4
13 > 8 : à droite vers 10 ; 13 > 10 : à droite vers 14 ; 13 < 14 : à gauche, on trouve 13. Nœuds examinés : 8, 10, 14, 13.
Exercice 8
Exemple de réponse : Si l’arbre est vide, il n’a aucune feuille : on renvoie 0. Si le nœud n’a ni enfant gauche ni enfant droit, c’est une feuille : on renvoie 1. Sinon, on renvoie la somme des feuilles des deux sous-arbres.
Sur l’arbre A, la fonction renvoie 4 (feuilles 1, 4, 7, 13).
```
def nb_feuilles(a):
    if a is None:
        return 0
    if a.gauche is None and a.droit is None:
        return 1
    return nb_feuilles(a.gauche) + nb_feuilles(a.droit)
```
Python
- Cas de l’arbre vide.
- Test d’une feuille (deux enfants à None).
- Somme des appels récursifs sur les deux sous-arbres.

Sauf mention contraire, les questions portent sur l’arbre A du cours, rappelé dans les énoncés. Convention : un arbre réduit à sa racine a une hauteur 1.

Exercices corrigés : 0 / 8

Exercice 1 sur 8
Association
Associe chaque terme à sa définition.
- Racine
- Feuille
- Taille
- Hauteur
Aide d’ULU pour cet exercice
Exercice 2 sur 8
Calcul
Quelle est la taille de l’arbre A ?
```
            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13
```
Texte
Ta réponse
Aide d’ULU pour cet exercice
Exercice 3 sur 8
Calcul
Quelle est la hauteur de l’arbre A (convention : racine seule = hauteur 1) ?
```
            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13
```
Texte
Ta réponse
Aide d’ULU pour cet exercice
Exercice 4 sur 8
Réponse à écrire
Écris les valeurs de A dans l’ordre du parcours préfixe, séparées par des espaces.
```
            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13
```
Texte
Ta réponse
Aide d’ULU pour cet exercice
Exercice 5 sur 8
QCM
Quel parcours d’un arbre binaire de recherche donne ses clés dans l’ordre croissant ?
Choisis une réponse
PréfixeInfixeSuffixeEn largeur
Aide d’ULU pour cet exercice
Exercice 6 sur 8
Vrai ou faux
L’arbre ci-dessous est un arbre binaire de recherche.
```
        5
       / \
      3   8
       \
        7
```
Texte
Vrai ou faux ?
VraiFaux
Aide d’ULU pour cet exercice
Exercice 7 sur 8
Calcul
Combien de nœuds sont examinés (y compris celui trouvé) lors de la recherche de 13 dans l’ABR A ?
```
            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13
```
Texte
Ta réponse
Aide d’ULU pour cet exercice
Exercice 8 sur 8
Question ouverte
Écris une fonction récursive nb_feuilles(a) qui renvoie le nombre de feuilles d’un arbre binaire a (implémenté avec la classe Noeud, l’arbre vide étant None).
Ta réponse
Aide d’ULU pour cet exercice

À découvrir aussi

Terminale · Numérique et sciences informatiques (NSI)

La récursivité

Fonctions récursives en Python : cas de base, appels récursifs, pile d’appels, terminaison et comparaison avec l’itératif. Cours et exercices de NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

La programmation orientée objet

Classes, objets, attributs et méthodes en Python : constructeur __init__, self, interface et références. Cours et exercices de programmation objet en NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

Listes, piles, files et dictionnaires

Interface et implémentation des structures linéaires : listes chaînées, piles (LIFO), files (FIFO) et dictionnaires en Python. Cours et exercices de NSI Terminale.