« Arbres binaires/Définitions et propriétés » : différence entre les versions

== Définition formelle d'un arbre binaire ==

 

 

{{Définition

| contenu =

Étant donné deux ensembles <math>N</math> (valeurs des nœuds) et <math>F</math> (valeurs de feuilles), un arbre binaire est un ensemble fini d'éléments qui est :

* soit constitué d'une feuille <math>f \in F</math> ;

* soit constitué d'une '''racine''' <math>n \in N</math>, et de deux arbres binaires disjoints <math>g</math> et <math>d</math> appelés '''fils gauche''' et '''fils droit''' — on le note <math>(n,\ g,\ d)</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 :

 

 

=== Notion de parité ===