Arbres binaires/Définitions et propriétés

Début de la boite de navigation du chapitre
Définitions et propriétés
Icône de la faculté
Chapitre no 1
Leçon : Arbres binaires
Retour auSommaire
Chap. suiv. :Implémentation

Exercices :

Arbres en language Caml
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Arbres binaires : Définitions et propriétés
Arbres binaires/Définitions et propriétés
 », n'a pu être restituée correctement ci-dessus.

Définition formelle d'un arbre binaireModifier

Un arbre binaire est un arbre dont chaque nœud comporte au plus deux fils. C'est une structure de données qui apparaît souvent dans les problèmes algorithmiques classiques.


Remarque : on appelle aussi sous-arbre le fils d'un arbre binaire.

Représentation des arbres binairesModifier

 
Un exemple d'arbre binaire

La représentation d'un arbre binaire se fait de façon hiérarchique, en plaçant au premier niveau la racine, puis au second ses fils droit et gauche… Une flèche d'un nœud   vers un nœud   signifie que   est un fils de  .

L'image ci-contre illustre un arbre binaire où les feuilles et les nœuds sont étiquetés par l’ensemble des entiers naturels. La racine de l'arbre est l'entier  . On peut ainsi noter l'arbre sous la forme suivante :

 .

On peut parfois rencontrer la notion de nœud interne et de nœud externe : un nœud externe correspond à une feuille, un nœud interne à ce que l’on nomme nœud. Ici, les nœuds indexés par les entiers 4, 7, 8, 9 sont des feuilles.

Notion de parentéModifier

Par analogie avec un arbre généalogique, il semble intéressant de définir la notion de parenté dans un arbre binaire. On dit ainsi que la racine d'un arbre   est le père d'un arbre   si   est un fils (droit ou gauche) de  . Par abus de langage, on associera un nœud à sa racine, de sorte que dans l'arbre ci-contre,   est le père de   et  .

Indexation des élémentsModifier

Profondeur dans un arbreModifier

Dans un arbre  , on définit rapidement la notion de chemin de la racine (notée  ) vers une feuille   de   : c’est la donnée d'une suite   de nœuds de l'arbre, tels que pour tout  ,   soit le fils de  . La longueur de ce chemin est alors égale à  , le nombre de nœuds du chemin.



Dans le dernier exemple, les nœuds   et   ont une profondeur de  , la racine   une profondeur nulle. La hauteur de l'arbre vaut  .

Début d’un théorème
Fin du théorème



Remarque : cette définition peut être généralisée au cas d'arbre quelconque en rajoutant la condition suivante : tous les nœuds ont même degré. Dans le cas d'un arbre binaire, les nœuds ont tous pour degré  .

Début d’un théorème
Fin du théorème


Squelette d'un arbre binaireModifier