Chapitre 6 : Les arbres binaires.

3. Exercice :

A faire dans le cahier.

Dans cet exercice un arbre composé uniquement d'un seul noeud a une hauteur de 1.

On considère cet arbre binaire :

1. Quelle est sa racine?
2. Quelle est sa hauteur?
3. Quelle est sa taille?
4. Combien a-t-il de feuille?
5. Qui est l'enfant gauche de l'enfant gauche de l'enfant gauche du parent du parent de Mia?

12. Exercice :

A faire dans le cahier.

Représenter l'arbre correspondant au tableau ci-dessous :

13. Exercice

A faire dans le cahier.

En prenant exemple du tableau de l'exercice précédent, faire un tableau correspondant à l'arbre ci-dessous :

15. Exercice

Insérer dans Python l'arbre suivant à l'aide de liste de liste.

Une feuille aura ce format : [valeur,None,None]

16. Exercice

Ecrire une fonction ajout_feuille_gauche(liste_arbre,valeur) qui prend en paramètre un arbre sous forme de liste et une valeur.

Elle fonctionnera de manière récursive ainsi :

• Si l'enfant gauche de la racine est vide, on place la valeur à cet endroit.
• Sinon, on exécute cette fonction dans le sous-arbre gauche.

18. Exercice

Ecrire en Python les fonctions suivantes

• taille prenant paramètre une liste
• hauteur prenant paramètre une liste (un arbre composé que d'un seul noeud à une hauteur égale à 1).
• nombre_feuille prenant paramètre une liste

20. Exercice

A faire dans le cahier.

On considère l'arbre suivant:

Sur une feuille :

1. Ecrire les valeurs rencontrées en parcourant l'arbre dans l'ordre préfixe.
2. Ecrire les valeurs rencontrées en parcourant l'arbre dans l'ordre infixe.
3. Ecrire les valeurs rencontrées en parcourant l'arbre dans l'ordre postfixe.

22. Exercice

1. Programmer une fonction lecture_prefixe qui prend comme paramètre une liste représentant un arbre et qui affiche à l'aide de print les valeurs rencontrées en parcourant dans l'ordre préfixe.
2. Programmer une fonction lecture_infixe qui prend comme paramètre une liste représentant un arbre et qui affiche à l'aide de print les valeurs rencontrées en parcourant dans l'ordre infixe.
3. Programmer une fonction lecture_postfixe qui prend comme paramètre une liste représentant un arbre et qui affiche à l'aide de print les valeurs rencontrées en parcourant dans l'ordre postfixe.

24. Exercice :

Insérer dans Python l'arbre suivant à l'aide de la classe vu précedemment.

25. Exercice :

En utilisant la classe ci-dessus, écrire en Python les fonctions suivantes: (on pourra mettre les précédentes fonctions écrites en commentaire pour ne pas avoir d'ambiguïté)

1. taille prenant en paramètre un objet ArbreBinaire
2. hauteur prenant en paramètre un objet ArbreBinaire
3. nombre_feuille prenant en paramètres un objet ArbreBinaire
4. Programmer une fonction lecture_prefixe qui prend comme paramètre un objet ArbreBinaire et qui affiche à l'aide de print les valeurs rencontrées en parcourant l'arbre dans l'ordre préfixe.
5. Programmer une fonction lecture_infixe qui prend comme paramètre un objet ArbreBinaire et qui affiche à l'aide de print les valeurs rencontrées en parcourant l'arbre dans l'ordre infixe.
6. Programmer une fonction lecture_postfixe qui prend comme paramètre un objet ArbreBinaire et qui affiche à l'aide de print les valeurs rencontrées en parcourant l'arbre dans l'ordre postfixe.

27. Exercice

On considère l'arbre suivant:

Sur une feuille, écrire les valeurs des noeuds rencontrés par un parcours en largeur.

29. Exercice :

Le but est de programmer en Python la lecture en largeur d'abord comme ci-dessus

1. Dans un même fichier, implémenter les objets ArbreBinaire et File.
2. Implémenter un arbre, par exemple celui de l'exercice 24.
3. Ecrire l'algorithme ci-dessus et le tester.

32. Exercice :

A faire dans le cahier

On considère l'arbre de l'exemple précédent.

1. Ecrire les valeurs rencontrées en parcourant l'arbre dans l'ordre préfixe.
2. Ecrire les valeurs rencontrées en parcourant l'arbre dans l'ordre infixe.
3. Ecrire les valeurs rencontrées en parcourant l'arbre dans l'ordre postfixe.

35. Exercice :

Programmer une fonction Python evaluer qui prend comme paramètre un objet ArbreBinaire contenant une expression mathématique et qui l'évalue.

class ArbreBinaire:
    def __init__(self,valeur):
        self.valeur=valeur
        self.gauche=None
        self.droit=None

    def ajout_gauche(self,valeur):
        self.gauche=Arbre_binaire(valeur)

    def ajout_droit(self,valeur):
        self.droit=Arbre_binaire(valeur)

    def suppr_gauche(self):
        self.gauche=None

    def suppr_droit(self):
        self.droit=None
        
            
            
arbre=ArbreBinaire("+")
arbre.ajout_gauche("*")
arbre.gauche.ajout_gauche(3)
arbre.gauche.ajout_droit(2)
arbre.ajout_droit("/")
arbre.droit.ajout_gauche(60)
arbre.droit.ajout_droit("+")
arbre.droit.droit.ajout_gauche(4)
arbre.droit.droit.ajout_droit(6)

def evaluer(arbre):
    ......

36. Exercice : (sujet 21 - 2023)

Une expression arithmétique ne comportant que les quatre opérations \( + \), \(-\), \( \times \) , \( \div \) peut être représentée sous forme d’arbre binaire. Les nœuds internes sont des opérateurs et les feuilles sont des nombres. Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses que nous connaissons bien.

En parcourant en profondeur infixe l’arbre binaire ci-dessus, on retrouve l’expression notée habituellement :

La classe Noeud ci-après permet d’implémenter une structure d’arbre binaire.

Compléter la fonction récursive expression_infixe qui prend en paramètre un objet de la classe Noeud et qui renvoie l’expression arithmétique représentée par l’arbre binaire passé en paramètre, sous forme d’une chaîne de caractères contenant des parenthèses.

e = Noeud(Noeud(Noeud(None, 3, None),
    '*', Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))),
    '-', Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None)))


