Une définition OCaml du type « arbre binaire »

On voit ici la représentation d’un arbre binaire étiqueté.

Il est composé de noeuds, qui possèdent chacun un fils gauche et un fils droit (chacun de ces deux sous-arbres pouvant être vide).

Les feuilles sont les noeuds dont les deux descendants sont vides. Un seul nœud n’a pas d’ancêtre : c’est la racine de l’arbre.

À chaque noeud est attaché une valeur (ou étiquette ).

Dans le dessin d’un arbre binaire, on ne représente pas (en général) les deux descendants vides des feuilles de l’arbre.

Figure du chapitre 10, page 1

Un arbre est soit vide, soit est un noeud (portant une étiquette) d’où partent un arbre « fils gauche » et un arbre « fils droit ».

On en déduit le type « arbre binaire étiqueté par des valeurs de type ’a » :

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :