In [ ]:
Nom = ""
Prénom = ""

Python 10 - Parcours dans un arbre binaire¶

Dans Python 9, nous avons essentiellement construit des arbres binaires. Dans cette activité, nous allons d'abord voir les différentes façons de parcourir la totalité d'un arbre binaire. Ensuite, nous verrons comment spécifier un noeud et atteindre ce noeud.

Commençons par récupérer la classe Noeud ainsi que quelques fonctions utiles :

In [ ]:
import json, hashlib

class Noeud:
    
    def __init__(self, gauche, valeur, droit):
        self.gauche = gauche
        self.v = valeur
        self.droit = droit

    def __repr__(self):
        return json.dumps(obj2list(self))
    
    def __eq__(self, noeud):
        return noeud is not None and noeud.gauche == self.gauche and noeud.droit == self.droit


def obj2list(racine):
    if racine is None:
        return None
    return [obj2list(racine.gauche), racine.v, obj2list(racine.droit)]

def list2obj(l):
    if l is None:
        return None
    gauche, v, droit = l
    return Noeud(list2obj(gauche), v, list2obj(droit))

def obtenir_arbre(s):
    return list2obj(json.loads(s))

def hash(s):
    """
    Renvoie la version hashée de la chaine de caractères s
    :param s: (str) la chaine de carcatères à hasher
    :return: (bytes array) la version hashée, sous forme de tableau d'octets
    """
    return hashlib.md5(s.encode()).digest()

1 - Parcours de l'intégralité d'un arbre binaire¶

a - Les différents types de parcours¶

Nous allons voir quatre types de parcours :

  • le parcours en largeur : l'arbre est parcouru par ligne de gauche à droite (une ligne étant formée par les noeuds à la même distance de la racine), et en partant de la racine.
  • trois parcours en profondeur :
    • le parcours infixe : pour chaque noeud, nous parcourons d'abord l'arbre gauche, nous stockons la valeur du noeud, puis nous parcourons l'arbre droit ;
    • le parcours préfixe : pour chaque noeud, nous stockons d'abord la valeur du noeud, nous parcourons l'arbre gauche, puis nous parcourons l'arbre droit ;
    • le parcours suffixe : pour chaque noeud, nous parcourons d'abord l'arbre gauche, nous parcourons l'arbre droit puis nous stockons la valeur du noeud ;

Par exemple, parcourons l'arbre suivant :

L'ordre de stockage des noeuds est le suivant :

  • parcours infixe : 8, 4, 2, 6, 5, 7, 1, 3 ;
  • parcours préfixe : 1, 2, 4, 8, 5, 6, 7, 3 ;
  • parcours suffixe : 8, 4, 6, 7, 5, 2, 3, 1 ;
  • parcours en largeur : 1, 2, 3, 4, 5, 8, 6, 7.

Exercice

Dans cet arbre, chaque noeud correspond à un chiffre. En parcourant cet arbre, vous formez donc une chaine de 10 caractères (sans espaces ni virgules).

Complèter dans la cellule suivante les chaines de caractères correspondants aux différents parcours :

In [ ]:
parcours_largeur = ''
parcours_infixe = ''
parcours_suffixe = ''
parcours_prefixe = ''

# Insérez votre code ici
In [ ]:
assert (hash(parcours_largeur) == b'Ht7\xb9\xca&\x9e\x17YT\xf73n\xa9\x8eT'), "Largeur faux"
assert (hash(parcours_infixe) == b'\xdf\xa8\xf7\xcb\x19kY\x18\xe4\xb5\xf9\x9b\x98O\x98\xe7'), "Infixe faux"
assert (hash(parcours_suffixe) == b'\x16\rN\xf4\x13g\xebQc\x00\x7fi\x83h+;'), "Suffixe faux"
assert (hash(parcours_prefixe) == b').-\xfdDW\xda{\xf1\xfe\xe6\x15\xc0\x19\xe3\x9c'), "Préfixe faux"

b - Implémentation du parcours infixe¶

