Structure

Définition

Arbre binaire

Un arbre binaire est une structure arborescente où chaque position dans l'arbre donne sur exactement deux branches.

C'est un ensemble fini de nœuds défini par l'un des deux cas suivants :

• Soit l'arbre est vide, et ne contient aucun nœud.
• Soit l'arbre n'est pas vide, et contient des nœuds structurés de la manière suivante :
• l'un des nœuds est appelé racine de l'arbre ;
• les autres nœuds sont répartis en deux sous-ensembles nommés sous-arbre gauche et sous-arbre droit définis récursivement de la même manière ;
• la racine est reliée par deux branches aux deux sous-ensembles de l'arbre.

Pour représenter un arbre binaire non vide, la majorité du temps, on place la racine en haut et les sous-arbres gauche et droit à gauche et à droite sous la racine, reliés par un trait (la branche). Les nœuds sont généralement représentés par des cercles.

Exercice

Dessiner tous les arbres binaires ayant respectivement 1, 2 et 3 nœuds.

Vocabulaire

Feuille

Une feuille est un arbre qui ne contient qu'un seul nœud (à ne pas confondre avec arbre binaire vide).

Taille

La taille d'un arbre est le nombre de nœuds de cet arbre.

Hauteur

La hauteur d'un arbre est le plus grand nombre de nœuds possible rencontrés entre une racine et une feuille en n'empruntant que des sous-arbres.

Par exemple, l'arbre binaire ci-contre est de hauteur 3.

Une définition récursive est possible :

• Un arbre vide a pour hauteur 0.
• Un arbre non vide a pour hauteur le maximum de la hauteur des sous-arbres de la racine plus 1.

Nombre de nœuds et hauteur

Soit \(n\) la taille d'un arbre binaire, et \(h\) la hauteur de ce même arbre binaire. Ces deux valeurs sont liées par l'inéquation :

\[h \le n \le 2^h−1\]

On peut prouver \(h \le n\) grâce aux arbres ayant que des sous-arbres gauches ou que des sous-arbres droits. Ces arbres sont appelés peignes.

On peut prouver \(n \le 2^h−1\) grâce aux arbres ayant le plus grand nombre de nœuds à une hauteur fixe. On dit que ces arbres sont parfaits.

Exercice

Sachant qu'il y a :

• 1 arbre binaire de taille 0 ;
• 1 arbre binaire de taille 1 ;
• 2 arbres binaires de taille 2 ;
• 5 arbres binaires de taille 3 ;
• 14 arbres binaires de taille 4.

Combien y a-t-il d'arbres binaires de taille 5 ?

Les données

C'est bien beau d'avoir des arbres, mais on les stocke où nos données ?

Eh bien, dans les nœuds !

L'implémentation

Nous implémentons les arbres binaires à l'aide d'une classe en Python.

Créons une classe Noeud permettant de stocker la valeur de la racine et deux sous-arbres (donc deux instances de Noeud).

class Noeud:
    def __init__(self, g, v, d):
        self.gauche = g
        self.valeur = v
        self.droit = d

Ainsi, l'arbre ci-contre est enregistré dans la variable a avec a = Noeud(Noeud(Noeud(None, 5, None), 7, Noeud(None, 2, None)), 3, Noeud(Noeud(None, 8, None), 1, None)) qui peut s'écrire de la façon suivante :

a = Noeud(
        Noeud(
            Noeud(None, 5, None),
            7,
            Noeud(None, 2, None)
            ),
        3,
        Noeud(
            Noeud(None, 8, None),
            1,
            None
            )
        )