MP/TSI 23-24.
-
CPGE TETOUAN.- TP : Algorithmes de tri.
Informatique
Manipulation des arbres sous Python
Question 1: Représenter (crayon/papier !) et définir les arbres ci dessous en Python :
a0 = [15 , [] , []]
a1 = [18 , [12 , [] , [17 , [] , []]] , [30 , [15 , [] , []] , []]]
a2 = [19 , [42 , [] , [17 , [10 , [] , []] , []]] , [15 , [35 , [] , []] , [12 , [] , []]]]
NB : Toutes les fonctions seront testées sur les trois arbres ci dessous (et qu’on com-
mencera par traiter à la main).
Question 2:
— Écrire une fonction hauteur(a) calculant la hauteur d’un arbre binaire.
∗ hauteur(a1)
2
∗ list(map(hauteur, [a0, a1, a2]))
[0, 2, 3]
— une fonction nbNoeud(a) calculant le nombre de nœuds d’un arbre binaire.
∗ list(map(nbNoeud, [a0, a1, a2]))
[1, 5, 7]
— une fonction nbFeuille(a) calculant le nombre de feuilles d’un arbre binaire.
— une fonction recherche(a , x) qui recherche un élément x dans un arbre a
— isNoeudInterne (a) : determine si un nœud est un nœud interne
— nbNoeudsInterne(a) : calcule le nombre de nœuds interne de l’arbre a
— sumCleArbre(a) : retourne la somme des valeurs des nœuds
Question 3:
— Écrire une fonction parcours infixe(a) retournant la liste des étiquettes d’un arbre,
parcouru de façon infixe.
∗ list(map(parcours inf ixe, [a0, a1, a2]))
[[15], [12, 17, 18, 15, 30], [42, 10, 17, 19, 35, 15, 12]]
— Recommencer avec le parcours préfixe, puis avec le postfixe.
Page 1
— programmer le parcours en largeur
— Tester sur les trois arbres données au début du TD.
Question 4:
— Écrire une fonction créant un arbre complet(h , r) (tous les niveaux sont remplis)
d’une hauteur donnée. On s’efforcera de distribuer des etiquettes de façon injec-
tive(toutes différentes).
∗ complet(2, 1)
[1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
— Écrire une fonction calculant le miroir d’un arbre donnée (au sens d’une symétrie
par rapport à un l’axe vertical).
∗ miroir(complet(2, 1))
[1, [3, [7, [], []], [6, [], []]], [2, [5, [], []], [4, [], []]]]
Page 2