class Noeud:
    '''
    classe implementant un noeud d'arbre binaire
    '''

    def __init__(self, g, v, d):
        '''
        un objet Noeud possede 3 attributs :
        - gauche : le sous-arbre gauche,
        - valeur : la valeur de l'etiquette,
        - droit : le sous-arbre droit.
        '''
        self.gauche = g
        self.valeur = v
        self.droit = d

    def __str__(self):
        '''
        renvoie la representation du noeud en chaine de caracteres
        '''
        return str(self.valeur)

    def est_une_feuille(self):
        '''
        renvoie True si et seulement si le noeud est une feuille
        '''
        return self.gauche is None and self.droit is None


def expression_infixe(e):
    s = ...
    if e.gauche is not None:
        s = '(' + s + expression_infixe(...)
    s = s + ...
    if ... is not None:
        s = s + ... + ...
    return s

Résultat attendu avec l'arbre ci-dessus :

>>> e = Noeud(Noeud(Noeud(None, 3, None),
'*', Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))),
'-', Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None)))
>>> expression_infixe(e)
'((3*(8+7))-(2+1))'

37. Exercice : (sujet 33 - 2023)

Un arbre binaire de caractères est stocké sous la forme d’un dictionnaire où les clés sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clé, la liste des caractères des fils gauche et droit du nœud.

Par exemple, l’arbre

est stocké dans

a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'],'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], 'H':['','']}

Écrire une fonction récursive taille prenant en paramètres un arbre binaire arbre sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de l’arbre, et qui renvoie la taille de l’arbre, à savoir le nombre total de nœud.

On observe que, par exemple, arbre[lettre][0], respectivement arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement droit, de l’arbre arbre de sommet lettre.

Exemple :

>>> taille(a, 'F')
9

38. Exercice :

On considère les classes ci-dessous :

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droit = None
  
class Arbre_Binaire:
    def __init__(self):
        self.racine = None

On considère l'arbre suivant :

Il est par exemple stocké dans Python à l'aide du code ci-dessous :

# Creation des noeuds
noeud_f = Noeud("F")
noeud_b = Noeud("B")
noeud_c = Noeud("C")
noeud_d = Noeud("D")
noeud_e = Noeud("E")

# Creation de l'arbre et assignation des sous-arbres
arbre = Arbre_Binaire()
arbre.racine = noeud_f

# Assignation des enfants selon le graphe
noeud_f.gauche = noeud_b
noeud_f.droit = noeud_c
noeud_b.droit = noeud_d
noeud_d.gauche = noeud_e

1. Ecrire une fonction valeur_de_la_racine(arbre: ArbreBinaire) et qui renvoie un string associé à la valeur de la racine.
2. Ecrire une fonction valeur_enfant_droit(arbre: ArbreBinaire) et qui renvoie un string associé à la valeur de l'enfant directement à droite de la racine.
3. Ecrire une fonction taille(arbre: ArbreBinaire) et qui renvoie un integer associé à la taille de l'arbre.
4. Ecrire une fonction hauteur(arbre: ArbreBinaire) et qui renvoie un integer associé à la hauteur de l'arbre. Ici, un arbre composé uniquement d'une racine aura pour hauteur 0 et l'arbre donné en exemple aura une hauteur de 3.
5. Ecrire une fonction liste_prefixe(arbre: ArbreBinaire) et qui renverra une liste des valeurs des noeuds de l'arbre parcouru en profondeur dans l'ordre préfixe. Par exemple, l'arbre donné en exemple renverra ["F","B","D","E","C"].

39. Exercice :

Il est moins usuel mais nous pouvons programmer un parcours préfixé en itératif à l'aide de l'algorithme suivant :

fonction parcours_prefixe_iteratif(arbre):
    créer une pile p
    insérer l'arbre dans la pile 
    tant que la pile p n'est pas vide 
        depiler un element de la pile que l'on nommera element 
        traiter la racine de cet element en l'affichant par exemple
        si le sous-arbre droit n'est pas vide :
            on empile dans p le sous-arbre droit
        si le sous arbre gauche n'est pas vide :
            on empile dans p le sous-arbre gauche

Coder ceci en python à l'aide des classes ArbreBinaire et Pile. On pourra utiliser un arbre des exercices précédents.