Aller au contenu

Les arbres binaires

Programme

Notions Compétences Remarques
Arbres : structures hiérarchiques.
Arbres binaires : nƓuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.		 Identifier des situations nĂ©cessitant une structure de donnĂ©es arborescente.
Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).		 On fait le lien avec la rubrique « algorithmique ».
Activité 1 - Introduction

Regardez la vidéo

  1. Construisez un ou deux terriers correspondants Ă  la consigne : un terrier qui minimise le nombre de trajets.
    N'oubliez pas d'indiquer pour chaque arbre le nombre total de trajets fait pour toutes les marmottes du terrier. Pour chaque marmotte on prend le nombre de fois oĂč elle se rĂ©veille fois le nombre de tunnels empruntĂ©s.
  2. Comparez avec les autres élÚves de la classe les différents terriers créés. Caractérisez les arbres qui répondent le mieux à la question.
  3. DĂ©terminez un algorithme de construction de terrier qui minimise le nombre de trajets.
Correction 
  1. flowchart TD
        A(( )) --- B(( ))
        A --- C(( ))
        B --- D(( ))
        B --- E((5))
        C --- F((7))
        C --- G((8))
        D --- H((2))
        D --- I((3))
  2. Nombre de trajets: 2 x 6 + 3 x 6 + 5 x 4 + 7 x 4 + 8 x 4 = 110

  3. Par exemple, si on a les réveils des marmottes suivants : 7; 3; 5; 9; 2; 4; 6

    • on crĂ©Ă© des terriers en les sĂ©parant en deux au bout de chacun, jusqu’à ce qu’il y ait autant de terrier que de marmottes (ici 7) 
    flowchart TD
    A(( )) --- B(( ))
    A --- C(( ))
    B --- D(( ))
    B --- E(( ))
    C --- F(( ))
    C --- G((9))
    D --- H((2))
    D --- I((3))
    E --- K((4))
    E --- L((5))
    F --- M((6))
    F --- N((7))
    • On place les marmottes le plus en haut suivant le nombre de rĂ©veil le plus haut, puis on descend au niveau infĂ©rieur et on recommence


    Ici, le nombre de trajet est : 2 x 6 + 3 x 6 + 4 x 6 + 5 x 6 + 6 x 6 + 7 x 6 + 9 x 4 = 198

Les arbres binaires

Vidéo

Un arbre binaire est une structure dite arborescente oĂč chaque position donne accĂšs sur exactement deux branches.

Un arbre binaire est un ensemble fini de noeuds correspondant Ă  l'un des deux cas suivants :

  • soit l'arbre est vide, c'est Ă  dire qu'il ne contient aucun noeud.
  • soit l'arbre n'est pas vide et ses noeuds sont structurĂ©s de la maniĂšre suivante :
  • un noeud est appelĂ© la racine de l'arbre.
  • la racine a deux branches (ou arĂȘtes) qui forment rĂ©cursivement deux sous-arbres (ou fils) appelĂ©s respectivement sous-arbre gauche et sous-arbre droit.

Un noeud dont les sous-arbres sont vides est appelé feuille.

Dans la figure ci-dessous, tous les arbres dessinĂ©s sont deux Ă  deux distincts, ce qui confirme qu'il faut distinguer sous-arbre droit et gauche, et qu'un des sous-arbres peut ĂȘtre vide :

Activité 2 - Nombre de noeuds
  1. Dessiner tous les arbres binaires ayant 3 noeuds.
  2. Dessiner tous les arbres binaires ayant 4 noeuds.
Correction

Avec 3 noeuds :

flowchart LR

    subgraph a [A]
        direction TB
        A(( )) --- B(( ))
        A --- C(( ))

    end

    subgraph b [B]
        direction TB
        D(( )) --- E(( ))
        D --- F(( ))
        E --- G(( ))
        E --- H(( ))
        style F opacity:0
        linkStyle 3 stroke-width:0px
        style H opacity:0
        linkStyle 5 stroke-width:0px

    end

    subgraph c [C]
        direction TB
        I(( )) --- J(( ))
        I --- K(( ))
        K --- M(( ))
        K --- L(( ))
        style J opacity:0
        linkStyle 6 stroke-width:0px
        style M opacity:0
        linkStyle 8 stroke-width:0px

    end

    subgraph d [D]
        direction TB
        N(( )) --- O(( ))
        N --- P(( ))
        O --- Q(( ))
        O --- R(( ))
        style P opacity:0
        linkStyle 11 stroke-width:0px
        style Q opacity:0
        linkStyle 12 stroke-width:0px

    end

    subgraph e [E]
        direction TB
        S(( )) --- T(( ))
        S --- U(( ))
        U --- V(( ))
        U --- W(( ))
        style T opacity:0
        linkStyle 14 stroke-width:0px
        style W opacity:0
        linkStyle 17 stroke-width:0px

    end

    a x--x | | b x--x | | c x--x | | d x--x | | e

Avec 4 noeuds :

