Correction : Arbres binaires

Propriétés

Selon la définition choisie, la hauteur de cet arbre est 4.
La taille de cet arbre est : 31
on peut stocker 31 données dans cet arbre
On doit parcourir au maximum 4 branches pour trouver une donnée
Un arbre de taille 63 a une hauteur de 5. Un arbre de taille 127 a une hauteur de 6. Un arbre de taille 255 a une hauteur de 7.
de façon générale la taille n et la hauteur h sont liées par n-1 =2^h+1 . on retiendra que n est de l’ordre de 2^h ou que h est de l'ordre de log₂(n)

Implémentation

Avec cette implémentation, chaque nœud est donc lui-même un sous-arbre de l'arbre ( et pas seulement une valeur ! ) :

	
from classe_arbre import *

hetre = Arbre(21, Arbre(10, Arbre('+', None, Arbre('A')), Arbre('feuille')), Arbre('pere', Arbre('fils1'), Arbre('fils2')))

hetre.dessine()

C'est donc une structure récursive, au même titre que les listes chaînées.

Une application : les arbres arithmétiques

Création de l'arbre


from classe_arbre import *
	
expr = Arbrearith('*',Arbrearith('+',Arbrearith('x'),Arbrearith(1)),Arbrearith('+',Arbrearith('*',Arbrearith(3),Arbrearith('y')),Arbrearith(2)))

expr.dessine()

Méthode `calcule`

Pour pouvoir évaluer l'expression, il faut remplacer les étiquettes 'x' et 'y' par les valeurs des deux variables x et y :

	
from classe_arbre import *

class Arbrearith(Arbre):

    def calcule(self):
        '''Calcule la valeur d'un arbre arithmétique de façon récursive'''

        if self.filsgauche == None and self.filsdroit == None:
            return self.valeur
        elif self.valeur == '+':
            return self.filsgauche.calcule() + self.filsdroit.calcule()
        elif self.valeur == '-':
            return self.filsgauche.calcule() - self.filsdroit.calcule()
        elif self.valeur == '*':
            return self.filsgauche.calcule() * self.filsdroit.calcule()
        elif self.valeur == '/':
            return self.filsgauche.calcule() / self.filsdroit.calcule()


x = 3
y = 2

expr = Arbrearith('*',Arbrearith('+',Arbrearith(x),Arbrearith(1)),Arbrearith('+',Arbrearith('*',Arbrearith(3),Arbrearith(y)),Arbrearith(2)))

expr.dessine()
print(expr.calcule()) # affiche (3 + 1)*(3*2 + 2) = 32

Un problème binaire : le morse

Construire l'arbre binaire

	
from classe_arbre import *

def creer_arbre_morse():
    '''
        Construit un arbre binaire de morse à partir d'un dictionnaire de morse, . à gauche et - à droite
    '''
    dicomorse = { 'A':'.-', 'B':'-...','C':'-.-.', 'D':'-..', 'E':'.','F':'..-.', 'G':'--.', 'H':'....','I':'..','J':'.---','K':'-.-','L':'.-..', 'M':'--', 'N':'-.','O':'---', 'P':'.--.', 'Q':'--.-','R':'.-.', 'S':'...','T':'-','U':'..-', 'V':'...-', 'W':'.--','X':'-..-', 'Y':'-.--', 'Z':'--..','1':'.----', '2':'..---', '3':'...--','4':'....-', '5':'.....', '6':'-....','7':'--...', '8':'---..', '9':'----.','0':'-----', ', ':'--..--', '.':'.-.-.-','?':'..--..', '/':'-..-.', '-':'-....-','(':'-.--.', ')':'-.--.-',' ':'.......'}

    racine = Arbre('')      # création de la racine
    noeud_courant=racine    # le noeud courant pointe vers la racine.

    for clef in dicomorse:          # Pour chaque clef ( = caractère ) codé dans le dictionnaire,
        for car in dicomorse[clef]: # pour chaque signe ('.' ou '-' ) du code morse du caractère :
            if car == '.':          # si le signe est un '.',
                noeud_courant.insertion_gauche('')      # alors on insère un noeud ( sans étiquette ! )  à gauche,
                noeud_courant=noeud_courant.filsgauche  # et on pointe le noeud courant vers ce nouveau noeud.
            if car == '-':          # même chose pour un signe '-',
                noeud_courant.insertion_droite('')      # on insère à droite
                noeud_courant=noeud_courant.filsdroit   # on "descend" vers le nouveua fils droit
        noeud_courant.valeur = clef # une fois tous les signes du code traité, on est (normalement !) "descendu" jusqu'à un noeud dont l'étiquette correspond au caractère codé
        noeud_courant = racine # ne pas oublier de "remonter" à la racine de l'arbre morse pour coder le caractère suivant
    return racine

creer_arbre_morse().dessine() # appel de la fonction de création, et appel de la méthode dessine() sur le résultat qu'elle renvoie

Décoder un message

Complexité

Au lieu de parcourir les n noeuds, on parcourt dans le pire des cas les log₂(n) branches de l'arbre La complexité de la recherche dans l'arbre morse sera donc de O(log₂(n))

Décodons !

	
def decode_morse(code: str, arbrebin: Arbre)->str:
    """
    Fonction pour décoder un caractère codé en morse

    Entrées :
        code : un code composé de - de . codant un caractère selon l'alphabet morse
        arbrebin : l'arbre binaire (. à gauche, - à droite) correspondant au dictionnaire de morse
    Sortie :
        le caractère décodé
    """
    noeud_courant = arbrebin
    for car in code:
        if car == ".":
            noeud_courant = noeud_courant.filsgauche
        else:
            noeud_courant = noeud_courant.filsdroit
    return noeud_courant.valeur

morse = creer_arbre_morse() # création de l'arbre

mes = ".--. .- ... ... .. --- -. -. .- -. - ....... .-.. .- ....... -. ... .. " # message à décoder

dec = ''
for code in mes.split(' '):       
    dec += decode_morse(code, morse)

print(dec)