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 
    #   la tête (le premier élément) de la file 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 sachant que :
    #   precedent sert à remonter vers la tête de la File
    #   tandis que suivant sert à descendre vers la queue de la File.
    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 chaînées
        if self.tete is 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 Nœud étudié de noter sa valeur puis de mettre en mémoire le fait qu'il faudra visiter ses enfants après les nœuds 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 is 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 is 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.