Arbres binaires : taille, hauteur et parcours

Un arbre binaire est soit vide, soit formé d'un nœud (la racine) et de deux arbres binaires : son sous-arbre gauche et son sous-arbre droit. Un nœud sans aucun fils est une feuille.

Prenons l'arbre de racine A, dont le fils gauche est B et le fils droit C ; B a pour fils D et E ; C n'a qu'un fils droit, F. On le représente ici par un dictionnaire : à chaque nœud, le couple (fils gauche, fils droit), None signalant l'absence de fils.

La définition étant récursive, les algorithmes le sont aussi. La hauteur (convention : 1 pour une racine seule, 0 pour l'arbre vide) vaut 1 + la plus grande des hauteurs des deux sous-arbres ; la taille est le nombre de nœuds.

arbre = {"A": ("B", "C"), "B": ("D", "E"), "C": (None, "F"), "D": (None, None), "E": (None, None), "F": (None, None)}

def prefixe(n):
    if n is None:
        return []
    g, d = arbre[n]
    return [n] + prefixe(g) + prefixe(d)

def infixe(n):
    if n is None:
        return []
    g, d = arbre[n]
    return infixe(g) + [n] + infixe(d)

def suffixe(n):
    if n is None:
        return []
    g, d = arbre[n]
    return suffixe(g) + suffixe(d) + [n]

def hauteur(n):
    if n is None:
        return 0
    g, d = arbre[n]
    return 1 + max(hauteur(g), hauteur(d))

print(prefixe("A"))
print(infixe("A"))
print(suffixe("A"))
print(hauteur("A"), len(arbre))

['A', 'B', 'D', 'E', 'C', 'F']
['D', 'B', 'E', 'A', 'C', 'F']
['D', 'E', 'B', 'F', 'C', 'A']
3 6

Les parcours en profondeur diffèrent par le moment où l'on visite la racine :

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

Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite, à l'aide d'une file :

arbre = {"A": ("B", "C"), "B": ("D", "E"), "C": (None, "F"), "D": (None, None), "E": (None, None), "F": (None, None)}
file = ["A"]
ordre = []
while file:
    n = file.pop(0)
    ordre.append(n)
    for fils in arbre[n]:
        if fils is not None:
            file.append(fils)
print(ordre)

['A', 'B', 'C', 'D', 'E', 'F']

Arbre binaire de recherche (ABR). Chaque nœud porte une clé ; toutes les clés du sous-arbre gauche sont inférieures à la sienne, toutes celles du sous-arbre droit supérieures. Pour rechercher une clé, on part de la racine et on descend à gauche ou à droite selon la comparaison : on suit un seul chemin, de longueur au plus la hauteur. Pour insérer, on descend de la même façon jusqu'à une place vide. Le coût est donc proportionnel à la hauteur : logarithmique si l'arbre est équilibré, mais linéaire s'il est filiforme. Le parcours infixe d'un ABR donne ses clés dans l'ordre croissant.

Énoncé. Un arbre binaire a 7 nœuds. Entre quelles valeurs sa hauteur est-elle comprise ?

1. Hauteur maximale : l'arbre est filiforme (chaque nœud a un seul fils) ; la hauteur est alors égale à la taille : 7.
2. Hauteur minimale : chaque niveau est rempli. Avec h niveaux, on loge au plus 1 + 2 + 4 + … = 2ʰ − 1 nœuds. Avec 2 niveaux, au plus 3 nœuds ; avec 3 niveaux, au plus 7 : la hauteur minimale est 3.

Conclusion : 3 ⩽ h ⩽ 7. En général, pour un arbre non vide de taille n et de hauteur h : h ⩽ n ⩽ 2ʰ − 1.

Trois niveaux : hauteur 3. Six nœuds : taille 6. Trois feuilles : D, E et F.