Noeud, racine, feuille et sous-arbre

Le vocabulaire de base

Un arbre binaire est une structure de données hiérarchique, formée de noeuds reliés par des liens parent/enfant, où chaque noeud possède au maximum deux enfants : un enfant gauche et un enfant droit.

• Le noeud est l'unité de base : il contient une valeur et jusqu'à deux enfants.
• La racine est l'unique noeud sans parent, celui par lequel on accède à tout l'arbre.
• Une feuille est un noeud qui n'a aucun enfant.
• Un sous-arbre est simplement l'arbre formé par un noeud et tous ses descendants ; on parle de sous-arbre gauche et de sous-arbre droit.

Schéma annoté

              5              (racine, aucun parent)
            /   \
           3     8           (3 et 8 sont enfants de 5)
          / \     \
         1   4     9         (1, 4 et 9 sont des feuilles : aucun enfant)

sous-arbre gauche de 5 : le noeud 3 et tout ce qu'il contient (3, 1, 4)
sous-arbre droit de 5  : le noeud 8 et tout ce qu'il contient (8, 9)

Parent et profondeur

Chaque noeud, sauf la racine, a exactement un parent. La profondeur d'un noeud est le nombre de liens à parcourir depuis la racine pour l'atteindre : la racine est à profondeur 0, ses enfants directs à profondeur 1, et ainsi de suite.

Piège classique

Ne confonds pas « feuille » et « sous-arbre vide » : une feuille est un vrai noeud, avec une valeur, qui n'a simplement pas d'enfants. Un sous-arbre vide (souvent noté None en Python) signifie l'absence totale de noeud à cet endroit. Beaucoup d'algorithmes sur les arbres s'arrêtent justement quand ils rencontrent un sous-arbre vide, ce qui marque la fin d'une branche.