Aller au contenu

Squelette d'arbre binaire

Définition : 😀 Arbre binaire non étiqueté

Un arbre binaire non étiqueté est simplement un arbre binaire pour lequel chaque nœud ne porte aucune valeur. On appellera cette structure un squelette que l'on notera en abrégé skel (pour skeleton en anglais).

👍 Dans la suite des exercices, le symbole 😀 indiquera un exercice en lien avec un arbre binaire non étiqueté, alias squelette.

Modélisation des squelettes

Dans cet exercice, on modélisera les arbres binaires non étiquetés avec des tuples, de la façon suivante :

  • le squelette vide sera modélisé par (), le tuple vide, de taille 0 et de hauteur 0.
  • un squelette non vide sera modélisé par (gauche, droite), un tuple à deux éléments représentant respectivement le sous-arbre à gauche et celui à droite avec des tuples.

On peut résumer cette modélisation par () | (⋅, ⋅) qui se lit () ou un tuple à deux éléments ; de manière inductive.

Exemples

Ci-dessous un terminal pour générer des exemples aléatoires.

  • Vous pouvez générer un squelette à n nœuds.
    • Conseil : choisir n égal à 2 ou 3, puis 4 ou 5, puis 7 ou 8.
  • Vous pouvez ensuite le dessiner.
    • Exercice : d'après le dessin, construire la représentation à base de tuple.
  • Vous pouvez ensuite vérifier votre proposition.
    • Soit en faisant un test d'égalité,
    • soit en affichant la réponse.

Voici un exemple d'entrainement possible :

🐍 Console Python
>>> skel = skel_aléatoire(4)
>>> dessine(skel)  # Un résultat →
>>> # Chercher ensuite sa représentation
>>> ma_proposition = (((()),()), ())  # juste ???
>>> # On teste
>>> skel == ma_proposition
False
>>> # On révèle ...
>>> skel  # la bonne réponse
((((), ()), ()), ((), ()))

Expérience

Trois fonctions disponibles uniquement dans ce terminal, pour avoir de l'aide :

🐍 Console Python
>>> help(skel_aléatoire)
>>> help(dessine)
>>> help(repr_svg)

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

Le squelette sera dessiné ici.

Objectifs des exercices

  1. Coder des fonctions simples sur les squelettes (taille, hauteur) pour se familiariser avec la modélisation.
  2. Coder une fonction vers_skel qui extrait le squelette d'un arbre binaire.

Exercice 1