Nous allons définir une fonction infixe qui prend en argument un arbre (c'est à dire sa racine) et remplit une liste pile avec les valeurs de ses noeuds. La variable pile est globale.

In [ ]:
def infixe(racine):
    """
    Stocke dans une pile les valeurs de l'arbre avec un parcours infixe
    :param racine: (objet Noeud) la racine de l'arbre
    :return: None
    :se: rajoute des valeurs à la pile (side-effect)
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, '5', None], '3', None], '1', [None, '4', [None, '6', None]]], '0', [None, '2', [[None, '8', None], '7', [None, '9', None]]]]
racine = list2obj(arbre_liste)
pile = []
infixe(racine)
assert hash(''.join(pile)) == b'\xdf\xa8\xf7\xcb\x19kY\x18\xe4\xb5\xf9\x9b\x98O\x98\xe7'

c - Implémentation du parcours suffixe¶

Nous allons définir une fonction suffixe qui prend en argument un arbre (c'est à dire sa racine) et remplit une liste pile avec les valeurs de ses noeuds. La variable pile est globale.

In [ ]:
def suffixe(racine):
    """
    Stocke dans une pile les valeurs de l'arbre avec un parcours suffixe
    :param racine: (objet Noeud) la racine de l'arbre
    :return: None
    :se: rajoute des valeurs à la pile (side-effect)
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, '5', None], '3', None], '1', [None, '4', [None, '6', None]]], '0', [None, '2', [[None, '8', None], '7', [None, '9', None]]]]
racine = list2obj(arbre_liste)
pile = []
suffixe(racine)
assert hash(''.join(pile)) == b'\x16\rN\xf4\x13g\xebQc\x00\x7fi\x83h+;'

d - Implémentation du parcours préfixe¶

Nous allons définir une fonction prefixe qui prend en argument un arbre (c'est à dire sa racine) et remplit une liste pile avec les valeurs de ses noeuds. La variable pile est globale.

In [ ]:
def prefixe(racine):
    """
    Stocke dans une pile les valeurs de l'arbre avec un parcours préfixe
    :param racine: (objet Noeud) la racine de l'arbre
    :return: None
    :se: rajoute des valeurs à la pile (side-effect)
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, '5', None], '3', None], '1', [None, '4', [None, '6', None]]], '0', [None, '2', [[None, '8', None], '7', [None, '9', None]]]]
racine = list2obj(arbre_liste)
pile = []
prefixe(racine)
assert hash(''.join(pile)) == b').-\xfdDW\xda{\xf1\xfe\xe6\x15\xc0\x19\xe3\x9c'

e - Implémentation du parcours en largeur¶

Nous allons définir une fonction largeur qui prend en argument une liste de noeuds (formant une ligne) et remplit une liste pile avec les valeurs de ses noeuds. La variable pile est globale.

La première ligne d'un arbre est toujours [racine]. La liste correspondant à la ligne suivante sera complétée au fur et à mesure en parcourant l'arbre.

In [ ]:
def largeur(ligne):
    """
    Stocke dans une pile les valeurs de l'arbre avec un parcours en largeur
    :param ligne: (list) une liste de noeuds formant une ligne
    :return: None
    :se: rajoute des valeurs à la pile (side-effect)
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, '5', None], '3', None], '1', [None, '4', [None, '6', None]]], '0', [None, '2', [[None, '8', None], '7', [None, '9', None]]]]
racine = list2obj(arbre_liste)
pile = []
largeur([racine])
assert hash(''.join(pile)) == b'Ht7\xb9\xca&\x9e\x17YT\xf73n\xa9\x8eT'

2 - Parcours vers un noeud¶

Dans un arbre binaire, chaque noeud peut être identifié par un nombre binaire avec les règles suivantes :

  • la racine correspond au nombre 0b1 ;
  • le nombre du noeud de gauche est celui du noeud avec un 0 à gauche (multiplication par deux) ;
  • le nombre du noeud de droite est celui du noeud avec un 1 à gauche (multiplication par deux plus un) ;

Par exemple, si un noeud correspond au nombre 0b10010, son noeud de gauche correspondra à 0b100100 et son noeud de droite 0b100101.

Autre exemple, l'arbre de la partie précédente avec les nombres indiqués dans chaque noeud :

Exercice

