⌨ Spécialité NSI · Numérique et sciences informatiques Terminale Générale · Chapitre 3

Arbres et arbres binaires de recherche

Vocabulaire des arbres (racine, nœud, feuille, hauteur, taille), arbres binaires, implémentation, parcours en profondeur (préfixe, infixe, suffixe) et en largeur, arbres binaires de recherche : recherche, insertion et coût.

1. Vocabulaire

Définition

Un arbre est une structure hiérarchique formée de nœuds ; le nœud de départ est la racine, les nœuds sans enfant sont les feuilles. La taille est le nombre de nœuds ; la hauteur est le nombre de nœuds sur la plus longue branche (convention : hauteur $1$ pour une racine seule). Dans un arbre binaire, chaque nœud a au plus deux enfants : un sous-arbre gauche et un sous-arbre droit.

1346781014← racinefeuille
Arbre binaire de recherche : à gauche les clés plus petites, à droite les plus grandes.

2. Implémentation et parcours

Exemple · Classe Noeud

class Noeud:
    def __init__(self, cle, gauche=None, droit=None):
        self.cle, self.gauche, self.droit = cle, gauche, droit

def taille(a):
    if a is None:
        return 0
    return 1 + taille(a.gauche) + taille(a.droit)

Propriété · Parcours en profondeur

Préfixe : nœud, puis gauche, puis droit. Infixe : gauche, nœud, droit. Suffixe : gauche, droit, nœud. Le parcours en largeur visite les nœuds niveau par niveau, à l'aide d'une file. Sur l'arbre du cours : infixe $1, 3, 4, 6, 7, 8, 10, 14$ ; largeur $8, 3, 10, 1, 6, 14, 4, 7$.

3. Arbres binaires de recherche (ABR)

Définition

Un ABR est un arbre binaire où, pour chaque nœud, les clés du sous-arbre gauche sont inférieures à sa clé et celles du sous-arbre droit supérieures. Son parcours infixe donne les clés triées.

Méthode · Recherche dans un ABR

def recherche(a, x):
    while a is not None:
        if x == a.cle:
            return True
        a = a.gauche if x < a.cle else a.droit
    return False

Propriété · Coût

La recherche et l'insertion suivent une seule branche : coût proportionnel à la hauteur $h$. Pour un arbre équilibré de $n$ nœuds, $h \approx \log_2 n$ ; pour un arbre « peigne » (clés insérées dans l'ordre), $h = n$.

Activité · Insérer dans un ABR

MatérielPython.
ConsigneÉcrire une fonction récursive inserer(a, x) qui renvoie l'arbre après insertion de x.
Résultat
def inserer(a, x):
    if a is None:
        return Noeud(x)
    if x < a.cle:
        a.gauche = inserer(a.gauche, x)
    else:
        a.droit = inserer(a.droit, x)
    return a
BilanL'ordre d'insertion détermine la forme de l'arbre, donc son efficacité.

⚠️ Une erreur dans ce cours ? Signalez-la

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

2

Taille et hauteur

★☆☆

Taille et hauteur de l'arbre ci-dessous ? (La hauteur est le nombre de nœuds de la plus longue branche : une racine seule a pour hauteur $1$.)

1346781014
Un arbre binaire de recherche à 8 nœuds.
🔒 Correction réservée aux membres Créer un compte gratuit →
5

Parcours infixe

★☆☆

Le parcours infixe de l'arbre ci-dessous donne $1, 3, 4, 6, 7, 8, 10, 14$. Pourquoi le parcours infixe donne-t-il les clés dans l'ordre croissant ?

1346781014
Un arbre binaire de recherche à 8 nœuds.
🔒 Correction réservée aux membres Créer un compte gratuit →
6

Vérifier un ABR

★★☆

Dans l'arbre binaire de recherche ci-dessous, on remplace la clé $7$ par $9$. Est-ce toujours un ABR ?

1346781014
Un arbre binaire de recherche à 8 nœuds.
🔒 Correction réservée aux membres Créer un compte gratuit →
12

Hauteur

★★★

Les arbres binaires sont construits avec la classe Noeud ci-dessous. Écrire une fonction récursive hauteur(a) (hauteur $0$ pour l'arbre vide).

class Noeud:
    def __init__(self, cle, gauche=None, droit=None):
        self.cle, self.gauche, self.droit = cle, gauche, droit
# l'arbre vide est représenté par None
🔒 Correction réservée aux membres Créer un compte gratuit →
13

Nombre de feuilles

★★★

Les arbres binaires sont construits avec la classe Noeud ci-dessous. Écrire une fonction feuilles(a) qui compte les feuilles.

class Noeud:
    def __init__(self, cle, gauche=None, droit=None):
        self.cle, self.gauche, self.droit = cle, gauche, droit
# l'arbre vide est représenté par None
🔒 Correction réservée aux membres Créer un compte gratuit →
14

Minimum d'un ABR

★★☆

Où se trouve la plus petite clé d'un ABR ? Écrire la fonction (pour un ABR non vide construit avec la classe Noeud ci-dessous).

class Noeud:
    def __init__(self, cle, gauche=None, droit=None):
        self.cle, self.gauche, self.droit = cle, gauche, droit
# l'arbre vide est représenté par None
🔒 Correction réservée aux membres Créer un compte gratuit →
15

Parcours en largeur

★★★

Écrire le parcours en largeur d'un arbre binaire (construit avec la classe Noeud ci-dessous) à l'aide d'une file.

class Noeud:
    def __init__(self, cle, gauche=None, droit=None):
        self.cle, self.gauche, self.droit = cle, gauche, droit
# l'arbre vide est représenté par None
🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.