Exercices corrigés sur les arbres - TD 3

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
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)

T2

T1

 memeniveau(T1, 0)
False
 memeniveau(T2, 0)
True
Solution
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
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))

                                                

Partager ce cours avec tes amis :

Rédigé par ESSADDOUKI Mostafa

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Commentaire(s)