Supprimer un noeud de l'arbre binaire de recherche

Lorsque nous supprimons un noeud, trois possibilités se présentent.

Le noeud à supprimer est une feuille, il est terminal et il suffit de le retirer de l'arbre.

Le nœud à supprimer n'a qu'un seul enfant, on relie son fils à son père et on supprime le nœud .

L’élément à supprimer a deux fils : on le remplace par son successeur qui est toujours le minimum de ses descendants droits.

Notez que le prédécesseur peut également être utilisé (nœud de clé maximum dans le sous-arbre gauche du nœud).

class Noeud:
    def __init__(self, key):
        self.gauche = None
        self.droit = None
        self.val = key


def Successeur(noeud):
    courant = noeud
    while(courant.gauche is not None):
        courant = courant.gauche
    return courant


def Predecesseur(noeud):
    courant = noeud
    while(courant.droit is not None):
        courant = courant.droit
    return courant


def Supprimer(noeud, cle):
    if noeud is None:
        return

    # si cle est inférieure à la valeur du noeud, rechercher dans le sous-arbre gauche
    if cle < noeud.val:
        noeud.gauche = Supprimer(noeud.gauche, cle)

    # si cle est supérieure à la valeur du noeud, rechercher dans le sous-arbre droit
    elif(cle > noeud.val):
        noeud.droit = Supprimer(noeud.droit, cle)

    # sinon
    else:

        # noeud a un fils unique
        if noeud.gauche is None:
            temp = noeud.droit
            noeud = None
            return temp

        elif noeud.droit is None:
            temp = noeud.gauche
            noeud = None
            return temp

        # noeud a deux enfants
        succ = Successeur(noeud.droit)

        # le cas de prédécesseur
        # pred=Predecesseur(noeud.gauche)

        # remplacer la valeur du noeud à supprimer avec la valeur du successeur
        noeud.val = succ.val

        # supprimer le successeur
        noeud.droit = Supprimer(noeud.droit, succ.val)

        # le cas de prédecesseur
        #noeud.gauche = Supprimer(noeud.gauche, succ.val)

    return noeud


# parcours infixe
def infixe(noeud):
    if noeud == None:
        return
    if noeud.gauche != None:
        infixe(noeud.gauche)
    print(noeud.val)
    if noeud.droit != None:
        infixe(noeud.droit)


def inserer(noeud, val):
    if noeud is None:
        noeud = Noeud(val)
    else:
        if noeud.val < val:
            if noeud.droit is None:
                noeud.droit = Noeud(val)
            else:
                inserer(noeud.droit, val)
        else:
            if noeud.gauche is None:
                noeud.gauche = Noeud(val)
            else:
                inserer(noeud.gauche, val)


racine = Noeud(9)
inserer(racine, 5)
inserer(racine, 11)
inserer(racine, 3)
inserer(racine, 4)
inserer(racine, 7)
inserer(racine, 8)
inserer(racine, 6)

racine = Supprimer(racine, 5)
infixe(racine)