Les parcours (préfixe, infixe, suffixe) et la hauteur

Trois façons de lire un arbre

Un parcours d'arbre visite tous les noeuds selon un ordre précis. Les trois parcours « en profondeur » les plus courants ne diffèrent que par la position où l'on traite la racine :

• préfixe : racine, puis sous-arbre gauche, puis sous-arbre droit ;
• infixe : sous-arbre gauche, puis racine, puis sous-arbre droit ;
• suffixe : sous-arbre gauche, puis sous-arbre droit, puis racine.

Schéma : les trois parcours sur le même arbre

                    8
                  /   \
                 3     10
                / \       \
               1   6        14
                  / \      /
                 4   7    13

prefixe (racine, gauche, droite) : 8 3 1 6 4 7 10 14 13
infixe  (gauche, racine, droite) : 1 3 4 6 7 8 10 13 14   (toujours trié !)
suffixe (gauche, droite, racine) : 1 4 7 6 3 13 14 10 8

La hauteur d'un arbre

La hauteur d'un arbre est la longueur, en nombre de liens, du plus long chemin entre la racine et une feuille. Un arbre réduit à un seul noeud a une hauteur de 0, et un arbre vide a une hauteur conventionnelle de -1.

Sur l'arbre ci-dessus, le chemin le plus long va de 8 vers 4, 7 ou 13 (tous à la même profondeur) : par exemple 8 -> 3 -> 6 -> 4, soit 3 liens. La hauteur de cet arbre est donc 3.

Implémentation en Python

def prefixe(noeud, resultat):
    if noeud:
        resultat.append(noeud.valeur)
        prefixe(noeud.gauche, resultat)
        prefixe(noeud.droit, resultat)
    return resultat

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

Piège classique

Ne mélange pas hauteur et nombre de noeuds : un arbre « en baguette » (chaque noeud n'a qu'un seul enfant) contenant 100 noeuds a une hauteur de 99, alors qu'un arbre bien équilibré de 100 noeuds a une hauteur d'environ 6 seulement (puisque 2 puissance 7 dépasse 100). C'est cette différence qui rend les arbres équilibrés si efficaces en pratique.