Arbres binaires de recherche

class ABR(Arbre_b): 
    def __init__(self, racine = None): 
        super().__init__(racine)

Solution récursive :

La classe Arbre_br n’étant en elle même pas structurellement récursive, on imbrique une fonction récursive m (portant sur les nœuds de l’arbre) à l’intérieur des méthodes min et max :

def min(self):
    """ Renvoie la plus petite valeur de l'arbre """
    def m(n):
        if n.g is not None:
            return m(n.g)
        return n
    return m(self.racine)


def max(self):
    """ Renvoie la plus grande valeur de l'arbre """
    def m(n):
        if n.d is not None:
            return m(n.d)
        return n
    return m(self.racine)

Solution itérative :

def min(self):
    n = self.racine
    p = None
    while n is not None:
        p = n
        n = n.g
    return p

def max(self):
    n = self.racine
    p = None
    while n is not None:
        p = n
        n = n.d
    return p

def chercher(self, v):
    """ Renvoie le Noeud de valeur v
        None si aucun noeud n'a cette valeur
    """
    n = self.racine
    while n is not None:
        if v > n.v:
            n = n.d
        elif v < n.v:
            n = n.g
        else:
            return n

On peut décomposer en implémentant une méthode chercher_plu-proche, très proche de chercher, mais qui renvoie None si le nœud de valeur v existe déjà (on ne doit pas avoir deux nœuds de même valeur dans l’ABR) :

def chercher_plus_proche(self, v):
    n = self.racine
    p = None
    while n is not None:
        if v < n.v:
            p = n
            n = n.g
        elif v > n.v:
            p = n
            n = n.d
        else:
            return
    return p

Ou tout intégrer dans une unique méthode :

def inserer(self, v):
    """ Insère un nouveau Noeud de valeur v dans l'arbre
        (version itérative)
    """
    if self.racine is None:
        self.racine = Noeud_b(v)

    else:
        n = self.racine
        while n is not None:
            if v < n.v:
                if n.g is None:
                    n.g = Noeud_b(v)
                    return
                n = n.g

            elif v > n.v:
                if n.d is None:
                    n.d = Noeud_b(v)
                    return
                n = n.d

            else:
                return # clé déjà dans l'arbre

def supprimer(self, v):
    """ Supprime le Noeud de valeur v dans l'arbre
        (s'il existe)
    """
    n = self.racine
    p = None  # Père de n
    continuer = True
    while n is not None and n.v != v:
        p = n
        if v > n.v:
            n = n.d
        else: # Remarque : le cas n.v == v ne peut pas se produire ici
            n = n.g

    if p is not None and n is not None:
        if n.d is None and n.g is None:  # Feuille
            if n.v < p.v:
                p.g = None
            else:
                p.d = None
                
        elif n.d is None:                # Fils unique à gauche
            if p.v < n.v:
                p.g = n.d
            else:
                p.d = n.d
        elif n.g is None:                # Fils unique à droite
            if p.v < n.v: 
                p.d = n.d 
            else: 
                p.d = n.g        
        
        else:                            # 2 fils
            # on cherche le plus grand noeud à gauche (noeud à déplacer m) et son père p
            m = n.g
            p = n
            while m.d is not None:
                p = m
                m = m.d
            n.v = m.v # On remplace la valeur du noeud supprimer par celle du noeud à déplacer
            # On supprime la référence du noeud à déplacer (lien père-fils)
            if m.v < p.v: # il est à gauche de son père p
                p.g = m.g
            else:         # il est à droite de son père p
                p.d = m.g