Problème — Affichage indenté et statistiques d'un arbre

Pour l'affichage indenté, on effectue un parcours en profondeur en passant un paramètre de profondeur qui détermine le décalage. On choisit d'afficher le sous-arbre droit en premier, ce qui donne, en tournant la tête, une représentation visuelle de l'arbre couché.

def afficher(arbre, profondeur=0):
    if arbre is None:
        return
    afficher(arbre.droit, profondeur + 1)
    print("    " * profondeur + str(arbre.valeur))
    afficher(arbre.gauche, profondeur + 1)

def statistiques(arbre):
    if arbre is None:
        return (0, -1, 0)             # (taille, hauteur, feuilles)
    if arbre.gauche is None and arbre.droit is None:
        return (1, 0, 1)              # feuille
    tg, hg, fg = statistiques(arbre.gauche)
    td, hd, fd = statistiques(arbre.droit)
    taille = 1 + tg + td
    hauteur = 1 + max(hg, hd)
    feuilles = fg + fd
    return (taille, hauteur, feuilles)

# Test :
racine = None
for v in [8, 3, 10, 1, 6, 14]:
    racine = inserer(racine, v)
afficher(racine)
print(statistiques(racine))          # (6, 2, 3)

La fonction statistiques calcule les trois grandeurs en un seul parcours $O(n)$, en combinant les résultats des sous-arbres. On évite ainsi de parcourir l'arbre trois fois séparément.