Parcours d'un arbre

On décide de prendre l'implémentation des arbre donné ci-dessous :

class Arbre:
    def __init__(self,valeur):
        self.v=valeur
        self.fg=None
        self.fd=None
    def ajout_gauche(self,val):
        self.fg=Arbre(val)
    
    def ajout_droit(self,val):
        self.fd=Arbre(val)
        
    def affiche(self):
        """permet d'afficher un arbre"""
        if self==None:
            return None
        else :
            return [self.v,Arbre.affiche(self.fg),Arbre.affiche(self.fd)]
    def taille(self):
        if self==None:
            return 0
        else :
            return 1+Arbre.taille(self.fg)+Arbre.taille(self.fd)
    def hauteur(self):
        if self==None:
            return 0
        elif self.fg==None and self.fd==None:
            return 0
        else : 
            return 1+max(Arbre.hauteur(self.fg),Arbre.hauteur(self.fd))
    def get_valeur(self):
        if self==None:
            return None
        else:
            return print(self.v)
                

Prise en main de l'implémentation

  1. Implémenter cet arbre :

    un arbre
  2. Tester les différentes méthodes sur cet arbre.

Parcours en profondeur : infixe, préfixe et suffixe

Dans cette partie, nous allons aborder les parcours en profondeur. Il existe trois manières de parcourir un arbre en profondeur comme nous allons le voir. L'idée de ces parcours, c'est de descendre tout en bas de l'arbre avant de se déplacer vers la droite de l'arbre.

Ces parcours sont parfois notés DPS pour Depth-First Search.

Ces parcours serviront à réaliser des algorithme de recherche textuelle par exemple ou à gérer des "AI" de jeux vidéos.

Parcours préfixe

Dans ce parcours on note tous les nœuds en commençant par la racine puis les deux sous arbres.

Réaliser à la main le parcours préfixe de cet arbre :

un abre

Algorithme du parcours préfixe.

voila la méthode écrite en Python du parcours préfixe d'un arbre de recherche:

 def dfs_prefixe(self):
    if self==None:
        return None
    else :
        Arbre.get_valeur(self)
        Arbre.dfs_prefixe(self.fg)
        Arbre.dfs_prefixe(self.fd)

            

Parcours infixe

Dans ce parcours on note tous les nœuds en commençant par le sous arbre gauche puis la racine puis le sous arbre droit.

Réaliser à la main le parcours infixe de cet arbre :

un abre

Ecrire l'algorithme du parcours infixe.

Parcours suffixe

Dans ce parcours on note tous les nœuds en commençant par le sous arbre gauche puis le sous arbre droit et enfin la racine .

Réaliser à la main le parcours suffixe de cet arbre :

un abre

Ecrire l'algorithme du parcours suffixe.

Parcours en largeur d'abord

Dans cette partie, nous allons aborder les parcours en largeur.

Ce parcours est parfois noté BFS pour Breadth-First Search.

Parcours en largeur

Quand on parcourt en largeur un arbre, on note chaque sommet niveau par niveau et en commençant par la gauche.

le parcours en largeur de cet arbre :

un autre arbre

est : 8-5-7-9-3-5-1

On reprend l'implémentation de file vu dans SD3

class Element:
    #chaque élément a pour attribut : le precedent , le suivant et la valeur de l'élément
    def __init__(self,x):
        self.val=x
        self.precedent=None
        self.suivant=None
    def __str__(self): #methode qui permet de lance un print sur un tel objet
        return str(self.val)+"-"+str(self.suivant)

l'objet file :

class File:
    #ici une file est la donnée de deux attributs : la file complète de type Element et le dernier élément de la file de type Element 
    def __init__(self):
        self.tete=None
        self.queue=None
    def enfile(self,x):
        e=Element(x) #on transforme l'élément à ajouter en un objet Element de listes doublement Chainées
        if self.tete==None:
            self.tete=e #file vide la tete est remplacée par l'élément e
        else:
            e.precedent=self.queue #le précédent de l'élément pointe sur l'ancienne queue de la file
            self.queue.suivant=e #l'ancienne queue de la file pointe sur e avec suivant
        self.queue=e #on redéfinit self.queue par e.
        
    def file_vide(self):
        return self.tete is None #renvoie True si None et False sinon
    
    def defile(self):
        if not self.file_vide():
            e=self.tete #on stocke l'élément à defiler
            if e.suivant is None: #cas où il n'y a qu'un élément 
                self.tete=None
                self.queue=None
            else:
                self.tete=e.suivant
                self.tete.precedent=None
            return e.val
        
    def __str__(self):
        return str(self.tete)

Algorithme BFT

def BFT(arbre):
    f=File()
    f.enfile(arbre)
    l=[]
    while not f.file_vide():
        a=f.defile()
        l.append(a.v)
        if a.fg!=None:
            f.enfile(a.fg)
        if a.fd!=None:
            f.enfile(a.fd)
    return l

Tester l'algorithme sur cet arbre :

Algorithmes des arbres binaires de recherche

Voila l'implémentation des arbres binaires de recherche que nous avons vu dans sd4

class ABR:
    def __init__(self,valeur,fg=None,fd=None):
        self.v=valeur
        self.fg=fg
        self.fd=fd
     def ajoute(self,valeur):
        if self==None:
            return ABR(valeur,None,None)
        elif valeur<self.v:
            return ABR(self.v,ABR.ajoute(self.fg,valeur),self.fd)
        else:
            return ABR(self.v,self.fg,ABR.ajoute(self.fd,valeur))
     def affiche(self):
        if self==None:
            return None
        else :
            return [self.v,ABR.affiche(self.fg),ABR.affiche(self.fd)]

Implémenter l'arbre suivant :

un arbre binaire de recherche

Recherche d'une clé

Ecrire la méthode recherche(self,val) qui renvoie True si val est une clé de l'arbre et False sinon.

Le principe ici est celui de la dichotomie. On élimine grâce à la structure des arbres binaires de recherche la moitié des nœuds restant à chaque étape.

Insérer une clé

La méthode qui insère un élément dans un arbre binaire de recherche est déjà écrite. Quelle est-elle?

Commenter cette méthode.

Exercices

Ecrire une méthode min(self) qui renvoie la clé minimale d'un arbre.

Ecrire une méthode max(self) qui renvoie la clé maximale d'un arbre.

Donner tous les arbres binaires de recherche formés des trois nœuds : 7, 52, 40

Ecrire une fonction listeEnArbre(l) qui en paramètre reçoit une liste d'entiers et qui renvoie un arbre binaire de recherche contenant les éléments de la liste l.

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International