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

Exercice 1

Étant donné un arbre binaire, trouvez la somme de toutes les feuilles.

Exemple(s)

somme_feuilles(abr)
La somme des nœuds feuilles est : 15

Solution

Python

def somme_feuilles(a):
    # Ici le cas de base, ca veut dire l'enfant d'une feuille, puisque une feuille
    # n'a pas d'enfant retourner 0
    if len(a) == 0:
        return 0
    # si il s'agit d'une feuille [val,[],[]]
    # le noeud n'a pas d'enfant gauche [] et d'enfant droit []
    elif len(a[1]) + len(a[2]) == 0:
        return a[0]
    else:
        # Sinon retourner le nombre d'enfants de sous arbre gauche a[1] et sous arbre droit a[2]
        return somme_feuilles(a[1]) + somme_feuilles(a[2])


a2 = [19, [42, [], [17, [10, [], []], []]], [15, [35, [], []], [12, [], []]]]
print(somme_feuilles(a2))

Exercice 2

Étant donné un arbre binaire, vérifiez si toutes les feuilles sont au même niveau ou non.

Exemple(s)

memeniveau(T1, 0)
False
memeniveau(T2, 0)
True

Solution

Python

niveau = -1


def memeniveau(a, l):
    global niveau
    # arbre est vide
    if len(a) == 0:
        return True
    # si il s'agit d'une feuille [val,[],[]]
    # le noeud n'a pas d'enfant gauche [] et d'enfant droit []
    elif len(a[1]) + len(a[2]) == 0:
        if niveau < 0:
            niveau = l
            return True
        return l == niveau
    else:
        return memeniveau(a[1], l+1) and memeniveau(a[2], l+1)


a2 = [19, [42, [], [17, [], []]], [15, [35, [], []], [12, [], []]]]

print(memeniveau(a2, 0))

Exercices 3

Étant donné un arbre binaire et deux noeuds «a» et «b», déterminez si les deux noeuds sont cousins l’un de l’autre ou non.
Deux noeuds sont cousins l’un de l’autre s’ils sont au même niveau et ont des parents différents.

Exemple(s)

cousins(a2, 4, 1)
True
cousins(a2, 3, 5)
False

Solution

Python

def cheminTonoeud(a, chemin, val):

    # si l'arbre est vide
    if a == []:
        return False

    # Ajouter le noeud dans le chemin
    chemin.append(a[0])

    # Si la racine a la même valeur que val, retourner True
    if a[0] == val:
        return True

    # Vérifier si val se trouve dans le sous-arbre gauche ou droit
    if cheminTonoeud(a[1], chemin, val) or cheminTonoeud(a[2], chemin, val):
        return True

    # S'il n'est pas présent dans le sous-arbre enraciné avec "a",
    # supprimez la racine du chemin et retourner False
    chemin.pop()
    return False


def cousins(a, val1, val2):
    if a == []:
        return False
    chemin1 = []  # stocker le chemin vers val1
    chemin2 = []  # stocker le chemin vers val2

    # calculer le chemin vers val1
    cheminTonoeud(a, chemin1, val1)
    # calculer le chemin vers val2
    cheminTonoeud(a, chemin2, val2)

    # Si chemin1==chemin2 (dans le même niveau) et il ont des parent différents
    # retourner True
    if len(chemin1) == len(chemin2) and (chemin1[-2] != chemin2[-2]):
        return True

    return False


a2 = [40, [14, [5, [3, [], []], [2, [], []]], [4, [], []]], [6, [1, [], []], [5, [], []]]]

print(cousins(a2, 4, 1))
print(cousins(a2, 3, 5))

Exercices corrigés sur les arbres - TD 3