Arbres binaires

Arbres binaires¶

Définition et vocabulaire¶

Un arbre binaire est un ensemble fini de nœuds correspondant à l'un des deux cas suivants :

L'arbre ne contient aucun nœud (arbre vide) ;
l'arbre n'est pas vide :
- un nœud est appelé la racine de l'arbre ;
- les nœuds restants sont répartis entre le sous-arbre gauche (abrégé sag) et le sous-arbre droit (abrégé sad). Ces sous-arbres sont appelés les enfants (gauche, droit) de l'arbre.

Un nœud dont les deux enfants sont l'arbre vide est appelé une feuille. On peut ajouter à chaque nœud une étiquette. On parle dans ce cas d'arbre étiqueté.

On appelle profondeur d'un nœud dans un arbre le nombre d'arêtes qu'il faut parcourir en descendant de la racine au nœud.
On appelle hauteur d'un arbre la profondeur maximale d'un nœud de l'arbre.
On appelle taille d'un arbre le nombre de nœuds qui composent l'arbre.

L'arbre ci-dessous à gauche a pour hauteur 3, pour taille 15, et le nœud étiqueté \(11\) a pour profondeur 2. L'arbre ci-dessous à droite a une hauteur de 3 et une taille de 4. Le nœud étiqueté \(2\) a pour profondeur \(1\).

Soit \(A\) un arbre binaire, \(h\) sa hauteur et \(n\) sa taille. Alors :

\[ h + 1 \leq n \leq 2^{h + 1} - 1 \]

On montre cette propriété par récurrence sur la hauteur de l'arbre.

Parcours d'arbre¶

Parcours en profondeur d'abord¶

Le parcours en profondeur d'un arbre binaire correspond à l'algorithme récursif donné ci-dessous :

Si l'arbre est vide, on ne fait rien ;
Si l'arbre n'est pas vide, alors on effectue les trois opérations suivantes dans un certain ordre :
- Parcours : On parcourt récursivement le sous-arbre gauche.
- Parcours : On parcourt récursivement le sous-arbre droit.
- Traitement : On effectue une opération sur la racine.

Lorsque l'opération de traitement est réalisée entre les deux appels récursifs, on dit que le parcours est infixe. Si le traitement est effectué en premier, on dit que le parcours est prefixe, si le traitement est effectué en dernier, on dit qu'il est postfixe.

Dans tous les cas suivants, l'opération de traitement est l'opération "afficher l'étiquette de la racine".

Parcours préfixe de l'arbre.

Les nœuds sont parcourus dans l'ordre /home/, David/, Clémence/, NSI/, devoirs.txt.
Parcours infixe de l'arbre.

Les nœuds sont parcourus dans l'ordre 1, 5, 6, 8, 9.
Parcours postfixe de l'arbre.

Les nœuds sont parcourus dans l'ordre 1, 5, 8, ×, +

Parcours en largeur d'abord¶

Cela correspond à un parcours itératif de l'arbre à l'aide d'une file d'attente FIFO (First In First Out) :

On maintient la liste des éléments à parcourir dans une file : initialement la file est constituée d'un élément, correspondant à la racine de l'arbre à parcourir.
Tant que la file des éléments à parcourir n'est pas vide :
1. Défiler le premier élément \(A\) de la file.
2. Traiter l'élément \(A\).
3. Ajouter à la file d'attente les enfants de \(A\).

Parcours en largeur d'abord de l'arbre :

Affichage. a, b, c, d, e, f, g, h, k

Interface et implémentation en Python¶

On donne dans le tableau ci-dessous la liste des fonctionnalités que le type Arbre doit supporter.

Fonctionnalité	Notation objet	Description
`creer_vide()`	`Arbre()`	Renvoie l'arbre vide
`Arbre(e, a1, a2)`	`Arbre(e, a1, a2)`	Renvoie l'arbre dont la racine est étiquetée par `e` et dont le sous-arbre gauche est `a1` et le sous-arbre droit est `a2`.
`est_vide(a)`	`a.est_vide()`	Teste si l'arbre `a` est vide.
`gauche(a)`	`a.gauche()`	Renvoie le sous-arbre gauche de l'arbre `a`.
`droit(a)`	`a.droit()`	Renvoie le sous-arbre droit de l'arbre `a`.
`etiquette(a)`	`a.etiquette()`	Renvoie l'étiquette de la racine de l'arbre `a`.

Il est possible d'implémenter en Python cette interface via les classes Noeud et Arbre suivantes :

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

class Arbre:
    def __init__(self, e=None, a1=None, a2=None):
        self.racine = Noeud(e, a1, a2) if None not in {e, a1, a2} else None