Les arbres

On crée une classe dont le constructeur prend la valeur du nœud et, optionnellement, ses deux enfants.

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche      # sous-arbre gauche (Noeud ou None)
        self.droit = droit        # sous-arbre droit (Noeud ou None)

# Construction de l'arbre :
#        1
#       / \
#      2   3
#     / \
#    4   5
arbre = Noeud(1,
              Noeud(2, Noeud(4), Noeud(5)),
              Noeud(3))

def taille(arbre):
    if arbre is None:          # cas de base : arbre vide
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droit)

def hauteur(arbre):
    if arbre is None:          # arbre vide : hauteur -1 par convention
        return -1              # ainsi une feuille aura une hauteur 0
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

La fonction taille compte la racine ($1$) plus les nœuds de chaque sous-arbre. La fonction hauteur renvoie $-1$ pour l'arbre vide, de sorte qu'une feuille (deux sous-arbres vides) obtienne $1+\max (-1,-1)=0$. Ces deux fonctions ont un coût de $O(n)$ car elles visitent chaque nœud une fois.

Chaque parcours s'écrit en trois lignes récursives, en plaçant le traitement de la racine (ici un append) au bon endroit.

def prefixe(arbre, resultat):
    if arbre is not None:
        resultat.append(arbre.valeur)   # 1. racine
        prefixe(arbre.gauche, resultat) # 2. gauche
        prefixe(arbre.droit, resultat)  # 3. droit

def infixe(arbre, resultat):
    if arbre is not None:
        infixe(arbre.gauche, resultat)  # 1. gauche
        resultat.append(arbre.valeur)   # 2. racine
        infixe(arbre.droit, resultat)   # 3. droit

def suffixe(arbre, resultat):
    if arbre is not None:
        suffixe(arbre.gauche, resultat) # 1. gauche
        suffixe(arbre.droit, resultat)  # 2. droit
        resultat.append(arbre.valeur)   # 3. racine

On appelle par exemple prefixe(arbre, res) avec une liste res initialement vide, qui contiendra l'ordre de visite à la fin.

Le parcours en largeur ne s'écrit pas naturellement par récursivité : il utilise une file (FIFO). On y place la racine, puis tant que la file n'est pas vide on en retire un nœud, on le traite et on enfile ses enfants.

from collections import deque

def largeur(arbre):
    if arbre is None:
        return []
    resultat = []
    file = deque([arbre])           # on enfile la racine
    while file:
        noeud = file.popleft()      # on defile (FIFO)
        resultat.append(noeud.valeur)
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droit is not None:
            file.append(noeud.droit)
    return resultat

Sur l'arbre précédent, ce parcours renvoie [1, 2, 3, 4, 5] : niveau par niveau. Comme chaque nœud est enfilé et défilé une seule fois, le coût est $O(n)$.

La propriété d'ordre permet de diviser l'espace de recherche par deux à chaque étape : si la valeur cherchée est plus petite que celle du nœud courant, on descend à gauche ; sinon à droite. On n'explore jamais les deux sous-arbres.

def recherche(arbre, x):
    if arbre is None:           # arbre vide : valeur absente
        return False
    if x == arbre.valeur:
        return True
    elif x < arbre.valeur:
        return recherche(arbre.gauche, x)   # on descend a gauche
    else:
        return recherche(arbre.droit, x)    # on descend a droite

Insérer revient à descendre dans l'arbre comme pour une recherche, jusqu'à trouver une place vide (None) où accrocher le nouveau nœud. On respecte ainsi automatiquement la propriété d'ordre.

def inserer(arbre, x):
    if arbre is None:                  # place libre trouvee
        return Noeud(x)
    if x < arbre.valeur:
        arbre.gauche = inserer(arbre.gauche, x)
    elif x > arbre.valeur:
        arbre.droit = inserer(arbre.droit, x)
    # si x == arbre.valeur, on ne l'insere pas (pas de doublon)
    return arbre

# Construction d'un ABR a partir d'une liste :
racine = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    racine = inserer(racine, v)

La fonction renvoie la racine du sous-arbre (éventuellement nouveau) : c'est le motif récursif classique qui permet de « recoller » l'arbre modifié. L'insertion a le même coût que la recherche, soit $O(h)$ où $h$ est la hauteur, c'est-à-dire $O(\log n)$ en moyenne et $O(n)$ dans le pire cas.