C5 : Exercices

■ Arbres binaires

C5.E1 : Arbre représentant une expression arithmétique

Considérons l'arbre suivant :

1) Quelle est la particularité des nœuds qui sont des feuilles et des nœuds qui ne sont pas des feuilles ?

2) Écrire l'implémentation en python à base de tuples imbriqués de cet arbre.

3) Écrire une fonction récursive affiche(arb_expr) qui prend un arbre correspondant à une expression arithmétique en paramètre et renvoie une chaine de caractère contenant l'expression avec les parenthèses. Ainsi, la fonction affiche appliquée à l'arbre précédent doit renvoyer ((35 + 12) × (6 - 8)).

4) Écrire une fonction récursive calcul(arb_expr) qui prend un arbre correspondant à une expression arithmétique en paramètre et renvoie la valeur calculée de cette expression. Ainsi, la fonction calcul appliquée à l'arbre précédent doit renvoyer -94.

Afficher la correction 
def affiche(arb):
    if arb[1] == None and arb[2] == None:
        return str(arb[0])
    else:
        return "("+affiche(arb[1])+str(arb[0])+affiche(arb[2])+")"

def calcul(arb):
    if arb[1] == None and arb[2] == None:
        return arb[0]
    else:
        if arb[0] == "+":
            return calcul(arb[1]) + calcul(arb[2])
        elif arb[0] == "-":
            return calcul(arb[1]) - calcul(arb[2])
        elif arb[0] == "×" or arb[0] == "*":
            return calcul(arb[1]) * calcul(arb[2])
        elif arb[0] == "/":
            return calcul(arb[1]) / calcul(arb[2])

arbre = ("×",("+",(35,None,None),(12,None,None)),("-",(6,None,None),(8,None,None)))

print(affiche(arbre))
print(calcul(arbre))

C5.E2 : Analyse d'une fonction

A faire sans l'ordinateur

On considère des arbres binaires dont les valeurs sont des nombres entiers, implémentés à l'aide de tuples imbriqués (avec None si l'arbre est vide).

On s'intéresse à la fonction dont le code est donné ci-dessous.

def est_dans(arb, val):
    if arb == None :
        return False
    else:
        return arb[0] == val or est_dans(arb[1], val) or est_dans(arb[2], val)

1) Expliquer le mécanisme de cette fonction.

2) Écrire la docstring de cette fonction.

3) On propose une deuxième version de la fonction ci-dessous :

def est_dans(arb, val):
    if arb == None :
        return False
    elif arb[0] == val:
        return True
    else:
        return est_dans(arb[1], val) or est_dans(arb[2], val)

Indiquer, en justifiant votre réponse, la version qui vous semble la plus optimale.

C5.E3 : Arbre binaire strict (ou localement complet)

Un arbre binaire strict ou localement complet est un arbre dont tous les nœuds possèdent zéro ou deux fils.

1) Parmi les arbres ci-dessous lesquels sont localement complets ?

2) En travaillant avec une implémentation des arbres binaires à l'aide de tuples imbriqués (avec None si l'arbre est vide), écrire une fonction prédicat (c'est-à-dire qui renvoie True ou False) qui permet de tester si un arbre binaire passé en paramètre est localement complet.

Afficher la correction 
def est_local_cplt(arb):
    if arb == None:
        return True
    else:
        return (est_local_cplt(arb[1])
                and est_local_cplt(arb[2])
                and not( (arb[1] == None and arb[2] != None) or (arb[1] != None and arb[2] == None) )
               )

# arbres de la question 1
arb0 = (3,(2,(1,None,None),None),(4,None,(5,None,None)))
arb1 = ((12),(42,(43,None,None),(32,None,None)),(22,None,None))
arb2 = ('J',('B',('F',None,None),('Z',None,None)),('H',('C',None,None),None))

# autres arbres
arb3 = (5, (13, (35, None, None), (12, None, None)), (9, (6, None, None), (8, None, (15, None, None))))
arb4 = (3,(2,(1,None,None),None),(4,None,(5,None,None)))
arb5 = (3,(2,(1,None,None),(5,None,None)),(4,None,None))

print(est_local_cplt(arb0))
print(est_local_cplt(arb1))
print(est_local_cplt(arb2))


# Autre version
# def est_local_cplt(arb):
#     _, sag, sad = arb
#     if (sag == None and sad != None) or (sag != None and sad == None):
#         return False
#     elif sag == None and sad == None:
#         return True
#     else:
#         return est_local_cplt(sag) and est_local_cplt(sad)

■ Arbres binaires de recherche

C5.E11 : Quelques arbres

Représenter tous les ABR contenant les entiers 3, 5 et 7.

C5.E12 : Plus petite valeur dans un ABR

1) Où se trouve la plus petite valeur dans un ABR ?

2) En travaillant avec une implémentation des arbres binaires à l'aide de tuples imbriqués (avec None si l'arbre est vide), écrire une fonction qui prend un ABR en paramètre et renvoie sa plus petite valeur.

Afficher la correction

1) La plus petite valeur est celle du nœud le plus en bas à gauche.

2)

def mini(arbre):
    if arbre == None:
        return None
    elif arbre[1] == None:
        return arbre[0]
    else:
        return mini(arbre[1])


abr = (3, (2, None, None), None)
print(mini(abr) == 2)

abr = (3, None, (4, None, None))
print(mini(abr) == 3)

abr = (3, (2, None, None), (4, None, None))
print(mini(abr) == 2)

abr = (18,(8,(5,(1,None,None),(6,None,None)),(12,(10,None,None),None)),(24,(19,None,(21,None,None)),(33,(30,None,None),(35,None,None))))
print(mini(abr) == 1)

C5.E13 : Tri d'une liste à l'aide des ABR

Dans cet exercice, on travaillera avec une implémentation des arbres binaires à l'aide de tuples imbriqués (avec None si l'arbre est vide)

1) Écrire une fonction qui prend un ABR en paramètre et renvoie la liste des clés de cet arbre dans l'ordre infixe. Quel est la particularité de la liste renvoyée ?

2) Écrire une fonction qui :

3) Écrire une fonction qui prend une liste en paramètre et renvoie une liste triée contenant les mêmes valeurs.

Afficher la correction 
from random import randint

def parcours_infixe(abr):
    if abr == None:
        return []
    else:
        return parcours_infixe(abr[1]) + [abr[0]] + parcours_infixe(abr[2])

def ajoute(abr, val):
    if abr == None:
        return (val, None, None)
    else:
        val_racine, abr_g, abr_d = abr
        if val <= val_racine:
            return (val_racine, ajoute(abr_g, val), abr[2])
        else:
            return (val_racine, abr[1], ajoute(abr_d, val))

def tri_liste(li):
    abr = None
    for val in li:
        abr = ajoute(abr, val)
    return parcours_infixe(abr)


arbre = (18,(8,(5,(1,None,None),(6,None,None)),(12,(10,None,None),None)),(24,(19,None,(21,None,None)),(33,(30,None,None),(35,None,None))))
print(parcours_infixe(arbre))

arbre = ajoute(arbre, 11)
print(parcours_infixe(arbre))

liste = [randint(1,99) for _ in range(20)]
print(liste)
print(tri_liste(liste))