Exercices corrigés sur les arbres - TD 2
Exercice 1
Écrivez une fonction qui retourne vrai si l'arbre binaire donné est SommeEnfants sinon faux. Un SommeEnfants est un arbre binaire où la valeur d'un nœud est égale à la somme des nœuds présents dans son sous-arbre gauche et son sous-arbre droit. Un arbre vide est SommeEnfants et la somme d'un arbre vide peut être considérée comme 0. Un nœud feuille est également considéré comme SommeEnfants.
Exemple(s)
SommeEnfants(a)
True
True
Solution
# Une fonction utilitaire pour obtenir la somme des valeurs # dans un arbre avec la racine "a" def somme(a): # Enfant d'une feuille ! if a == []: return 0 else: # somme des valeurs à gauche+racine+valeurs à droite return somme(a[1])+a[0]+somme(a[2]) # renvoie True si la propriété SommeEnfant est # vraie pour le nœud donné et ses deux enfants def SommeEnfant(a): # Si le nœud est vide [], retournez true if a == []: return True # S'il s'agit d'un nœud feuille, retournez true if a[1] == [] and a[2] == []: return True else: # somme des éléments de sous arbre gauche gauche = somme(a[1]) # somme des éléments de sous arbre droit droit = somme(a[2]) # si le nœud et ses deux enfants satisfont la propriété, # retourne True sinon False if a[0] == (gauche+droit) and (SommeEnfant(a[1]) == True and SommeEnfant(a[2]) == True): return True return False a0 = [17, [6, [3, [3, [], []], []], []], [5, [], []]] print(SommeEnfant(a0))
Exercice 2
Écrire une fonction créant un arbre complet (tous les niveaux sont remplis) d’une hauteur donnée. On s’efforcera de distribuer des étiquettes de facon injective.
Exemple(s)
complet(2,1)
[1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
[1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
Solution
def complet(hauteur, racine): if hauteur == 0: return [racine, [], []] else: return [racine, complet(hauteur-1, 2*racine), complet(hauteur-1, 2*racine+1)] print(complet(2,1))
Exercice 3
Écrire une fonction calculant le miroir d’un arbre donné (au sens d’une symétrie par rapport à un axe vertical).
Exemple(s)
a=[1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
miroir(a)
[1, [3, [7, [], []], [6, [], []]], [2, [5, [], []], [4, [], []]]]
miroir(a)
[1, [3, [7, [], []], [6, [], []]], [2, [5, [], []], [4, [], []]]]
Solution
def miroir(a): if len(a) == 0: return [] else: return [a[0], miroir(a[2]), miroir(a[1])] print(miroir(a))
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa