Skip to content

NSI - Terminale - Les arbres binaires

Travail demandé

Partie 1: arbre binaire de compétition

On vous propose de créer un logiciel qui permet d'obtenir des informations sur un tournoi de Tennis féminin. On a choisi de modéliser les différentes rencontres avec un arbre binaire dont le noeud racine est étiqueté avec la vainqueure du tournoi, les noeuds enfants de la racine sont étiquetés avec les demi-finalistes dont les noeuds enfants portent les quarts-finalistes, jusqu'aux feuilles qui représentent toutes les participantes du premier tour

Voici l'arbre obtenu lors de cette compétition (figure 1):

Pour coder l'arbre, on choisit le langage python et le modèle objet:

class Noeud:
    # méthode d'initialisation des attributs
    def __init__(self, g, v, d):
        self._enfant_gauche = g
        self._etiquette = v
        self._enfant_droit = d

    # méthode qui renvoie True si le noeud est une feuille
    def est_feuille(self):
        return self._enfant_gauche is None and self._enfant_droit is None

    # méthode qui renvoie l'étiquette du noeud
    def get_etiquette(self):
        return self._etiquette

    # méthode qui renvoie l'enfant gauche du noeud
    def get_enfant_g(self):
        return  self._enfant_gauche

    # méthode qui renvoie l'enfant droit du noeud
    def get_enfant_d(self):
        return self._enfant_droit

'''implémentation d'un arbre avec un seul 
match entre deux joueuses dont la vainqueure est Sacha Touille:'''

joueuse_1 = Noeud(None, "Sacha Touille", None)
joueuse_2 = Noeud(None, "Nadine Amite", None)
arbre = Noeud(joueuse_1,"Sacha Touille", joueuse_2)

Exercice 1:

  • Préciser pour l'arbre de compétition de la figure 1 ci-dessus, quelle est la taille N et la hauteur h de l'arbre si on considère que la racine est à hauteur 1, Indiquer la relation entre N et H.
  • Préciser si l'arbre est parfait, strict et son nombre de feuilles.

Exercice 2:

  • Coder l'arbre de compétition avec des instances de la classe Noeud.
  • Adapter, Coder et tester les fonctions taille et hauteur données dans la partie ressources pour vérifier si vos mesures sont exactes.

Exercice 3:

  • Ecrire le code de la fonction vainqueur qui prend comme argument un arbre de compétition représenté par la variable arbre et qui renvoie le nom de la personne qui a gagné le tournoi, vous utiliserez si nécessaire les méthodes de la classe, on considère que les attributs sont privés, ils ne doivent pas être utilisés directement en dehors de la classe. La fonction renvoie None si l'arbre est une feuille. 
def vainqueur(arbre):
    # à compléter

Exercice 3:

  • Compléter le code de la fonction sous_arbre_gauche qui prend en argument un arbre de compétition représenté par la variable arbre et qui renvoie un objet Noeud représentant le sous_arbre_gauche, vous utiliserez si nécessaire les méthodes de la classe, on considère que les attributs sont privés, ils ne doivent pas être utilisés directement en dehors de la classe. La fonction renvoie None si l'arbre est une feuille. 
def sous_arbre_gauche(arbre):
    # à compléter

Exercice 4:

  • Compléter le code de la fonction sous_arbre_droit qui prend en argument un arbre de compétition représenté par la variable arbre et qui renvoie un objet Noeud représentant le sous_arbre_droit, vous utiliserez si nécessaire les méthodes de la classe, on considère que les attributs sont privés, ils ne doivent pas être utilisés directement en dehors de la classe. La fonction renvoie None si l'arbre est une feuille. 
def sous_arbre_gauche(arbre):
    # à compléter

Exercice 5:

  • Ecrire la fonction finalistes qui prend en argument un arbre de compétition représenté par la variable arbre et qui renvoie une liste avec le nom des deux joueuses finalistes du tournoi.
def finalistes(arbre):
    # à compléter

Exercice 6:

  • En utilisant un parcours en largeur, écrire la fonction participantes qui prend en argument un arbre de compétition représenté par la variable arbre et qui renvoie une liste avec toutes les joueuses du tournoi.
def participantes(arbre):
    # à compléter

Exercice 7:

  • Ecrire la fonction Nombre_de_matchs qui prend en arguments un arbre de compétition représenté par la variable arbre et une joueuse représentée par la variable joueuse, la fonction renvoie le nombre de matchs joués par la joueuse choisie ou None si elle n'a pas participé à la compétition. 