flowchart LR

    subgraph a [A]
        direction TB
        A(( )) --- B(( ))
        A --- C(( ))
        B --- D(( ))
        B --- E(( ))
        D --- F(( ))
        D --- G(( ))

        style C opacity:0
        linkStyle 1 stroke-width:0px
        style E opacity:0
        linkStyle 3 stroke-width:0px
        style G opacity:0
        linkStyle 5 stroke-width:0px

    end

    subgraph b [B]
        direction TB
        A1(( )) --- B1(( ))
        A1 --- C1(( ))
        C1 --- D1(( ))
        C1 --- E1(( ))
        E1 --- F1(( ))
        E1 --- G1(( ))

        style B1 opacity:0
        linkStyle 6 stroke-width:0px
        style D1 opacity:0
        linkStyle 8 stroke-width:0px
        style F1 opacity:0
        linkStyle 10 stroke-width:0px

    end

    subgraph c [C]
        direction TB
        A2(( )) --- B2(( ))
        A2 --- C2(( ))
        B2 --- D2(( ))
        B2 --- E2(( ))
        E2 --- F2(( ))
        E2 --- G2(( ))

        style C2 opacity:0
        linkStyle 13 stroke-width:0px
        style D2 opacity:0
        linkStyle 14 stroke-width:0px
        style G2 opacity:0
        linkStyle 17 stroke-width:0px

    end

    subgraph d [D]
        direction TB
        A3(( )) --- B3(( ))
        A3 --- C3(( ))
        C3 --- D3(( ))
        C3 --- E3(( ))
        D3 --- F3(( ))
        D3 --- G3(( ))

        style B3 opacity:0
        linkStyle 18 stroke-width:0px
        style E3 opacity:0
        linkStyle 21 stroke-width:0px
        style F3 opacity:0
        linkStyle 22 stroke-width:0px

    end

    subgraph e [E]
        direction TB
        A4(( )) --- B4(( ))
        A4 --- C4(( ))
        C4 --- D4(( ))
        C4 --- E4(( ))
        D4 --- F4(( ))
        D4 --- G4(( ))

        style B4 opacity:0
        linkStyle 24 stroke-width:0px
        style E4 opacity:0
        linkStyle 27 stroke-width:0px
        style G4 opacity:0
        linkStyle 29 stroke-width:0px

    end

    subgraph f [F]
        direction TB
        A5(( )) --- B5(( ))
        A5 --- C5(( ))
        B5 --- D5(( ))
        B5 --- E5(( ))
        E5 --- F5(( ))
        E5 --- G5(( ))

        style C5 opacity:0
        linkStyle 31 stroke-width:0px
        style D5 opacity:0
        linkStyle 32 stroke-width:0px
        style F5 opacity:0
        linkStyle 34 stroke-width:0px

    end

    a x--x | | b x--x | | c x--x | | d x--x | | e x--x | | f

flowchart LR

    subgraph a [A]
        direction TB
        A(( )) --- B(( ))
        A --- C(( ))
        B --- D(( ))
        B --- E(( ))

        style C opacity:0
        linkStyle 1 stroke-width:0px

    end

    subgraph b [B]
        direction TB
        A1(( )) --- B1(( ))
        A1 --- C1(( ))
        C1 --- D1(( ))
        C1 --- E1(( ))

        style B1 opacity:0
        linkStyle 4 stroke-width:0px

    end

    subgraph c [C]
        direction TB
        A4(( )) --- B4(( ))
        A4 --- C4(( ))
        B4 --- F4(( ))
        B4 --- G4(( ))

        style F4 opacity:0
        linkStyle 10 stroke-width:0px

    end

    subgraph d [D]
        direction TB
        A3(( )) --- B3(( ))
        A3 --- C3(( ))
        C3 --- D3(( ))
        C3 --- E3(( ))

        style E3 opacity:0
        linkStyle 15 stroke-width:0px

    end

    subgraph e [E]
        direction TB
        A2(( )) --- B2(( ))
        A2 --- C2(( ))
        B2 --- D2(( ))
        B2 --- E2(( ))

        style E2 opacity:0
        linkStyle 19 stroke-width:0px

    end

    subgraph f [F]
        direction TB
        A5(( )) --- B5(( ))
        A5 --- C5(( ))
        C5 --- D5(( ))
        C5 --- E5(( ))

        style D5 opacity:0
        linkStyle 22 stroke-width:0px

    end

    a x--x | | b x--x | | c x--x | | d x--x | | e x--x | | f

Propriétés

Taille : nombre de noeuds d'un arbre.

Profondeur :

Hauteur : Profondeur maximale d'un arbre

Complet ou parfait : c'est un arbre binaire de hauteur h tel qu'à chaque profondeur p tous les noeuds sont présents.

Activité 3 - Taille et hauteur

Déterminer les taille et hauteur de chaque arbre de l'activité précédente.

Correction

Avec 3 noeuds :

flowchart LR

    subgraph a [Hauteur 2]
        direction TB
        A(( )) --- B(( ))
        A --- C(( ))

    end

    subgraph b [Hauteur 3]
        direction TB
        D(( )) --- E(( ))
        D --- F(( ))
        E --- G(( ))
        E --- H(( ))
        style F opacity:0
        linkStyle 3 stroke-width:0px
        style H opacity:0
        linkStyle 5 stroke-width:0px

    end

    subgraph c [Hauteur 3]
        direction TB
        I(( )) --- J(( ))
        I --- K(( ))
        K --- M(( ))
        K --- L(( ))
        style J opacity:0
        linkStyle 6 stroke-width:0px
        style M opacity:0
        linkStyle 8 stroke-width:0px

    end

    subgraph d [Hauteur 3]
        direction TB
        N(( )) --- O(( ))
        N --- P(( ))
        O --- Q(( ))
        O --- R(( ))
        style P opacity:0
        linkStyle 11 stroke-width:0px
        style Q opacity:0
        linkStyle 12 stroke-width:0px

    end

    subgraph e [Hauteur 3]
        direction TB
        S(( )) --- T(( ))
        S --- U(( ))
        U --- V(( ))
        U --- W(( ))
        style T opacity:0
        linkStyle 14 stroke-width:0px
        style W opacity:0
        linkStyle 17 stroke-width:0px

    end

    a x--x | | b x--x | | c x--x | | d x--x | | e

