Les Arbres

1. Qu’est-ce qu’un arbre ?

Un arbre est une structure de données hiérarchique utilisée pour représenter des données organisées en niveaux, comme une organisation, un dossier, ou une famille.

Définition formelle :

• Un arbre est un ensemble de nœuds reliés entre eux par des arêtes (liens),

• Il y a un nœud racine unique, qui est le point de départ,

• Chaque nœud peut avoir zéro, un ou plusieurs enfants,

• Il n’y a pas de cycle (pas de retour en arrière, pas de boucle),

• Chaque nœud (sauf la racine) a exactement un parent.

Propriétés importantes :

• La profondeur d’un nœud : nombre de liens entre ce nœud et la racine,

• La hauteur de l’arbre : la plus grande profondeur parmi tous les nœuds,

• Les feuilles sont des nœuds qui n’ont aucun enfant,

• Un arbre vide est un arbre sans nœuds.

2. Pourquoi utiliser un arbre ?

• Pour modéliser des données hiérarchiques (dossiers, menus, expressions, généalogies),

• Pour organiser et rechercher efficacement des données,

• Pour gérer des structures comme des expressions mathématiques ou logiques,

• Pour représenter des relations parent-enfant facilement.

3. Arbre binaire : définition et particularités

Un arbre binaire est un arbre où chaque nœud a au maximum deux enfants distincts :

• Un enfant gauche,

• Un enfant droit.

Cela limite la structure à deux sous-arbres par nœud, ce qui simplifie certaines opérations.

Propriétés spécifiques à l’arbre binaire

• Chaque nœud possède donc deux liens (ou aucun, si c’est une feuille) :

  gauche et droite.

• Un arbre binaire peut être vide (racine = None),

• Il est aussi défini récursivement :

  Un arbre binaire est un nœud + un arbre binaire gauche + un arbre binaire droit.

4. Représentation et structure d’un nœud en Python

On peut modéliser un nœud d’arbre binaire par une classe :

class Noeud:
    def __init__(self, valeur, gauche=None, droite=None):
        self.valeur = valeur    # La donnée stockée
        self.gauche = gauche    # Sous-arbre gauche (Noeud ou None)
        self.droite = droite    # Sous-arbre droit (Noeud ou None)

Chaque nœud « pointe » vers ses enfants, ou vers None s’il n’en a pas.

5. Parcours d’un arbre binaire

Parcourir un arbre signifie visiter tous ses nœuds dans un ordre précis. Il existe 3 parcours principaux, très importants en algorithmique.

5.1 Parcours préfixe (Nœud-Gauche-Droite)

• On visite d’abord le nœud courant,

• Puis on parcourt le sous-arbre gauche,

• Puis le sous-arbre droit.

Schéma du parcours :

Premier passage → visite nœud

Deuxième passage → sous-arbre gauche

Troisième passage → sous-arbre droit

def parcours_prefixe(noeud):
    if noeud:
        print(noeud.valeur)           # 1er passage
        parcours_prefixe(noeud.gauche) # 2e passage
        parcours_prefixe(noeud.droite) # 3e passage

5.2 Parcours infixe (Gauche-Nœud-Droite)

• On parcourt d’abord le sous-arbre gauche,

• Puis on visite le nœud courant,

• Puis on parcourt le sous-arbre droit.

Schéma :

Premier passage → sous-arbre gauche

Deuxième passage → visite nœud

Troisième passage → sous-arbre droit

def parcours_infixe(noeud):
    if noeud:
        parcours_infixe(noeud.gauche) # 1er passage
        print(noeud.valeur)           # 2e passage
        parcours_infixe(noeud.droite) # 3e passage

Ce parcours est très utilisé car, sur un arbre binaire de recherche, il affiche les valeurs dans l’ordre croissant.

5.3 Parcours postfixe (Gauche-Droite-Nœud)

• On parcourt d’abord le sous-arbre gauche,

• Puis le sous-arbre droit,

• Enfin, on visite le nœud courant.

Schéma :

Premier passage → sous-arbre gauche

Deuxième passage → sous-arbre droit

Troisième passage → visite nœud

def parcours_postfixe(noeud):
    if noeud:
        parcours_postfixe(noeud.gauche) # 1er passage
        parcours_postfixe(noeud.droite) # 2e passage
        print(noeud.valeur)             # 3e passage

6. Arbre binaire de recherche (ABR)

Un arbre binaire de recherche est un arbre binaire qui respecte une propriété clé :

Pour chaque nœud, toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud,

et toutes les valeurs du sous-arbre droit sont strictement supérieures à la valeur du nœud.

Pourquoi cette propriété est importante ?

Elle permet :

• De rechercher une valeur rapidement,

• D’insérer et supprimer des valeurs tout en gardant l’ordre,

• D’afficher les valeurs triées facilement avec un parcours infixe.

6.1 Recherche dans un ABR

Pour rechercher une valeur x :

• On compare avec la valeur du nœud courant :
  • Si égal, on a trouvé,
  • Sinon, si x est plus petit, on cherche dans le sous-arbre gauche,
  • Sinon, dans le sous-arbre droit.

• Si on atteint un arbre vide (None), x n’est pas dans l’arbre.

6.2 Insertion dans un ABR

Pour insérer une valeur x :

• Si l’arbre est vide, on crée un nouveau nœud avec x,

• Sinon, on compare avec la valeur du nœud courant,

• On insère récursivement dans le sous-arbre gauche ou droit suivant la comparaison,

• Le nouvel élément devient une feuille à l’endroit adéquat.

6.3 Suppression dans un ABR

La suppression est plus complexe car il faut préserver la propriété ABR :

• Si le nœud est une feuille, on peut le supprimer directement,

• Sinon, on remplace la valeur du nœud par :
  • La valeur minimale du sous-arbre droit (successeur), ou
  • La valeur maximale du sous-arbre gauche (prédécesseur),

• Puis on supprime ce nœud successeur/prédécesseur, qui est une feuille.

7. Pourquoi apprendre les arbres binaires ?

• Les arbres sont partout en informatique (bases de données, systèmes de fichiers, compilateurs, intelligence artificielle),

• Les arbres binaires, notamment les ABR, permettent une gestion rapide et efficace des données,

• Les parcours d’arbre sont des exemples classiques d’algorithmes récursifs,

• La compréhension des arbres est souvent demandée au bac NSI, notamment sur les parcours et la structure ABR.

8. Résumé