Application aux arbres binaires

Soit $f$ une fonction prenant an argument un arbre binaire, la façon la plus claire et la précise de définir une telle fonction est souvent de la caractériser par induction. Par exemple

Définition 4.1.1   On note $h(A)$ la hauteur de l'arbre $A$. On la définit par induction :

• $h(\emptyset) = -1$
• $h((A_g, r, A_d)) = 1 + \max(h(A_g), h(A_d))$

Définition 4.1.2   On note $\vert A\vert$ le nombre de noeuds d'un arbre $A$. On le définit par induction :

• $\vert\emptyset\vert = 0$
• $\vert(A, r, B)\vert = 1 + \vert A\vert + \vert B\vert$