adplus-dvertising

Exercices corrigés sur les arbres - TD 2

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
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, [], []]]]
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, [], []]]]
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
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.