Hauteur d'un arbre (convention racine = 0)

Application directe du cours · niveau 1 (application) · NSI (terminale), chapitre 3 — Les arbres

Énoncé

Hauteur d'un arbre (convention racine = 0).

Écrire une fonction hauteur(arbre) renvoyant la hauteur d'un arbre binaire, avec la convention : un arbre vide a une hauteur de $- 1$ et une feuille une hauteur de $0$ .

Corrigé


def hauteur(arbre):
    if arbre is None:
        return -1
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

Le max sélectionne le sous-arbre le plus profond, et le +1 compte le lien vers la racine. Coût $O (n)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.