def Nombre_de_matchs(arbre, joueuse):
    # à compléter

Partie 2: arbre binaire de recherche:

M Gautier a demandé à une IA de représenter les élèves de terminale NSI avec un ABR dont le critère de rangement est basé sur l'ordre alphabétique du prénom (sachant qu'il n'y a pas d'homonymes dans la classe).

Voici la liste des noms dans l'ordre alphabétique sans Bilal qui sera insèré dans l'ABR plus tard: ["Adam", "Alexis" , "Arthur", "Bastien", "Esteban", "Jakub", "Jeanne", "Lilian", "Melinda", "Mohamed", "Nassim", "Rayane", "Yanis", "Yasmine"]

Le résultat proposé par l'IA est celui-ci:

Exercice 8:

  • Que pensez-vous du résultat obtenu, l'arbre est-il un ABR? Expliquez votre raisonnement ?

  • Imaginez que l'on recherche "Yasmine" dans cette arbre, quelle va être la compléxité en temps de la recherche (revoir le notion de complexité dans le dossier ressources si nécessaire) ?

On vous propose maintenant l'arbre suivant:

Exercice 9:

  • Imaginez que l'on recherche "Yasmine B" dans cet arbre, quelle serait approximativement la compléxité en temps de la recherche (revoir le notion de complexité dans le dossier ressources si nécessaire) ?

Exercice 10:

  • Donner le résultat d'un parcours infixe de ce nouvel arbre. Comparer avec l'ordre alphabétique de la liste (magique non?).

  • Donner le résultat d'un parcours préfixe de ce nouvel arbre.

  • Donner le résultat d'un parcours postfixe (ou suffixe) de ce nouvel arbre.

Exercice 11:

  • Redessiner l'arbre en ajoutant "Bilal E" ( vous ne dessinerez que le noeud parent du noeud qui accueillera Bilal et la branche gauche ou droite du noeud d'étiquette "Bilal E").

Exercice 12:

  • coder cet arbre en utilisant des dictionnaires pour représenter les noeuds, on vous donne ci-dessous une fonction noeud qui renvoie le dictionnaire d'un noeud à partir des arguments donnés au paramètres g,v et d. Vous vous limiterez à un arbre de hauteur 2 avec seulement Jeanne, Esteban et Rayane.
# fonction qui renvoie un dictionnaire
def noeud(g, v, d):
    return {"gauche":g, "valeur":v, "droit":d}

# création de la feuille Rayane
Rayane = noeud(None,"Rayane", None)

# à compléter
Esteban = 
abr =

Exercice 13:

  • coder et tester une fonction parcours_infixe qui parcourt l'abr et renvoie une liste avec les personnes dans l'ordre rencontré dans le parcours ici le résultat attendu sera [ "Esteban", "Jeanne", "Rayane" ]
# fonction qui renvoie un dictionnaire
def noeud(g, v, d):
    return {"gauche":g, "valeur":v, "droit":d}

def parcours_infixe(abr):
   # à compléter

# création de la feuille Rayane
Rayane = noeud(None,"Rayane", None)

# à compléter
Esteban = 
abr=

Exercice 14:

  • Ecrire la fonction verif qui prend deux arguments: un arbre représenté par la variable abr et un nom représenté par la variable nom, la fonction renvoie True si la valeur de la variable nom est une des étiquettes des noeuds de l'arbre.Tester votre code en recherchant "Esteban" et "Melinda".
# fonction qui renvoie un dictionnaire
def noeud(g, v, d):
    return {"gauche":g, "valeur":v, "droit":d}

# création de la feuille Rayane
Rayane = noeud(None,"Rayane", None)

# à compléter
Esteban = 
abr =  

def verif(abr, nom):
    # à compléter 

# utilisation

print(verif(abr, "Esteban"))
print(verif(abr, "Esteban"))

Exercice 15:

  • Ecrire et tester la fonction insere qui prend deux arguments: un arbre représenté par la variable abr et un nom représenté par la variable nom, la fonction insère un noeud avec comme étiquette la valeur de la variable nom si cette étiquette n'est pas déjà présente. 
# fonction qui renvoie un dictionnaire
def noeud(g, v, d):
    return {"gauche":g, "valeur":v, "droit":d}

# création de la feuille Rayane
Rayane = noeud(None,"Rayane", None)

# à compléter
Esteban =  
abr = 

def insere(abr, nom):
    # à compléter

# utilisation 
insere(abr, "Bilal")