Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Supprimer un noeud de l'arbre binaire de recherche

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

Feuille

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

Le noeud a un fils unique

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

Le noeud à supprimer a deux enfants

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)

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :