Les arbres binaires 

Introduction
La structure d'arbre est l'une des plus importantes et des plus spécifiques de l'informatique. Elle est utilisée par exemple pour l’organisation des fichiers dans les systèmes d'exploitation, la représentation d'une table des matières, d'un arbre généalogique, etc.

Dans cette leçon, l’accent sera mise sur les arbres binaires qui sont un cas particulier des arbres généraux. Une propriété intrinsèque de la structure d’arbre est la récursivité.

Définitions
Un arbre binaire B est un ensemble de noeuds qui est soit vide, soit composé d’une racine et de deux arbres binaires disjoints appelés sousarbre droit et sous-arbre gauche.

• Le père du sommet x est le sommet p tel qu'il existe un arc entre p et x (seule la racine de l’arbre n’a pas de père).
• Le frère de x est un sommet qui a le même père.
• Le sous-arbre droit (resp. gauche) d'un arbre binaire B est le sous-arbre qui a pour racine le fils droit (resp. gauche) de B.
• Un noeud interne est un sommet qui a au moins un fils (gauche ou droit ou les deux).
• Une feuille est un sommet qui n'a pas de fils.
• La hauteur d'un sommet x est la longueur (en nombre d'arcs) du plus long chemin de x à une feuille.
• La hauteur d'un arbre est égale à la hauteur de la racine.

Création d’un arbre binaire

Un arbre binaire peut être créé en définissant un type correspondant à un noeud de l’arbre. Soit par exemple :

Types
Arbre = ^Noeud
Noeud = Struct
    Valeur : Entier
    Gauche : Arbre
    Droite : Arbre
FinStruct

Une telle structure peut être utilisée pour ordonner des éléments, en considérant que le sous-arbre gauche d’un noeud de valeur n contient les éléments inférieurs à n, tandis que le sous-arbre droit contient les
éléments supérieurs n

Une telle structure est pratique pour effectuer des tris rapides. L’algorithme suivant permet de construire un arbre d’entiers à partir d’une suite de nombres entrés par l’utilisateur.

Recherche dans un arbre binaire ordonné

Arbres binaires particuliers

• Un arbre binaire complet possède 2P+1 noeuds (nombre impair) dont P sommets internes et P+1 feuilles.
• On appelle arbre binaire parfait un arbre binaire (complet) tel que chaque sommet est le père de deux sous-arbres de même hauteur.
• Un arbre binaire parfait possède 2h+1-1 sommets, où h est la hauteur de l'arbre.
• On appelle arbre binaire quasi-parfait un arbre binaire parfait éventuellement grignoté d'un étage en bas à droite.
• arbre binaire complet un arbre binaire tel que chaque sommet possède 0 ou 2 fils.

Parcours d’un arbre binaire
On cherche à parcourir un arbre binaire selon une stratégie dite « en profondeur d’abord » ou dans l’ordre préfixe illustré sur le diagramme ci-dessous :

Les éléments doivent être affichés dans l’ordre suivant : 0 1 2 3 4 5 6.