Dans l'arbre donné en exemple au début de ce notebook :

  • quel est le nombre correspondant au Noeud8 ?
  • quel noeud correspond au nombre dont l'écriture décimale est 10 ?
In [ ]:
# Insérez votre code ici

a - Accès à un noeud¶

Implémenter une fonction obtenir_noeud qui prend en argument un nombre et un noeud (la racine de l'arbre) et renvoie le noeud correspondant à ce nombre.

In [ ]:
def obtenir_noeud(racine, nombre):
    """
    Obtenir un noeud identifié par son nombre binaire
    :param racine: (objet Noeud) la racine de l'arbre
    :param nombre: un nombre dont la représentation binaire correspond à un noeud de l'arbre
    :return: (objet Noeud) le noeud correspondant au nombre ou None s'il n'y en a pas
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, 5, None], 3, None], 1, [None, 4, [None, 6, None]]], 0, [None, 2, [[None, 8, None], 7, [None, 9, None]]]]
racine = list2obj(arbre_liste)
assert obtenir_noeud(racine, 0b1).v == 0
assert obtenir_noeud(racine, 0b10).v == 1
assert obtenir_noeud(racine, 0b11).v == 2
assert obtenir_noeud(racine, 0b1011).v == 6
assert obtenir_noeud(racine, 0b10010) is None

b - Rajout d'un noeud¶

Implémenter une fonction ajouter_feuille qui prend en argument un noeud racine, un nombre et la valeur du noeud à ajouter. Le nombre devra correspondre à un noeud inexistant mais situé à gauche ou à droite d'un noeud existant.

Dans le cas où les arguments ne permttent pas de rajouter une feuille à l'arbre, on utilisera une exception TreeError avec la syntaxe suivante :

raise TreeError("message d'erreur")
In [ ]:
class TreeError(Exception):
    
    def __init__(self, message):
        self.message = message

def ajouter_feuille(racine, nombre, valeur):
    """
    Ajoute un noeud à un arbre
    :param racine: (objet Noeud) la racine de l'arbre
    :param nombre: (int) le nombre correspondant à un noeud inexistant
    :param valeur: (quelconque) la valeur du nouveau noeud ajouté
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, 5, None], 3, None], 1, [None, 4, [None, 6, None]]], 0, [None, 2, [[None, 8, None], 7, [None, 9, None]]]]
racine = list2obj(arbre_liste)
ajouter_feuille(racine, 0b11100, 'feuille1')
assert obtenir_noeud(racine, 0b11100).v == 'feuille1'
ajouter_feuille(racine, 0b11101, 'feuille2')
assert obtenir_noeud(racine, 0b11101).v == 'feuille2'

test = False
try:
    ajouter_feuille(racine, 0b10010, 'feuille3')
except TreeError:
    test = True
assert test

test = False
try:
    ajouter_feuille(racine, 0b100, 'feuille4')
except TreeError:
    test = True
assert test

3 - Parcours d'une ligne¶

En utilisant la fonction obtenir_noeud, implémenter une fonction obtenir_ligne qui renvoie la liste de tous les noeuds d'une ligne d'un arbre binaire, dans l'ordre de celui le plus à gauche à celui le plus à droite.

In [ ]:
def obtenir_ligne(racine, n):
    """
    Renvoie la liste des noeuds de la ligne n
    :param racine: (objet Noeud) le noeud racine de l'arbre
    :param n: (int) le numéro de la ligne, 0 correspondant à la racine
    :return: (list) la liste des noeuds de la ligne
    """
    # Insérez votre code ici
In [ ]:
arbre_liste = [[[[None, '5', None], '3', None], '1', [None, '4', [None, '6', None]]], '0', [None, '2', [[None, '8', None], '7', [None, '9', None]]]]
racine = list2obj(arbre_liste)

l = obtenir_ligne(racine, 0)
assert len(l) == 1
assert l[0] is racine

l = obtenir_ligne(racine, 1)
assert len(l) == 2
assert l[0] is racine.gauche
assert l[1] is racine.droit

l = obtenir_ligne(racine, 3)
assert len(l) == 4
s = ''
for noeud in l:
    s += noeud.v
assert s == '5689'