« Arbres binaires/Définitions et propriétés » : différence entre les versions
Contenu supprimé Contenu ajouté
mAucun résumé des modifications |
|||
Ligne 24 :
=== Représentation des arbres binaires ===
[[Fichier:Arbre_binaire_ordonne.svg|Un exemple d'arbre binaire|thumb
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 <math>a</math> vers un nœud <math>b</math> signifie que <math>b</math> est un fils de <math>a</math>.
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 <math>1</math>. On peut ainsi noter l'arbre sous la forme suivante :
Ligne 33 ⟶ 35 :
=== Notion de parité ===
[[File:Arbre_binaire.svg|thumb
Par similitude avec un arbre généalogique, il semble intéréssant de définir la notion de parité dans un arbre binaire. On dit ainsi qu'un arbre <math>a_1</math> est le '''père''' d'un arbre <math>a_2</math> si <math>a_2</math> est un fils (droit ou gauche) de <math>a_1</math>. Par abus de language, on associera un nœud à sa racine, de sorte que dans l'arbre ci-contre, <math>n_1</math> est le père de <math>n_2</math> et <math>n_3</math>.
Ligne 41 ⟶ 43 :
== Profondeur dans un arbre ==
{{Définition
| titre = Définition : profondeur
| contenu =
On appelle profondeur d'un nœud ou d'une feuille dans un arbre binaire le nombre d'arêtes qu'il faut parcourir pour atteindre ce nœud à partir de la racine de l'arbre.
}}
Dans le dernier exemple, les nœuds <math>n_2</math> et <math>n_3</math> ont une profondeur de 1, la racine <math>n_1</math> une profondeur nulle.
== Squelette d'un arbre binaire ==
| |||