Hauteur et taille d’un arbre binaire

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 :

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