Supprimer un noeud de l'arbre binaire de recherche

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

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

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter