La hauteur {h} d’un arbre non vide {\mathcal{A}} est le nombre d’arêtes dans un plus long chemin descendant de la racine à une feuille. Conformément au programme, la hauteur de l’arbre vide est {-1} et celle d’une feuille est {0}.
L’arbre binaire cité en exemple au début du chapitre est donc de hauteur {4}. Si {\mathcal{A}=\mathrm{Vide}}, alors {h(\mathcal{A})=-1}. Sinon, en écrivant {\mathcal{A}=(\mathcal{G},e,\mathcal{D})}, on a {h(\mathcal{A})=1+\max(h(\mathcal{G}),h(\mathcal{D}))}.
On en déduit la fonction hauteur donnant la hauteur d’un arbre :
|
1 2 3 4 |
let rec hauteur a = match a with | Vide -> -1 | Noeud(g, _, d) -> 1 + max (hauteur g) (hauteur d);; val hauteur : 'a arbre -> int = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres