Théorie des graphes

Insertion et suppression d'un élément de l'arbre binaire

Insertion dans un arbre binaire

L'idée est de faire un parcours en largeur itératif de l'arbre donné en utilisant une file d'attente

            inserer(val)
                1) nouveau=Noeud(val) /* créer un noeud */
                1) Créer une file d'attente vide file
                2) temp_node = Noeud / * commencer à partir de la racine * /
                3) Tanque temp_node n'est pas NUL
                         a) SI temp_node.gauche est NUL ALORS
                            temp_node.gauche=nouveau
                            retourne
                         b) SINON SI temp_node.gauche est NUL ALORS
                            temp_node.droit=nouveau
                            retourne
                            FINSI
                         c) Mettre en file d'attente file les enfants de temp_node (enfants gauche, puis enfant droit)
                         d) Retirer un noeud de file et l’attribuer à temp_node
            
                class Noeud:
                    def __init__(self, key):
                        self.gauche = None
                        self.droit = None
                        self.val = key                
                

                def Inserer(Noeud, val):
                    nouveau=Noeud(val)
                    file = []
                    file.append(Noeud)
                
                    while(len(file) > 0):
                        # retirer l'élément en tête de la file
                        node = file.pop(0)

                        # si l'enfant gauche est vide
                        if node.gauche is None:
                            node.gauche=nouveau
                            break

                        # si l'enfant droit est vide
                        elseif node.droit is None:
                            node.gauche=nouveau
                            break
                        else:
                            file.append(node.gauche)
                            file.append(node.droit)
                    
                # tester la fonction 
                racine = Noeud(30) 
                racine.gauche = Noeud(16) 
                racine.droit = Noeud(40) 
                racine.gauche.gauche = Noeud(9) 
                racine.gauche.droit = Noeud(20)
                racine.insert(5) 
                

Suppression d'un noeud dans un arbre binaire

Dans un arbre binaire, supprimer un noeud d'un arbre binaire consiste à remplacer le noeud a supprimer par le noeud le plus profond à l'extrême droite

L'idée est de faire un parcours en largeur de l'arbre donné en utilisant une file d'attente pour retrouver le noeud à l'extrême droite et le noeud à supprime

                1) En partant de la racine, recherchez le nœud le plus profond à l'extrême droite d'arbre binaire et le nœud à supprimé.
                2) Remplacez les données du nœud de l'extrême droite par le nœud a supprimer.
                3) Supprimez ensuite le nœud le plus profond à l'extrême droite.
            
                
                class Noeud:
                    def __init__(self, key):
                        self.gauche = None
                        self.droit = None
                        self.val = key
                
                
                # retourner le noeud à l'extereme droit avec son parent
                def noeudExtreme(noeud):
                    file = []
                    file.append(noeud.droit)
                    node = None
                    parent = noeud
                    while (len(file) > 0):
                        node = file.pop(0)
                
                        # ajouter l'enfant gauche de l'élément retiré
                        if node.gauche is not None:
                            file.append(node.gauche)
                
                        # ajouter l'enfant droit de l'élément retiré
                        if node.droit is not None:
                            file.append(node.droit)
                        parent = noeud
                
                    return (node, parent)
                
                # trouver le noeud a supprimer
                def TrouverNoeud(noeud, cle):
                    file = []
                    file.append(noeud)
                    node = None
                    while (len(file) > 0):
                        node = file.pop(0)
                        if node.val == cle:
                            return node
                
                        # ajouter l'enfant gauche de l'élément retiré
                        if node.gauche is not None:
                            file.append(node.gauche)
                
                        # ajouter l'enfant droit de l'élément retiré
                        if node.droit is not None:
                            file.append(node.droit)
                
                # afficher les noeuds
                def afficher(noeud):
                    file = []
                    file.append(noeud)
                    node = None
                    while (len(file) > 0):
                        node = file.pop(0)
                        print(node.val)
                
                        # ajouter l'enfant gauche de l'élément retiré
                        if node.gauche is not None:
                            file.append(node.gauche)
                
                        # ajouter l'enfant droit de l'élément retiré
                        if node.droit is not None:
                            file.append(node.droit)
                
                
                def suppression(noeud, cle):
                    assert noeud != None
                
                    extreme, parent = noeudExtreme(noeud)
                    elm = TrouverNoeud(noeud, cle)
                
                    if elm is not None:
                        elm.val = extreme.val
    
                        # supprimer le nœud le plus profond à l'extrême droite
                        if parent.gauche == extreme.val:
                            parent.gauche = None
                        else:
                            parent.droit = None
                
                
                racine = Noeud(30)
                racine.gauche = Noeud(16)
                racine.droit = Noeud(40)
                racine.gauche.gauche = Noeud(9)
                racine.gauche.droit = Noeud(20)
                suppression(racine, 9)
            


Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :