TP4 : programmation orientée objet et algorithmes - les arbres

Nous allons travailler sur les arbres. Tous les arbres vus ici seront binaires, et définis par les règles suivantes.


Définition : un arbre, c’est …


  • ou bien une valeur – qu’on appellera « feuille »,
  • ou bien un couple (fils gauche, fils droit) – qu’on appellera « nœud », les deux fils étant des arbres,
  • ou bien, cas particulier : l’arbre vide.

 


Exo 1 : création des arbres


Écrire une classe « tree » (vide dans un premier temps), et écrire trois fonctions :


  1. init_tree_1()
  2. init_tree_2(value)
  3. init_tree_3(left,right)

Qui devront retourner respectivement un arbre vide, une feuille, et un nœud.


 


À partir de ce code, écrire le constructeur __init__(self, …) de la classe « tree » de manière à pouvoir construire toutes sortes d’arbres :


t0 = tree() # crée un arbre vide
t1 = tree(tree(1),tree(tree(2),tree(4))) # crée un arbre avec 3 feuilles

Exo 2 : fonctions de base


Écrire une méthode « height » qui permet d’avoir la hauteur d’un arbre (chemin le plus long entre la racine et une feuille). NB : la hauteur de l’arbre vide est zéro ; la hauteur d’un arbre réduit à une feuille est 1.


t1.height() # doit donner 2

Écrire une méthode « leafcount » qui donne le nombre de feuilles d’un arbre.


 


Exo 3 : recherche dans un arbre


Écrire une fonction qui recherche un élément dans un arbre :


t1.search(5) # False
t1.search(4) # True

Puis, écrire une fonction « map » qui applique une fonction sur toutes les feuilles de l’arbre :


def add10(x): return x+10
t1.map(add10) # doit ajouter 10 à chaque feuille de l'arbre. NB: si les feuilles ne sont pas des nombres, ça plante !

Exo 4 : itération


On souhaite pouvoir écrire « for v in t1.values(): … » afin d’itérer sur toutes les feuilles de l’arbre.


Pour cela, écrire une fonction génératrice « values » dans la classe « tree ».


Commencer par écrire une fonction qui affiche (avec print) chaque valeur de l’arbre ; puis … simplement remplacer print par yield.


 


Écrire ensuite une fonction nodes() qui itère sur les nœuds de l’arbre (et qui retourne donc des objets de la classe tree, au lieu de retourner les valeurs stockées dans l’arbre).


 


Réécrire la fonction search et la fonction map avec ces fonctions.