Aperçu du sujet
EXERCICE 1 (4 points) Cet exercice porte sur les arbres binaires de recherche, la programmation orientée objet et la récursivité. Le code Morse doit son nom à Samuel Morse, l'un des inventeurs du télégraphe. Il a été conçu pour transférer rapidement des messages en utilisant une série de points et
EXERCICE 1 (4 points) Cet exercice porte sur les arbres binaires de recherche, la programmation orientée objet et la récursivité. Le code Morse doit son nom à Samuel Morse, l'un des inventeurs du télégraphe. Il a été conçu pour transférer rapidement des messages en utilisant une série de points et de tirets. Pour cet exercice, les points seront représentés par le caractère "o" et les tirets par le caractère "-". Chaque caractère du message que l'on veut transmettre est constitué d'une série de 1 à 5 points ou tirets. Le code a été conçu en tenant compte de la fréquence de chaque caractère dans la langue anglaise, de sorte que les caractères les plus fréquents, tels que E et T, ne comportent qu'un seul point ou tiret (E = "o", T = "-"), tandis que les caractères moins fréquents peuvent comporter 4 à 5 points ou tirets (par exemple, Q = "- - o -" et J = "o - - -"). Pour connaître le code morse de chaque caractère, on peut utiliser l'arbre binaire ci- dessous. En partant de la racine de l'arbre, la succession des branches reliant le nœud racine au caractère recherché nous donne le code morse de ce caractère en considérant que : une branche gauche correspond à un point ("o") ; une branche droite correspond à un tiret ("-"). Par exemple, le code morse de la lettre P est "o - - o" comme expliqué sur ce schéma : Figure 1 : Extrait de l’arbre binaire du code Morse 1. Déterminer le code morse du message "NSI", à l’aide de la figure de l’arbre binaire, en laissant un espace entre le code de chaque lettre. 2. Représenter le sous-arbre binaire pour les lettres M, G, O, Z et Q à l’aide de l’extrait de la table du code morse international : 23-NSIJ2LR1 Page 2/10 G : - - o M : - - O : - - - Q : - - o - Z : - - o o On donne, la déclaration de la classe et un extrait de la définition de l’arbre binaire : 1. cla s s Noeud: 2. d e f __init__(self, valeur, gauche=None, droite=None): 3. self.valeur = valeur 4. self.gauche = gauche 5. self.droite = droite 6. 7. arb r e = Noeud("Racine") 8. arb r e.gauche = Noeud("E") 9. arb r e.droite = Noeud("T") 10. arb