Avec 4 noeuds :

flowchart LR

    subgraph a [Hauteur 4]
        direction TB
        A(( )) --- B(( ))
        A --- C(( ))
        B --- D(( ))
        B --- E(( ))
        D --- F(( ))
        D --- G(( ))

        style C opacity:0
        linkStyle 1 stroke-width:0px
        style E opacity:0
        linkStyle 3 stroke-width:0px
        style G opacity:0
        linkStyle 5 stroke-width:0px

    end

    subgraph b [Hauteur 4]
        direction TB
        A1(( )) --- B1(( ))
        A1 --- C1(( ))
        C1 --- D1(( ))
        C1 --- E1(( ))
        E1 --- F1(( ))
        E1 --- G1(( ))

        style B1 opacity:0
        linkStyle 6 stroke-width:0px
        style D1 opacity:0
        linkStyle 8 stroke-width:0px
        style F1 opacity:0
        linkStyle 10 stroke-width:0px

    end

    subgraph c [Hauteur 4]
        direction TB
        A2(( )) --- B2(( ))
        A2 --- C2(( ))
        B2 --- D2(( ))
        B2 --- E2(( ))
        E2 --- F2(( ))
        E2 --- G2(( ))

        style C2 opacity:0
        linkStyle 13 stroke-width:0px
        style D2 opacity:0
        linkStyle 14 stroke-width:0px
        style G2 opacity:0
        linkStyle 17 stroke-width:0px

    end

    subgraph d [Hauteur 4]
        direction TB
        A3(( )) --- B3(( ))
        A3 --- C3(( ))
        C3 --- D3(( ))
        C3 --- E3(( ))
        D3 --- F3(( ))
        D3 --- G3(( ))

        style B3 opacity:0
        linkStyle 18 stroke-width:0px
        style E3 opacity:0
        linkStyle 21 stroke-width:0px
        style F3 opacity:0
        linkStyle 22 stroke-width:0px

    end

    subgraph e [Hauteur 4]
        direction TB
        A4(( )) --- B4(( ))
        A4 --- C4(( ))
        C4 --- D4(( ))
        C4 --- E4(( ))
        D4 --- F4(( ))
        D4 --- G4(( ))

        style B4 opacity:0
        linkStyle 24 stroke-width:0px
        style E4 opacity:0
        linkStyle 27 stroke-width:0px
        style G4 opacity:0
        linkStyle 29 stroke-width:0px

    end

    subgraph f [Hauteur 4]
        direction TB
        A5(( )) --- B5(( ))
        A5 --- C5(( ))
        B5 --- D5(( ))
        B5 --- E5(( ))
        E5 --- F5(( ))
        E5 --- G5(( ))

        style C5 opacity:0
        linkStyle 31 stroke-width:0px
        style D5 opacity:0
        linkStyle 32 stroke-width:0px
        style F5 opacity:0
        linkStyle 34 stroke-width:0px

    end

    a x--x | | b x--x | | c x--x | | d x--x | | e x--x | | f

flowchart LR

    subgraph a [Hauteur 3]
        direction TB
        A(( )) --- B(( ))
        A --- C(( ))
        B --- D(( ))
        B --- E(( ))

        style C opacity:0
        linkStyle 1 stroke-width:0px

    end

    subgraph b [Hauteur 3]
        direction TB
        A1(( )) --- B1(( ))
        A1 --- C1(( ))
        C1 --- D1(( ))
        C1 --- E1(( ))

        style B1 opacity:0
        linkStyle 4 stroke-width:0px

    end

    subgraph c [Hauteur 3]
        direction TB
        A4(( )) --- B4(( ))
        A4 --- C4(( ))
        B4 --- F4(( ))
        B4 --- G4(( ))

        style F4 opacity:0
        linkStyle 10 stroke-width:0px

    end

    subgraph d [Hauteur 3]
        direction TB
        A3(( )) --- B3(( ))
        A3 --- C3(( ))
        C3 --- D3(( ))
        C3 --- E3(( ))

        style E3 opacity:0
        linkStyle 15 stroke-width:0px

    end

    subgraph e [Hauteur 3]
        direction TB
        A2(( )) --- B2(( ))
        A2 --- C2(( ))
        B2 --- D2(( ))
        B2 --- E2(( ))

        style E2 opacity:0
        linkStyle 19 stroke-width:0px

    end

    subgraph f [Hauteur 3]
        direction TB
        A5(( )) --- B5(( ))
        A5 --- C5(( ))
        C5 --- D5(( ))
        C5 --- E5(( ))

        style D5 opacity:0
        linkStyle 22 stroke-width:0px

    end

    a x--x | | b x--x | | c x--x | | d x--x | | e x--x | | f

Arbres particuliers

Activité 4 - Un arbre en python
Création de l'arbre

Une façon classique de représenter un arbre binaire en Python est de créer une classe Noeud :

