Exercices corrigés sur les arbres - TD 2 | Développement Informatique

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

Python

# 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

Python

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

Python

def miroir(a):
    if len(a) == 0:
        return []
    else:
        return [a[0], miroir(a[2]), miroir(a[1])]

print(miroir(a))

Exercices corrigés sur les arbres - TD 2