Coder des fonctions taille et hauteur qui prennent en paramètre un squelette skel modélisé par () | (⋅, ⋅) et qui renvoient respectivement la taille et la hauteur de cet arbre binaire non étiqueté.

  • ⚠ On attend une docstring correcte.
  • 👍 Lire les messages en cas d'erreur à ce sujet !
  • 👍 Vous pourrez aussi utiliser le terminal de dessin dans le cadre au-dessus !
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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 : ∞/∞
.128013x,59/fq78r;nb o=ylaepcwgu)vd4613kRmhtsP(S0+2-i:050C0u0L0t0U0s0M0o0w0s0t0M0M0q010L0U0v010406050M0z0J0J0t0k0r040P0p0s0z0:0p0m050f0`0|0~100^0v04051g191j0f1g0^0C0U0B0(0*0,0.0K0U0y0K0s1x0K0L0?050Z0n0s0u1s0+0-011w1y1A1y0L1G1I1E0L0k1h0L0K1K1u010g0#0u0m0t0J0u010(130M0v0t0m0.0S1E1=1@1#1M1(1I1+1-0?0a0o0N0k0p0v0p0M0U160m0o0X1:0k0k0u0w2e191|0m1h0f1Z2r1W1Y1X1F0C1~0.1A0m1*2b1E1p1r0)1L2B0U2D0m0p2H1E0v2k1h2p2r2V0_1?2f2J1$2O0k0}0s0?0o0F2o2Z0@2Y1}2#1M2%2)2+0S2.1@2:2p2A012^0t2*040o0G2|2q0^2 2?0.32340o0D382~2Z303e2+0d3i3a3k3c310p2(332+0E3p2;2!1t2@3u2_350i3z3b3C3d3E3w350j3I3r3K3t3v3f0e3Q2=3S3m040F0Q3X3B2K3T3F0F2-1a2/3q3Y3*3!0F2{3/2}3;3)2$3M340F373`393A3l3 0?0F3h433j3=3~3U483o4b3|464f3#3y4b1k2T192H2u0C1Y2z3s0w2P1.1h4s1i4q2X4o4y0X2U3R3*0H0?0X0g3i453s0x2+4Q3J3?0g0?0Z0#1I4V4K1$0=040O4%4d2@0?0M0H0u0s4-3}1M4*0A3i0o4R3S0p0?0T020y0L0l4}4 3?0n0?2M0L4^304*0V3p0o5k4~4W1$0M1`04010I1*0B0p0U1J0*0o4!0s1I2g0z0o0M0h0z4?0Y0L1J4;4?015j5l591$4M040U4P4b5m4(4/045O4@5Z5T1M51040q0q585n4`0?0O0A5i4i5l5|5!4.0.5V2k0L0z0k185*5=0.0J0U0?3%5{5S68015V4?0M0u5f3s5h5R5}5~4_3d0?0y0t0z0w0K6l4o6g4*0c5;5#6t040C282d6A2V6r305-5:676G314:4=5)2V066q5k5+600?6264666N6$016a486F5 015-0R6;6s6U045B4$6B6T4*4,6 6=0m6u6w6y6M2/6-4{6_6P0?6^6S744Z0!5C792}7b5@6m3Z4N6K5M7q3*7c4i064j3s5V4O7v1$4T357E2@4Y040K6w5M647I0.717Q6{5(7T7x6,6g5-5355577h6`0m5b5W0m5e736`6o6e6#6g5p0?5s5u5w5y0t0o7M150u645E5G5I5K1S5N6W5Q7=6O7B5c5Y7Y6T755%6W7d3s6Q6R8h6=715_6p5}6-610Y6*8m3S6/046d6Y5|8w0?6j7m2q7o045`8F6!6-8j6v6x6z7W0?6E7(3l7s5w7u8Z8n0?8p2/8d7r8k4?8u8G6g8x63658A3*8C3.8q6`6@8`2$7+0}0b8W4+7T8j807O0k96722X6g8S778V7/5g0?0A8Y8~8!7L7N829c9k6n7p9v8.6J8$8K4J8r9m4|4i194H0u2r2S9K4r1q4t2u2x2s0t1H9N0f4s0^9X0Y7k0M04.

Exercice 2

Coder une fonction vers_skel qui prend en paramètre un arbre binaire défini à l'aide de la classe Noeud et qui renvoie son squelette modélisé par () | (⋅, ⋅).

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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 : ∞/∞
.128013.8901,59/f.q78rnb N_o|=ylaepcwgu)vd4613kRméhtsP(Sà2i:050F0x0P0w0W0v0Q0o0z0v0w0Q0Q0t010P0W0y010406050Q0C0M0M0w0l0u040T0r0v0C0=0r0m050f0|0~10120`0y04051i1b1l0f1i0`0F0W0E0*0,0.0:0O0W0B0O0v1z0O0P0^050#0n0v0x1u0-0/011y1A1C1A0P1I1K1G0P0l1j0P0O1M1w010g0%0x0m0w0M0x010*150Q0y0w0m0:0V1G1@1_1%1O1*1K1-1/0^0a0o0R0l0r0y0r0Q0W180m0o0Z1=0l0l0x0z2g1b1~0m1j0f1#2t1Y1!1Z1H0F200:1C0m1,2d1G1r1t0+1N2D0W2F0m0r2J1G0y2m1j2r2t2X0{1^2h2L1(2Q0l0 0v0^0I2q2#0_2!1 2%1O2)2+0^0V2/1_2;2r2C012_0w2,040J2}2s0`302@0:33350G382 2#313e0^0d3h3a3j3c320r2*340^0H3o2=2$1v2^3t2`040j3y3b3B3d3D3v040k3H3q3J3s3u350e3h1m2V1b2J2w0F1!2B3r0z2R1:1j3!1k3Y2Z1c2:053*0Z2W3Q2M010K0^0Z0g3W3I3|0A0^0o423{2(0g0^0E0x0l0Q0q0Q0K0x0v482?3R0@040S4m3A3|0m0^0w0n4s314p0D0X3P4n44460o4I4z3r0Q0F0^014P4E4t1(4M4H4I0L1,0E0r0W1L1K0o0Q0i0C4k0!0P1L0M2R0N1C0Q0N0o0w4d0z0o0S0D0o0s4}0b0c0o0b0D4R314U044I4I2j4x0o0X0o0C2h100n2m0o0n2O0$5n0F0N1*0m0W0o0U0o0v000$2j2j0,201L0p0r0x0C0F584L4N5b5c4P013o5c47431(3~040W413=2~5X492^4w4y5(2s5*4F1(0r455#0Q3h5;4S1O0K0z0^5J2F4K4o0^4D5/0_5W5W3z315!2m0P0C0l1a685|4A0^4~5V5c6c3r5!4k0Q0x643|4p672X066a6q5Y5~0^6f6h6j2X6l3r4p4r686r3R4v044d4f4h4j4l6Q6F0:6O6x2(5-6(1O0r0^0h6+3d0^0B0w0C0z0O6w6!5+6$0^0D0c5{6R4u4c4e4g4i4k6:016%6|5=5,044x7a6-046/7d5}6;040F2a2f6{2Z6#7b6 57680`0f3^0x2t2U7D3Z1s3#2w2z2u4x1K2t3!7A0Z0#0%0Q04.