class Noeud :
    """objet Noeud d'un arbre binaire"""
    def __init__(self, val = None, filsG = None, filsD = None) :
        self.set_val(val)
        self.set_filsG(filsG)
        self.set_filsD(filsD)

    def get_val(self):
        return self.val

    def set_val(self, nouvelle_val):
        self.val = nouvelle_val

    def get_filsG(self):
        return self.filsG

    def set_filsG(self, nouveau_filsG):
        self.filsG = nouveau_filsG

    def get_filsD(self):
        return self.filsD

    def set_filsD(self, nouveau_filsD):
        self.filsD = nouveau_filsD

    def __str__(self):
        return f"{self.get_val()}, {self.get_filsG()}, {self.get_filsD()}"

Le noeud contient 3 attributs : sa valeur, ses fils droit et gauche. On peut y ajouter un affichage basique.

Utilisation de la classe Noeud

Consigne :

  • ImplĂ©menter l'arbre suivant :

###(DĂ©s-)Active le code aprĂšs la ligne # Tests (insensible Ă  la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activĂ©, le texte copiĂ© dans le terminal est joint sur une seule ligne avant d'ĂȘtre copiĂ© dans le presse-papier
Évaluations restantes : 10/10

.128013rt=7CflbG)D1 {2e/vygj.:,8sw9nuph5aS(o3qNk_}i46P;Ă©cdm0050Z0q0c0I0S0h0A0n0Y0h0I0A0A0d010c0S0F010406050A0E0!0!0I0b0t040J0L0h0E0_0L0D050r101214160~0F04051m1f1p0r1m0~0Z0S0s0.0:0=0@0G0S0u0G0h1D0G0c0|050)0i0h0q1y0;0?011C1E1G1E0c1M1O1K0c0b1n0c0G0.190A0F0I0D0@0p011Q1A010g0+0q0D0I0!0q1K1-1/1@1S1`1O1}1 0|0a0n0V0b0L0F0L0A0S1c0D0n0%1+0b0b0q0Y2k1f220D1n0r1)2x1$1(1%1L0Z240@1G0D1|2h1K1v1x0/1R2H0S2J0D0L2N1K0F2q1n2v2x2#0 1.2l2P1^2U0b130h0|0n0m2u2)0}2(232+1S2-2/2;0p2@1/2_2v2G012~0I2:040n0M322w0~352|0@383a0n0T3e342)363k2;0H3o3g3q3i370L2.392;0U3v2`2*1z2}3A2 3b0e3F3h3I3j3K3C3b0z3O3x3Q3z3B3l0C3W2{3Y3s040m0#3%3H2Q3Z3L0m2?1g2^3w3(3:3*0m313^333`3/2,3S3a0m3d403f3G3r450|0m3n493p3{443!4e3u4h424c4l3+3E4o4b3y3}3N4u3P3|4d3+3V4z3X4B4r0m3$4F4j3J4r0p3-4L434N3L0p3@2#4p4w4C0p3 4X4v3)4!484%4A4k4U4g4,4G4.3T0p4n4;4M3R4O4t4`4S4|4U4y4 4q4U4E544Z4O4K584)4r0M4Q5c4H3L0M4W3_4(5i3T0M4$5m4-4T5p4+2^1q2Z1f2N2A0Z1(2F3y0Y2V201n5B1o5z2%4h055H0%2!4=1S0P0|2|3o0n5n2,0Y0|0O0L0q0E0Z5Z5#1S0{040x3.360B2;0n5{3o5/0@0A0Z0|020N0E0L0c0W63656769660W0L0i0v0(0n5)5+2F0Z02030M0C0W0E2l140i2q0n0i2S0*2q6c6b646d6D0W3v5{5|5t0@5W040%0g5.6M1_0!0|0Q0Q2S2j6X5}6T5;0K6$5U0@0i5;0A0q0h6R5P6%0|0y6S6+370|0s396`4{010L0|0d7050010P5%045)2J6*715;6_4h5!6T0D0|260A0j76367304757i5~787a7c0q7e777g7q4w7m0+0A0l7E3Y7s7u2#7j6{795(1d7A6?6{5;0k7K3:5;5?4o6K7(7P716-0|6/6;7B7r0|0w7:7F046/0c0Q6~0h7@3Y6(7 3|6}6 7V7f0|7Y7%7)6L6{7,7_6:6=2%6T7s7?86777l8f7{7n7p8m36818t7^8r821^7X6J8b7*778e7.8h5x8j7=8z2}7-0(0Q7n7J8w800|6)8T83048R8M0@8B4o067(7w6O6Q7Z2,0g0|0u8P7}8#018v8i8d6.8g8^7X7$4X8D8E366O2q0c0E0b1e7v6T8G8~8X1^8k8^8o8@8(8*6T8,0q8I33944w8:8p7|858{87048W9z8F8}7/9g5:6^8.8N042U0E0s6:1O9x7~9H8$88913_937w9e9G9D7;048l9%7^9l7O7w7M9K3j0|9N9P0h9R9-3_8)6K8+0|8-9c6{0D9v8=8q7H8s9+8U9B8^9#9r2w7w908C8b9 0497999b9.9d9Faf5T719i9U6|8Za83v9}8c719pat9t3)9v7`8QaAax8`8J8|8O9$aP9A7haqa39?0L9O0q0I0EaL0,a9aT7C9Waj7)9!as8^awaa8Y8ya2av749;ay9@a#a%a_4XaCaH3:aFa}a48;8P8!aN8Vada;bd040k9X419Z9o0|an9aa}aea=8Lax8obcb39n7Qa09qb8aJbb7H8Sa@8AbeaxbsbhaV2^b52,aYa!a$a(7I8 a-8aakaraRat9/bubI9LbxbPb(7tb8bS9PbUb,41b4ala1aW710g6V046X0A1$6#bh9Ca+36bMb*9Vbibk3fbmbAam0(aoa}0A0I7m8^0A1=046Hco0S0|0obfb$bt9)9jba7{9{33ah8V89ca012i0|0Rcocq0y5!axcL04cwbLbgcJa?c77^a6bVa*cF6@9BcIc!3YcTcNcScPcRcJcTcVcJc9c-3:cZc)aX04c$b@agc*0Kc,c 71c/cO626F67aB4Y3Y0Y0m0|030n0f0b0X0I2k2m1P0h6o6q0W6v2q5@7^dy7Ub|779:a`8n7S6lbXacax0!cu3+dLbOd8dI7b5*5,dLc6dT36dO0|5rd!3y7DdH3rdJdXc58^d$044:c|bJbidSd4d06kd/cJaOd)3Yd=4_d^9Ibi0kd{3b7w8od~5-d:dNdP5we27!9Jd,8xbGa}dGdEd-dVdKegcJd=4~e6cb0keCaBec0i0|2Y2S0cdYcB04dCdLd74a0r5R0q2x2YeU5A1w5C2A2D2y0I1NeX0r5B0~e+0(0*0,04.
Taille de l'arbre

Voici l'algorithme récursif de la fonction taille :

Fonction taille(arbre):
Si arbre est vide :
    Renvoyer 0
Sinon :
    Renvoyer 1 + taille(arbre.filsG) + taille(arbre.filsD)
Fin Si
  • ImplĂ©menter la fonction taille en vous aidant de l'algorithme prĂ©cĂ©dent.

###(DĂ©s-)Active le code aprĂšs la ligne # Tests (insensible Ă  la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activĂ©, le texte copiĂ© dans le terminal est joint sur une seule ligne avant d'ĂȘtre copiĂ© dans le presse-papier
Évaluations restantes : 10/10

.128013rt=7CflbG)D1 {2e/vygj.:,8sw9nuph5aS(o3qNk_}i4+6P;Ă©cdm0050!0q0c0I0S0h0A0n0Z0h0I0A0A0d010c0S0F010406050A0E0#0#0I0b0t040J0L0h0E0`0L0D050r111315170 0F04051n1g1q0r1n0 0!0S0s0/0;0?0^0G0S0u0G0h1E0G0c0}050*0i0h0q1z0=0@011D1F1H1F0c1N1P1L0c0b1o0c0G0/1a0A0F0I0D0^0p011R1B010g0,0q0D0I0#0q1L1.1:1^1T1{1P1~200}0a0n0W0b0L0F0L0A0S1d0D0n0(1,0b0b0q0Z2l1g230D1o0r1*2y1%1)1(1M0!250^1H0D1}2i1L1w1y0:1S2I0S2K0D0L2O1L0F2r1o2w2y2$101/2m2Q1_2V0b140h0}0n0m2v2*0~2)242,1T2.2:2=0p2^1:2`2w2H012 0I2;040n0M332x0 362}0^393b0n0T3f352*373l2=0H3p3h3r3j380L2/3a2=0V3w2{2+1A2~3B303c0e3G3i3J3k3L3D3c0z3P3y3R3A3C3m0C3X2|3Z3t040m0$3(3I2R3!3M0m2@1h2_3x3)3;3+0m323_343{3:2-3T3b0m3e413g3H3s460}0m3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0m3%4G4k3K4s0p3.4M444O3M0p3^2$4q4x4D0p404Y4w3*4#494(4B4l4V4h4-4H4/3U0p4o4=4N3S4P4u4{4T4}4V4z504r4V4F554!4P4L594*4s0M4R5d4I3M0M4X3`4)5j3U0M4%5n4.4U5q4,5t4?5v3b0M4;5y4|3=5q4`5E515G5B4 5J565q545O5a5k585S5e5k5c2_1r2!1g2O2B0!1)2G3z0Z2W211o5(1p5$2(4i055.0(2#5z0^0P0}2}3p0n5o2-0Z0}0O0L0q0E0!63651T0|040x3/370B2=0n6o3p6f0^0A0!0}020N0E0L0c0X6w6y6A6C6z0X0L0i0v0)0n696b2G0!02030M0C0X0E2m150i2r0n0i2T0+2r6F6E6x6G6*0X3w6o6p5u5 0}0(0g6e6?1`0#0}0Q0Q2T2k706q6|6h0K755~010i6h0A0q0h6`5_760}0y6{7a0D0}0s3a7m5F0L0}0d7s5K0P6704692K795F6h7l4i646|7o04270A0j7x377u047w7I6r017z681e0q7E5K7G7Q4x0}7N0l7)3Z7S7U2$7J7a7Y7B7!7$376h0k7.3;6h6j4p6;847?5F7c0}7e7g7{3z7S0w8c3*890)0Q7q0h8g800}787i7n7p7r8r7F0}7~83856=7a88048a7h2(6|8e8n2-8i0c0Q7N7P8v7%8p8K2~7+0,7O8U0^7}6:8A865K8D8F8Z018J8R3s8M8O8X7-8/3z778,7L7,8,8#4p06847W60046_7 2-0g0}0u8j8l8~8T8^3Z8*7f8G5!7j040k824Y8%8(37942r0c0E0b1f7V6|9i8b9g3;8.8H8s049d90926|94969A7n998E9c8u9H8w048q9W8)7d9j9e047H7=7W7L2V0E0s7f1P8k9V9l7a7}9p3`9r7W9C9k347W9G9^5F7L9K9+8I7v978V049.9:0h9=a73`916;936^0qa02x9s4x9S9b8N8P9(9Za49#8i9D9!7|8x9{429}9N0}9v9x9za88C9$aCaz7R0}8f9E8L7M8X8Q4Yak8B5F9Oaoab3k9S7eavaZax8,9 9(9*2_ar8had0L9/0q0I0E8=0-a!aS8_aF8$8A9~aQap5}7taU8{8Wb3a+8-aa9Qa50}aea b1aw9LalaJ95a*bm5K0Dat8j8}aW6g9faD3za?bE8!b78zb9bvaL9ybjbJbH7/bfbK38bh0A8@a#9M7@anbca`3}a-bC8?a;bXbTb53Z7(by8:a|a~b0b2b!9(9ob885baaBbca2bWbU3}bZb#a_c77Tbj9-a}9:b}bDb$bub(bwb*7W0g6~04700A1%74bX8`b;bbc0aG3gaIcobQaNcd6|0A0I7+8,0A1?046.cP0S0}0oa=cCbXa3a17K9a9U8mcz8p8yc91_2j0}0RcPcR0y64bXc:04cXcBc58,c#2x9,c(a/bic+9Yc-b?3;c{c=c`c@c_c.1Tc{c}dh0^b=c$7ad1bdbzd4b~ccdo9X0Kd9dw5Kdcc?6v6,6A63064Z3Za)cq7K9S0*0,1Pb:dlbY046Y2rcDc2am040SdM9IdW7#b_8d7v7;cK7@7A7Cd*dT81c2b%a(aK0)aMbj0#cV045h9|cnd{047f7e9(cE0~cGe6cId e15m34b+1_7S0Ucg0}dPagd?da1_cAdT7Ld)d0c8etacaub~b4dAaEd8dzaqceend+a{eqdRd7ayeG7*dV0b6ZeseTbV04aVewdtcleBbLeI3wdI7W0Z0m0}030n0f0b0Y0I2l2n1Q0h6R6T0Xey4Sb`f3aObecfeNca7_6OdSe*01e04fa@bgfc6cfeeZ3;fh045sfoeu7keofl6deR8,fq5DftbF9na^fD3k7ZfdfzbXfq5IfH017}0kfGeKc%fxfnd26|fq5xfPb^f7dsaY0-dvfUdpblf(b`6NfmfLdTfq5Nf$8x0keJ0~dJ3}0i0}2Z2T0cfXdrb`ePeYfY9_bGffexeWdXd7f}3G0r5{0q2y2Zgo5%1x5)2B2E2z0I1Ogr0r5(0 gB0)0+0-04.
Taille de l'arbre

Voici l'algorithme récursif de la fonction hauteur : 

Fonction hauteur(arbre):
Si arbre est vide :
    Renvoyer 0
Sinon :
    Renvoyer 1 + max(hauteur(arbre.filsG) , hauteur(arbre.filsD))
Fin Si
  • ImplĂ©menter la fonction hauteur

###(DĂ©s-)Active le code aprĂšs la ligne # Tests (insensible Ă  la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activĂ©, le texte copiĂ© dans le terminal est joint sur une seule ligne avant d'ĂȘtre copiĂ© dans le presse-papier
Évaluations restantes : 10/10

.128013rt=7CflbG)D1 {2e/vygj.:,8sw9nuph5aS(o3qNk_}i4+6P;Ă©cdxm0050!0q0c0I0S0h0A0n0Z0h0I0A0A0d010c0S0F010406050A0E0$0$0I0b0t040J0L0h0E0{0L0D050r12141618100F04051o1h1r0r1o100!0S0s0:0=0@0_0G0S0u0G0h1F0G0c0~050+0i0h0q1A0?0^011E1G1I1G0c1O1Q1M0c0b1p0c0G0:1b0A0F0I0D0_0p011S1C010g0-0q0D0I0$0q1M1/1;1_1U1|1Q1 210~0a0n0W0b0L0F0L0A0S1e0D0n0)1-0b0b0q0Z2m1h240D1p0r1+2z1(1*1)1N0!260_1I0D1~2j1M1x1z0;1T2J0S2L0D0L2P1M0F2s1p2x2z2%111:2n2R1`2W0b150h0~0n0m2w2+0 2*252-1U2/2;2?0p2_1;2{2x2I01300I2=040n0M342y10372~0_3a3c0n0T3g362+383m2?0H3q3i3s3k390L2:3b2?0V3x2|2,1B2 3C313d0e3H3j3K3l3M3E3d0z3Q3z3S3B3D3n0C3Y2}3!3u040m0%3)3J2S3#3N0m2^1i2`3y3*3=3,0m333`353|3;2.3U3c0m3f423h3I3t470~0m3p4b3r3}463$4g3w4j444e4n3-3G4q4d3A3 3P4w3R3~4f3-3X4B3Z4D4t0m3(4H4l3L4t0p3/4N454P3N0p3_2%4r4y4E0p414Z4x3+4$4a4)4C4m4W4i4.4I4:3V0p4p4?4O3T4Q4v4|4U4~4W4A514s4W4G564#4Q4M5a4+4t0M4S5e4J3N0M4Y3{4*5k3V0M4(5o4/4V5r4-5u4@5w3c0M4=5z4}3?5r4{5F525H5C505K575r555P5b5l595T5f5l5d2`1s2#1h2P2C0!1*2H3A0Z2X221p5)1q5%2)4j055/0)2$5A0_0P0~2~3q0n5p2.0Z0~0O0L0q0E0!64661U0}040x3:380B2?0n6p3q6g0_0A0!0~020N0E0L0c0X6x6z6B6D6A0X0L0i0v0*0n6a6c2H0!02030M0C0X0E2n160i2s0n0i2U0,2s6G6F6y6H6+0X3x6p6q5v600~0)0g6f6@1{0$0~0Q0Q2U2l716r6}6i0K765 010i6i0A0q0h6{5`770~0y6|7b0D0~0s3b7n5G0L0~0d7t5L0P68046a2L7a5G6i7m4j656}7p04280A0j7y387v047x7J6s017A691f0q7F5L7H7R4y0~7O0l7*3!7T7V2%7K7b7Z7C7#7%386i0k7/3=6i6k4q6=857@5G7d0~7f7h7|3A7T0w8d3+8a0*0Q7r0h8h810~797j7o7q7s8s7G0~7 84866?7b89048b7i2)6}8f8o2.8j0c0Q7O7Q8w7(8q8L2 7,0-7P8V0_7~6;8B875L8E8G8!018K8S3t8N8P8Y7.8:3A788-7M7-8-8$4q06857X61046`802.0g0~0u8k8m8 8U8_3!8+7g8H5#7k040k834Z8(8)38952s0c0E0b1g7W6}9j8c9h3=8/8I8t049e91936}95979B7o9a8F9d8v9I8x048r9X8*7e9k9f047I7?7X7M2W0E0s7g1Q8l9W9m7b7~9q3{9s7X9D9l357X9H9_5G7M9L9,8J7w988W049/9;0h9?a83{926=946_0qa12y9t4y9T9c8O8Q9)9!a59$8j9E9#7}8y9|439~9O0~9w9y9Aa98D9%aDaA7S0~8g9F8M7N8Y8R4Zal8C5G9Papac3l9T7fawa!ay8-a09)9+2`as8iae0L9:0q0I0E8?0.a#aT8`aG8%8B9 aRaq5~7uaV8|8Xb4a,8.ab9Ra60~afb0b2ax9MamaK96a+bn5L0Dau8k8~aX6h9gaE3Aa@bF8#b88AbabwaM9zbkbKbI7:bgbL39bi0A8^a$9N7^aobda{3~a.bD8@a=bYbUb63!7)bz8;a}a b1b3b#9)9pb986bbaCbda3bXbV3~b!b$a`c87Ubk9.a~9;b~bEb%bvb)bxb+7X0g6 04710A1(75bY8{b=bcc1aH3haJcpbRaOce6}0A0I7,8-0A1@046/cQ0S0~0oa?cDbYa4a27L9b9V8ncA8q8zca1`2k0~0RcQcS0y65bYc;04cYcCc68-c$2y9-c)a:bjc,9Zc.b@3=c|c?c{c^c`c/1Uc|c~di0_b?c%7bd2bebAd5b cddp9Y0Kdadx5Lddc@6w6-6B64064!3!a*cr7L9T0Gb10c6c0bb;dmbZ046Z2scEc3an040SdN9JdZ7$b`8e7w7=cL7^7B7Dd-dW82c3b(a)aL0*aNbk0$cW045i9}cod~047g7fbkd{bOc4bQe0bSd.3!e34gbk7T0Uch0i0~150#dVdbaYdQ1ddTewdBb{d,d1c9exadavb b5eDb7d90ka_35b,eydReBd8azeNa|eFc#eHeZcb04eKcmeIbMePdA3hdJ7X0Z0m0~030n0f0b0Y0I2m2o1R0h6S6U0Xe#5jaYf7d=bfcgeke)6O6deCd36}em3-a^bh7`6Pfids38fl5te(1`b_aPbofpfheX8-fl5EfwbG9oeRfj9Jfg6efDbYfl5JfHe.0keQch7!fqfPdWfl5yfT01fyfbdtaZ0.dwarcfd;eSd4fBfOd`bHe-01fl5Of(7~fV3xdK3~es042!2U0cfrf@0+0-1Qgbc(dY0b6!d_f|g13H0r5|0q2z2!gr5(1y5*2C2F2A0I1Pgu0r5)10gE0*0,0.04.
Activité 5 - Parcours d'un arbre

On parcours un arbre pour "afficher" ou tester toutes les valeurs d'un arbres. Il existe 4 type de parcours :

On donne les algorithmes de parcours suivants :

Fonction parcours_prefixe(arbre):
Si arbre n'est pas vide :
    Noeud ← arbre.racine
    Afficher Noeud.valeur
    parcours_prefixe(arbre.gauche)
    parcours_prefixe(arbre.droit)
Fin Si

Fonction parcours_infixe(arbre):
Si arbre n'est pas vide :
    Noeud ← arbre.racine
    parcours_infixe(arbre.gauche)
    Afficher Noeud.valeur
    parcours_infixe(arbre.droit)
Fin Si

Fonction parcours_suffixe(arbre):
Si arbre n'est pas vide :
    Noeud ← arbre.racine
    parcours_suffixe(arbre.gauche)
    parcours_suffixe(arbre.droit)
    Afficher Noeud.valeur
Fin Si

Fonction parcours_largeur(arbre):
Enfiler(f,arbre.racine)
Tant que f est non vide :
    x ← Defiler(f)
    Afficher x.valeur
    Si x.gauche est non nul :
    filsG ← x.gauche
    Enfiler(f,filsG.racine)
    Fin Si
    Si x.droit est non nul :
    filsD ← x.droit
    Enfiler(f,filsD.racine)
    Fin Si 
Fin Tant que
  • Appliquez les 4 algorithmes "Ă  la main" sur l'arbre binaire suivant et donner les valeurs dans l'ordre :

Correction
  • PrĂ©fixe : A B C E D F G I H J
  • Indixe : C E B D A I G F H J
  • Suffixe : E C D B I G J H F A
  • Largeur : A B F C D G H E I J
Activité 6 - Introduction aux arbres binaires de recherche (ABR)

Notebook Corrigé

DĂ©finition d'un Arbre binaire de recherche (ABR)

Un arbre binaire de recherche est un arbre binaire dont les valeurs peuvent ĂȘtre comparĂ©es (entiers, flottants, caractĂšres, chaĂźnes...) avec la rĂšgle suivante :

Pour tout noeud de l'arbre :

  • Toutes les valeurs situĂ©es dans le sous-arbre gauche sont plus petites que la valeur du noeud.
  • Toutes les valeurs situĂ©es dans le sous-arbre droit sont plus grandes que la valeur du noeud.

Activité 7 - Algorithmes de recherche dans un ABR

Complétez l'activité précédente avec les autres algorithmes de recherche.

Notebook Corrigé

Application : algorithme de Huffman
Introduction

On cherche Ă  crypter le mot Anticonstitutionnel sous forme d’une sĂ©rie de 0 et de 1.

  1. Proposez un cryptage possible.
  2. Quels peuvent ĂȘtre les inconvĂ©nients d’un tel cryptage?

Le principe de l’algorithme de Huffman

L’algorithme de Huffman (ou codage de Huffman) permet aussi d’encoder un message texte sous forme d’une sĂ©rie de 0 et de 1. La diffĂ©rence, c’est que ce codage s’appuie sur le nombre d’occurrence de chaque caractĂšre.

L’idĂ©e consiste Ă  coder les caractĂšres les plus frĂ©quents par des mots binaires plus courts que les caractĂšres les moins frĂ©quents. Si bien que chaque caractĂšre sera codĂ© avec un nombre diffĂ©rent de bits que d’autres caractĂšres du mĂȘme texte, compliquant sĂ©rieusement le dĂ©codage par une personne malveillante ayant interceptĂ© le message.

Arbre binaire de Huffman

Prenons toujours l’exemple du mot Anticonstitutionnel.

Comptage des occurrences

On indique pour chaque caractĂšre du mot le nombre d’occurrence de ce caractĂšre dans le mot. (on pourra mettre les rĂ©sultats sous forme d’un tableau, d’un dictionnaire
)

Tri par ordre croissant

On range cette « liste » dans l’ordre croissant (ou dĂ©croissant) des nombres d’ occurrences.

Construction de l’arbre binaire « de Huffman »

On crĂ©e des feuilles pour chaque Ă©lĂ©ment de la « liste », chacune Ă©tiquetĂ©e par un couple (caractĂšre, nombre d’occurrence).

On sĂ©lectionne les 2 feuilles dont le nombre d’occurrence est le plus petit.

On fusionne ces 2 feuilles dans un nouvel arbre. L’étiquette de ce nouvel arbre sera (’’,somme des poids des deux feuilles)

On supprime les 2 feuilles de la « liste » et on insÚre, à la bonne place, le nouvel arbre dans cette liste.

Par rĂ©currence, on « vide » la liste et l’ensemble des feuilles et des arbres qui s’y trouve. Au final, on obtient un arbre unique : l’arbre d’Huffman.

Mise en application : Codage

On peut maintenant utiliser cet arbre pour coder chaque caractùre : en parcourant l’arbre de la racine à une feuille, on notera 0 si on part à gauche ou 1 si on part à droite. On obtient ainsi la table de codage.

On obtient ainsi le codage d'Anticonstitutionnel :

11100011011011101111101001010110100011101101111010100000001

Mise en application : DĂ©codage

Un algorithme de cryptage ne servirait à rien si on ne pouvait pas décoder le message crypté.

Dans notre cas, l’arbre de Huffman va permettre aussi bien de coder que de dĂ©coder un message, tout simplement en prenant les nombres 0 et 1 les uns Ă  la suite des autres, on parcourt l’arbre en partant de la racine de l’arbre et en allant jusqu’à une feuille, puis en recommençant Ă  partir de la racine.

Activité 8 - Utilisation de l'algorithmes de Huffman

1. Codage
En suivant l’algorithme de Huffman, Dessiner les arbres des Huffman, et donner les tables de codages des mots suivants :
- Attention
- Institutionnalisation
2. DĂ©codage
On vous donne la sĂ©rie binaire et l’arbre de Huffman suivants :
110101101101001001111000010110011001111010101111111100100111010111011101110101000010011001100000001
Décoder la série binaire et donner le texte en clair.






Correction

1. Codage

En suivant l’algorithme de Huffman, Dessiner les arbres des Huffman, et donner les tables de codages des mots suivants :
- Attention

- Institutionnalisation

2. DĂ©codage
On vous donne la sĂ©rie binaire et l’arbre de Huffman suivants :
110101101101001001111000010110011001111010101111111100100111010111011101110101000010011001100000001





Décoder la série binaire et donner le texte en clair.
'Warriors deux mille vingt'

Activité 9 - Huffman avec Python

Version complĂšte : Notebook
Version Ă  trou : Notebook
Corrigé : Corrigé