Nom = ""
Prénom = ""
Python 7 : les arbres binaires¶
1 - Définitions et vocabulaire¶
Les arbres binaires ressemblent aux listes chainées, mais là où un maillon d'une liste a un maillon suivant, un noeud d'un arbre binaire a deux noeuds suivants : le noeud droit et le noeud gauche.
On obtient une structure qui ressemble à ça :
Chaque noeud a deux sous-arbres : le sous-arbre droit, et le sous-arbre gauche.
Un arbre (et donc un sous-arbre) peut éventuellement être vide.
Tous les noeuds sauf un ont un noeud parent. Le noeud qui n'a pas de noeud parent est la racine de l'arbre.
Un noeud dont les deux sous-arbres sont vides est une feuille.
Par exemple, dans l'arbre ci-dessus, la racine est le noeud 1, les noeuds 3, 6 et 7 sont des feuilles.
La taille d'un arbre est le nombre de ses noeuds. L'arbre ci-dessus est par exemple de taille 8.
La hauteur d'un arbre est le nombre maximum de noeuds entre la racine et une feuille. L'arbre ci-dessus est par exemple de hauteur 4.
Un arbre dont tous les chemins de la racine aux feuilles ont la même longueur est dit parfait.
Un arbre dont tous les sous-arbres droits sont des feuilles est un peigne gauche.
Exercice 1: Tracer un peigne gauche de hauteur 5.
Exercice 2: Tracer un arbre parfait de hauteur 5.
Exercice 3: Tracer tous les arbres de tailles 3 et 4.
Exercice 4: Déterminer le nombre d'arbres de taille 5.
2 - Représentation en Python¶
On va représenter un noeud d'un arbre par un objet d'une classe Noeud. Chaque
noeud aura une valeur (attribut v) ainsi qu'un arbre gauche (attribut gauche)
et un arbre droit (attribut droit).
Proposer une définition pour la classe Noeud :
# Insérez votre code ici
De manière à pouvoir afficher un noeud, on ajoute une méthode __str__ avec
la cellule suivante :
from tree import to_string
Noeud.__str__ = to_string
arbre = Noeud(Noeud(None, 1, None), 0, Noeud(None, 2, None))
assert arbre.v == 0
assert arbre.gauche.v == 1
assert arbre.droit.v == 2
print(arbre)
Exercice : Définir en Python l'arbre suivant. On placera la racine dans la variable racine.
# Insérez votre code ici
print(racine)
assert racine.v == 5
assert racine.gauche.v == 9
assert racine.droit.v == 1
assert racine.gauche.gauche.v == 0
assert racine.gauche.gauche.gauche is None
assert racine.gauche.gauche.droit is None
assert racine.gauche.droit.v == 8
assert racine.gauche.droit.gauche.v == 4
assert racine.gauche.droit.droit.v == 3
assert racine.gauche.droit.gauche.droit is None
assert racine.gauche.droit.gauche.gauche is None
assert racine.gauche.droit.droit.droit is None
assert racine.gauche.droit.droit.gauche is None
Exercice : Définir une fonction peigne qui prend en argument en nombre n strictement positif et renvoie la racine d'un peigne gauche de taille n. Toutes les feuilles auront pour valeur 1 et les autres noeuds auront des valeurs de 1 à n. La racine aura pour valeur n :
┌─6─┐
┌─5─┐ 1
┌─4─┐ 1
┌3─┐ 1
┌2┐ 1
1 1 # Insérez votre code ici
print(peigne(6))
noeud = peigne(10)
for i in range(9):
assert noeud.v == 10 - i
assert noeud.droit.v == 1
assert noeud.droit.gauche is None
assert noeud.droit.droit is None
noeud = noeud.gauche
assert noeud.v == 1 and noeud.gauche is None and noeud.droit is None
3 - Taille d'un arbre¶
Définir une fonction récursive taille qui renvoie la taille d'un arbre.
def taille(racine):
# Insérez votre code ici
racine = Noeud(Noeud(Noeud(None, 2, None), 5, Noeud(Noeud(None, -7, None), 2, Noeud(None, 3, None))), 5, Noeud(None, 7, None))
assert taille(racine) == 7
4 - Hauteur d'un arbre¶
Définir une fonction récursive hauteur qui renvoie la hauteur d'un arbre.
def hauteur(racine):
# Insérez votre code ici
racine = Noeud(Noeud(Noeud(None, 2, None), 5, Noeud(Noeud(None, -7, None), 2, Noeud(None, 3, None))), 5, Noeud(None, 7, None))
assert hauteur(racine) == 4
5 - Des objets vers les listes¶
On veut pouvoir représenter un arbre par des listes imbriquées.
Un noeud sera représenté par une liste de 3 éléments : le premier sera le sous-arbre gauche, le deuxième la valeur du noeud et le troisième le sous-arbre droit.
Définir une fonction obj2list qui prend en argument un noeud de la classe Noeud et renvoie une représentation avec des listes de l'arbre dont il est racine.
def obj2list(racine):
"""
Transforme un arbre représenté par des noeuds
en le même arbre représenté par des listes
imbriquées
:param racine: (Objet Noeud) le noeud qui est la racine
:return: (list) la liste contenant toutes les autres
"""
# Insérez votre code ici
racine = Noeud(Noeud(Noeud(None, 2, None), 5, Noeud(Noeud(None, -7, None), 2, Noeud(None, 3, None))), 5, Noeud(None, 7, None))
assert obj2list(racine) == [[[None, 2, None], 5, [[None, -7, None], 2, [None, 3, None]]], 5, [None, 7, None]]
6 - Des listes vers les objets¶
Définir une fonction list2obj qui fait la transformation inverse de la fonction obj2list.
def list2obj(l):
"""
Transforme un arbre représenté par des listes
imbriquées en le même arbre représenté par des noeuds
:param racine: (list) la liste contenant toutes les autres
:return: (Objet Noeud) le noeud qui est la racine
"""
# Insérez votre code ici
l = [[None, 0, [None, 1, None]], 2, [None, 3, None]]
racine = list2obj(l)
assert racine.v == 2
assert racine.gauche.v == 0
assert racine.gauche.gauche is None
assert racine.gauche.droit.v == 1
assert racine.gauche.droit.gauche is None
assert racine.gauche.droit.droit is None
assert racine.droit.v == 3
assert racine.droit.gauche is None
assert racine.droit.droit is None
7 - Représentation par une chaine de caractères¶
Le module json (JavaScript Object Notation) permet de convertir des listes en chaines
de caractère et inversement (fonctions json.dumps et json.loads respectivement).
a - Vers la chaine de caractères¶
Utiliser la fonction json.dumps et la fonction obj2list pour définir une méthode
__repr__ à la classe Noeud.
def repr_tmp(self):
"""
Renvoie une représentation de l'arbre dont la racine est self
sous la forme d'une chaine de caractères
:return: (str) la représentation
"""
# Insérez votre code ici
Noeud.__repr__ = repr_tmp
import json
racine = Noeud(Noeud(Noeud(None, 2, None), 5, Noeud(Noeud(None, -7, None), 2, Noeud(None, 3, None))), 5, Noeud(None, 7, None))
assert repr(racine) == '[[[null, 2, null], 5, [[null, -7, null], 2, [null, 3, null]]], 5, [null, 7, null]]'
b - Vers l'arbre¶
Définir une fonction obtenir_arbre qui, à partir d'une chaine de caractères telle que
renvoyer par la méthode __repr__, renvoie un arbre défini avec des instances de la classe Noeud.
def obtenir_arbre(s):
"""
Renvoie un arbre représenté par des noeuds
à partir de sa représentation sous la forme d'une chaine de caractères
:param s: (str) la représentation
:return: (objet Noeud) la racine de l'arbre
"""
# Insérez votre code ici
import json
s = '[[null, 0, [null, 1, null]], 2, [null, 3, null]]'
racine = obtenir_arbre(s)
assert racine.v == 2
assert racine.gauche.v == 0
assert racine.gauche.gauche is None
assert racine.gauche.droit.v == 1
assert racine.gauche.droit.gauche is None
assert racine.gauche.droit.droit is None
assert racine.droit.v == 3
assert racine.droit.gauche is None
assert racine.droit.droit is None
8 - Égalité de deux arbres¶
Rajouter à la classe Noeud une méthode __eq__ qui permet de tester l'égalité de deux arbres avec l'opérateur ==.
def eq_tmp(self, noeud):
# Insérez votre code ici
Noeud.__eq__ = eq_tmp
import json
s = '[[null, 0, [null, 1, null]], 2, [null, 3, null]]'
racine1 = obtenir_arbre(s)
racine2 = obtenir_arbre(s)
assert racine1 == racine2
assert not racine1 == None
racine1.gauche.v = 4
assert racine1 != racine2
9 - Arbre parfait¶
Exercice : Définir une fonction parfait qui prend en argument en nombre n strictement positif et renvoie la racine d'un arbre parfait de hauteur n. La valeur des noeuds sera une chaine de caractères de la forme 'i-j' où i est la distance du noeud de la racine et j la distance du noeud le plus à gauche de la ligne (une ligne étant définie comme les noeuds ayant le même i).
def parfait(n, i = 0, j = 0):
# Insérez votre code ici
print(parfait(5))
racine = parfait(5)
assert repr(racine) == '[[[[[null, "4-0", null], "3-0", [null, "4-1", null]], "2-0", [[null, "4-2", null], "3-1", [null, "4-3", null]]], "1-0", [[[null, "4-4", null], "3-2", [null, "4-5", null]], "2-1", [[null, "4-6", null], "3-3", [null, "4-7", null]]]], "0-0", [[[[null, "4-8", null], "3-4", [null, "4-9", null]], "2-2", [[null, "4-10", null], "3-5", [null, "4-11", null]]], "1-1", [[[null, "4-12", null], "3-6", [null, "4-13", null]], "2-3", [[null, "4-14", null], "3-7", [null, "4-15", null]]]]]'