Leçons de niveau 15

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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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 binaire[modifier | modifier le wikicode]

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 binaires[modifier | modifier le wikicode]

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 | modifier le wikicode]

Arbre binaire.svg

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éments[modifier | modifier le wikicode]

Profondeur dans un arbre[modifier | modifier le wikicode]

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 binaire[modifier | modifier le wikicode]