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 algorithmes de recherche textuelle par exemple ou à gérer des "AI" de jeux vidéos.

Pour retenir le nom différent entre ces trois parcours, il suffit de retenir la position de la racine dans chaque des parcours :

• "préfixe" : la racine est avant ses sous-arbres ; "pré" comme précéder.

• "infixe" : la racine est entre ses sous-arbres ; "in" comme intérieur.

• "suffixe" : la racine est après ses sous-arbres ; "su" comme succéder.

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

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

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

class Element:

    #chaque élément (d'une liste doublement chaînée) a pour attribut : le précédent , 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): # méthode qui permet d\'afficher un tel objet grâce à un print
        return str(self.val) + "<-" + str(self.suivant)

l'objet file :

class File:

    # ici une file est la donnée de deux attributs : 
    # la queue de la file de type Element et le premier élément de la file (la tête) de type Element 
    # l'éventuel corps de la file sera progressivement atteinte grâce aux attributs precedent et suivant des objets de la classe Element 
    # precedent sert à remonter vers la tête, suivant à descendre vers la queue.
    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 initiale 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)

Le précédent algorithme BFS de parcours en largeur consiste à chaque Noeud étudié de noter sa valeur puis de mettre en mémoire le fait qu'il faudra visiter ses enfants après les noeuds qu'il était déjà prévu de visiter : d'où l'utilisation d'une file de mémorisation pour un parcours en largeur.

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)]

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.