Partie 3 : Arbres¶

Programme officiel (B.O.)¶

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Arbres : structures hiérarchiques. Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches/droits.	Identifier des situations nécessitant une structure de données arborescente. Évaluer quelques mesures des arbres binaires (taille, hauteur, etc.).	On fait le lien avec la rubrique « algorithmique ».

1. Arbres : une structure hiérarchique¶

1.1 Définition¶

Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes. Il possède :

une racine : le nœud au sommet, sans parent ;
des feuilles : les nœuds sans enfant ;
des nœuds internes : les nœuds qui ont au moins un enfant.

1.2 Exemples concrets¶

Situation	Racine	Nœuds internes	Feuilles
Système de fichiers	`/` (racine)	Dossiers	Fichiers
Arbre généalogique	Ancêtre commun	Parents	Individus sans descendant
Expression arithmétique	Opérateur principal	Opérateurs	Nombres
Organisation	Direction générale	Services	Employés
Document HTML	`<html>`	Balises conteneurs	Texte, images

1.3 Vocabulaire général¶

Terme	Définition
Parent	Nœud directement au-dessus
Enfant	Nœud directement en dessous
Frères/sœurs	Nœuds ayant le même parent
Chemin	Suite de nœuds reliés par des arêtes
Niveau d'un nœud	Nombre d'arêtes entre la racine et ce nœud
Arité d'un nœud	Nombre d'enfants de ce nœud

2. Arbres binaires¶

2.1 Définition récursive¶

Un arbre binaire est soit :

l'arbre vide (noté None en Python) ;
un nœud contenant une valeur (appelée étiquette ou clé), un sous-arbre gauche et un sous-arbre droit, qui sont eux-mêmes des arbres binaires.

Chaque nœud possède donc au plus deux enfants.

        7
       / \
      4    9
     / \    \
    2   5    11

2.2 Vocabulaire spécifique¶

Terme	Définition	Exemple (arbre ci-dessus)
Racine	Nœud au sommet	7
Feuille	Nœud sans enfants	2, 5, 11
Nœud interne	Nœud ayant au moins un enfant	7, 4, 9
Sous-arbre gauche de 7	Arbre enraciné en 4	4 → (2, 5)
Sous-arbre droit de 7	Arbre enraciné en 9	9 → (∅, 11)

3. Mesures d'un arbre binaire¶

3.1 Taille¶

La taille est le nombre total de nœuds.

\[\text{taille}(a) = \begin{cases} 0 & \text{si } a \text{ est vide} \\ 1 + \text{taille}(\text{gauche}) + \text{taille}(\text{droit}) & \text{sinon} \end{cases}\]

3.2 Hauteur¶

La hauteur est la profondeur maximale (longueur du plus long chemin de la racine à une feuille).

\[\text{hauteur}(a) = \begin{cases} -1 & \text{si } a \text{ est vide} \\ 1 + \max(\text{hauteur}(\text{gauche}), \text{hauteur}(\text{droit})) & \text{sinon} \end{cases}\]

3.3 Encadrement de la hauteur¶

Pour un arbre binaire de taille n :

\[\lfloor \log_2(n) \rfloor \leq h \leq n - 1\]

Hauteur minimale : arbre complet (tous les niveaux remplis) → \(h = \lfloor \log_2(n) \rfloor\)
Hauteur maximale : arbre filiforme (dégénéré en liste) → \(h = n - 1\)

3.4 Nombre de feuilles¶

Le nombre de feuilles d'un arbre binaire est compris entre 1 et \(\lceil n/2 \rceil\).

4. Implémentation en Python¶

4.1 Classe Noeud¶

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

4.2 Construction d'un arbre¶

arbre = Noeud(7,
    Noeud(4, Noeud(2), Noeud(5)),
    Noeud(9, None, Noeud(11))
)

4.3 Fonctions de mesure¶

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

def hauteur(arbre):
    if arbre is None:
        return -1
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

def nb_feuilles(arbre):
    if arbre is None:
        return 0
    if arbre.gauche is None and arbre.droit is None:
        return 1
    return nb_feuilles(arbre.gauche) + nb_feuilles(arbre.droit)

>>> taille(arbre)
6
>>> hauteur(arbre)
2
>>> nb_feuilles(arbre)
3

4.4 Affichage d'un arbre¶

def afficher(arbre, prefixe="", est_gauche=True):
    if arbre is None:
        return
    connecteur = "├── " if est_gauche else "└── "
    print(prefixe + connecteur + str(arbre.valeur))
    nouveau = prefixe + ("│   " if est_gauche else "    ")
    if arbre.gauche or arbre.droit:
        afficher(arbre.gauche, nouveau, True)
        afficher(arbre.droit, nouveau, False)

5. Cas particuliers d'arbres binaires¶

Type	Définition
Arbre complet	Tous les niveaux sont entièrement remplis sauf éventuellement le dernier (rempli de gauche à droite)
Arbre parfait	Tous les niveaux sont entièrement remplis
Arbre filiforme	Chaque nœud a au plus un enfant (l'arbre ressemble à une liste)
Arbre équilibré	La différence de hauteur entre les sous-arbres gauche et droit de chaque nœud est au plus 1

À retenir¶

Concept	Description
Arbre	Structure hiérarchique avec racine, nœuds internes et feuilles
Arbre binaire	Chaque nœud a au plus 2 enfants (gauche et droit)
Définition récursive	Vide ou nœud + sous-arbre gauche + sous-arbre droit
Taille	Nombre de nœuds : `1 + taille(g) + taille(d)`
Hauteur	Profondeur max : `1 + max(hauteur(g), hauteur(d))`
Encadrement	\(\lfloor \log_2 n \rfloor \leq h \leq n - 1\)