Arbre généalogique

Un généalogiste amateur décide de représenter ses travaux avec Python.

Etant face à l'arbre généalogique des parents, grands-parents, etc d'un individu, il utilise pour ce faire des arbres binaires représentés ainsi :

l'arbre binaire vide est représenté par None ;
un arbre binaire non vide est représenté par un tuple de trois éléments (sag, personne, sad) dans lequel :
- sag est le sous-arbre gauche ;
- personne est le nom de la personne à la racine de l'arbre ;
- sad est le sous-arbre droit.

Il suit la convention de la généalogique qui veut que les pères soient placés sur la gauche et les mères sur la droite.

Ainsi l'arbre généalogique de base :

Arbre de base

Pierre         Pauline
    \         /
     \       /
      Jacques

sera représenté en Python par :

Arbre de base en Python

((None, "Pierre", None), "Jacques", (None, "Pauline", None))

Il arrive lors de la construction d'un arbre généalogique que l'on ignore l'ascendance d'une personne : l'arbre est interrompu sur certaines branches et est donc déséquilibré. Par exemple :

Arbre déséquilibré

Pierre      ?    ?         Martine
    \      /      \       /
     \    /        \     /
      Paul          Aline
          \        /
           \      /
            Pierre        ?
                \        /
                 \      /
                  Marion

Dans ce cas, les parents inconnus sont représentés par des arbres vides :

Arbre déséquilibré en Python

((((None, "Pierre", None), "Paul", None), "Pierre", (None, "Aline", (None, "Martine", None))), "Marion", None)

On cherche dans cet exercice à effectuer différents calculs sur des arbres généalogiques.

1. Personnes présentes

Écrire la fonction nb_presents qui prend en paramètre un tuple arbre représentant un arbre généalogique et renvoie le nombre de personnes présentes dans cet arbre.

Exemples

>>> une_gen = (None, "Moi", None)
>>> nb_presents(une_gen)
1
>>> deux_gen = ((None, "Papa", None), "Moi", (None, "Maman", None))
>>> nb_presents(deux_gen)
3
>>> trois_gen = ((None, "Papa", (None, "Mamy P.", None)), "Moi", ((None, "Papy M.", None), "Maman", None))
>>> nb_presents(trois_gen)
5

Évaluations restantes : 10/10

.128013ben,4vi3mo5_tPhklpwNf(: cga=ry0Su/2)s1+d050O0c0n0B0h0r0L0y0z0r0B0L0L0C010n0h0s010406050L0H0j0j0B0D0E040G0k0r0H0)0k0d050I0:0=0@0_0.0s040519121c0I190.0O0h0g0X0Z0#0%0p0h0A0p0r1q0p0n0,050S0b0r0c1l0!0$011p1r1t1r0n1z1B1x0n0D1a0n0p0X0|0L0s0B0d0%0J011D1n010v0U0c0d0B0j0c1x1W1Y1%1F1*1B1-1/0,0a0y0o0D0k0s0k0L0h0 0d0y0Q1U0D0D0c0z27121=0d1a0I1S2k1P1R1Q1y0O1@0%1t0d1,241x1i1k0Y1E2u0h2w0d0k2A1x0s2d1a2i2k2O0/1X282C1(2H0D0?0r0,0M2h2S0-2R1?2U1F2W2Y0,0J2$1Y2(2i2t012-0B2Z040i2;2j0.2@2+0%2`2|0f2 2?2S2^350,0l381d2M122A2n0O1R2s33010z2I1:1a3j1b3h2Q132%053q0Q2N3a3o0q0,0Q0v3f321m1F0t0,0y3K3E3M340v0,0d0b0m2L0c0L1,0n0L3R2*3T010+040w3*2T3,0d0,0@0b2d3;2^3.0K0x38060y433Q3L2D013G040h3J3y2=453S473@043_3{4d2j4f3+470k3O4a3)4m044o3=470q0z0,0u100c3|3o3.404v42444M2)4y1(492d0n0H0D114v4x2^0j0h0,0F414N462V0,0L0B0A4G3,3.0e384Y3o4i0s0c0D0L102w4:474=4@4O3b4,0B0O544*1F0k0,0C5a4g4+4j0D3`4F4K4)5h1F4R0R4U4W2O4^3,4!2!5g4p1(5d040N5A4P2,3W3Y3!3$0d3(511(3.3:4v554_574/5T5b0%3~5G2^5D5F4X5U3?5J3Z2d5M5O5Y5p5!0,5S2Q5Z2_57595=5B1F5#4K123B0c2k3!2k3u2l3l122o6d0B1A663i1j2(0I0Q0S0U0L04.

2. Nombre de générations

On définit le nombre de générations d'un arbre généalogique comme le nombre maximal de personnes rencontrées en remontant depuis la racine de l'arbre jusqu'à un ancêtre. Un arbre généalogique ne comptant qu'une seule personne a donc un nombre de génération égal à 1.

Écrire la fonction nb_generations qui prend en paramètre un tuple arbre représentant un arbre généalogique et renvoie sa hauteur.

Exemples

>>> une_gen = (None, "Moi", None)
>>> nb_generations(une_gen)
1
>>> deux_gen = ((None, "Papa", None), "Moi", (None, "Maman", None))
>>> nb_generations(deux_gen)
2
>>> trois_gen = ((None, "Papa", (None, "Mamy P.", None)), "Moi", ((None, "Papy M.", None), "Maman", None))
>>> nb_generations(trois_gen)
3

Évaluations restantes : 10/10

.128013ben,4vi3mo5_txPhklpwNf(: cga=ry0Su/2)s1+d050P0c0n0C0h0s0M0z0A0s0C0M0M0D010n0h0t010406050M0I0j0j0C0E0F040H0k0s0I0*0k0d050J0;0?0^0`0/0t04051a131d0J1a0/0P0h0g0Y0!0$0(0q0h0B0q0s1r0q0n0-050T0b0s0c1m0#0%011q1s1u1s0n1A1C1y0n0E1b0n0q0Y0}0M0t0C0d0(0K011E1o010w0V0c0d0C0j0c1y1X1Z1(1G1+1C1.1:0-0a0z0p0E0k0t0k0M0h100d0z0R1V0E0E0c0A28131?0d1b0J1T2l1Q1S1R1z0P1^0(1u0d1-251y1j1l0Z1F2v0h2x0d0k2B1y0t2e1b2j2l2P0:1Y292D1)2I0E0@0s0-0N2i2T0.2S1@2V1G2X2Z0-0K2%1Z2)2j2u012.0C2!040i2=2k0/2^2,0(2{2}0f302@2T2_360-0l391e2N132B2o0P1S2t34010A2J1;1b3k1c3i2R142(053r0R2O3b3p0r0-0R0w3g331n1G0u0-0z3L3F3N350w0-0d0b0m0B1-0c0E0C280M3S2+3U010,040x3,2U3.0d0-0^0b2e3?2_3:0L0y39060z453R3M2E013H040h3K3z2?473T493_043{3}4f2k4h3-490k3P4c3+4o044q3@490r0A0-0v110c3~3p3:424x44464O2*4A1)4b2e0n0I0E124x4z2_0j0h0-0G434P482W0-0M0C0B4I3.3:0e394!3p4k0t3%0M112x4=494@4_4Q3c4.0C0P554,1G0k0-0D5b4i4-4l0E3|4H4M4+5i1G4T0S4W4Y2P4`3.4$2#5h4r1)5e040O5B4R2-0b0-0@0o521)3:3=4x564{3X3Z3#2x3(3*5O1G5Q5#35584;5S5c0(404^4Z5T3^5V3!3$5Z0h114w2R5-3/0-5R5~5q5)044/5a5,6460040L0L43133C0c2l2M6i3j1k3l2o2r2m0C1B6l0J3k0/6v0S0U0W04.

3. Compter les prénoms identiques

Il arrive que certains prénoms apparaissent plusieurs fois dans un arbre généalogique.

Écrire la fonction compte qui prend en paramètre un tuple arbre représentant un arbre généalogique ainsi qu'un nom (au format str) et renvoie le nombre d'apparitions de ce nom dans l'arbre généalogique.

Exemples

>>> une_gen = (None, "Pierre", None)
>>> compte(une_gen, "Pierre")
1
>>> compte(une_gen, "Martin")
0
>>> deux_gen = ((None, "Paul", None), "Pierre", (None, "Jacqueline", None))
>>> compte(deux_gen, "Pierre")
1
>>> trois_gen = (((None, "Pierre", (None, "Jacqueline", None)), "Paul", None), "Pierre", ((None, "Pierre", None), "Jacqueline", None))
>>> compte(trois_gen, "Pierre")
3
>>> compte(trois_gen, "Jacqueline")
2

Évaluations restantes : 10/10

.128013ben,4vi+3mo5tPhklpwNf(: cga=ry0S6u/72)s18d050Q0c0n0B0h0r0N0y0z0r0B0N0N0C010n0h0s010406050N0I0k0k0B0D0E040G0l0r0I0+0l0d050J0=0@0_0{0:0s04051b141e0J1b0:0Q0h0g0Z0#0%0)0p0h0A0p0r1s0p0n0.050U0b0r0c1n0$0(011r1t1v1t0n1B1D1z0n0D1c0n0p0Z0~0N0s0B0d0)0L011F1p010v0W0c0d0B0k0c1z1Y1!1)1H1,1D1/1;0.0a0y0o0D0l0s0l0N0h110d0y0S1W0D0D0c0z29141@0d1c0J1U2m1R1T1S1A0Q1_0)1v0d1.261z1k1m0!1G2w0h2y0d0l2C1z0s2f1c2k2m2Q0;1Z2a2E1*2J0D0^0r0.0O2j2U0/2T1^2W1H2Y2!0.0L2(1!2*2k2v012/0B2#040j2?2l0:2_2-0)2|2~0f312^2U2`370.0m3a333c352{0l2Z2}0.0H3h2+2V1o2.3m2:040K3r343u363w3o040P3a1f2O142C2p0Q1T2u3k0z2K1=1c3M1d3K2S152)053S0S2P3j3C010q0.0S0v3I3B2F010t0.0y3;3*3?0d0v0.3S0k0s0n0c3{2,3+0-040w463t3}0.0_0b2f4c2`490e3a3`3=2X0.2J0k4j3k490M0x3h0y4A4o3|1*3-040h3:3!2@4C474e044g4i4J2l4L4d1*0l3^4G0N4n3s2`0q0z0.0u12454R3)4M1*494y4-064B4^4T4$0.2f0n0I0D134-4`3k0k0h0.0F4z4B4#3k0d0.0N0B0A4u480.4m525b3+5d040s0c0D0N122y5i3?4l4!4p2.5e0B0Q5A4D1H0l0.0C5G4/5C4O0D4h4,2Q4@5a5B364r5M4U5I5K5Z2`5557594A5n3?4F4H5%5c0.5r5t5v5S2)533+5J040C5L5m5W2{4r0l4t4-5-4:0.4=5T4_5V5H5X04512Q5|3?5~616k691H5)042%4?4^6q0)4F4}4 6j5{6x646i5;5}0.0i6H4N41435`2@6E494b68635p5f5h6U6g015z626!5p4s5x6a040M6L4V6J6/5O6N446+1H6S6_6h5f5F6Z5N0)6$6p6V65672S634w3r0J3%0c2m2N7e3L1l3N2p2s2n0B1C7h0J3M0:7r0T0V0X04.

4. Extraire une génération

On appelle génération $n$ dans un arbre, l'ensemble des personnes définies comme suit :

la personne à la racine de l'arbre forme la génération $1$ ;
ses parents forment la génération $2$ ;
ses grands-parents la génération $3$ ;
...

Écrire la fonction generation qui prend en paramètre un tuple arbre représentant un arbre généalogique ainsi qu'un entier strictement positif n et renvoie la liste des noms des personnes situés à la génération n.

La liste sera ordonnée de façon à correspondre à la représentation graphique de l'arbre : le nom d'une personne apparaissant sur la gauche sera placé plus tôt dans la liste que le nom d'une personne apparaissant sur la droite.

Exemples

>>> une_gen = (None, "Moi", None)
>>> generation(une_gen, 1)
['Moi']
>>> deux_gen = ((None, "Papa", None), "Moi", (None, "Maman", None))
>>> generation(deux_gen, 2)
['Papa', 'Maman']
>>> trois_gen = ((None, "Papa", (None, "Mamy P.", None)), "Moi", ((None, "Papy M.", None), "Maman", None), )
>>> generation(trois_gen, 3)
['Mamy P.', 'Papy M.']

Version videVersion avec un parcours en largeurVersion avec un parcours en profondeur

Évaluations restantes : 10/10

.128013bqO,vi3o_x;lpwf( g]6-)2As»1+ûené4[Em5tCRPhkN:c.a=rySu/7d«050(0E0M0W0g0m0z0r0U0m0W0z0z0X010M0g0n010406050z0#0K0K0W0Y0Z040!0i0m0#0}0i0F0r020W0K0n0l0r0O0E170Y0c0#0E0z050$1416181a120n04051F1y1I0$1F120(0g0f0=0@0_0{0Q0g0s0Q0m1W0Q0M10050-0b0m0E1R0^0`011V1X1Z1X0M1)1+1%0M0Y1G0M0Q0=1d0z0n0W0F0{0x011-1T010p0/0E0F1l0E1%23252a1/2d1+2g0K2i040a0r0P0Y0i0n0i0z0g1g1i0+210Y0Y0E0U2D1y2k0F1G0$1 2P1|1~1}1(0(2m0{1Z0F2f2A1%1O1Q0?1.2Z0g2#0F0i2)1%0n2I1G2N2P2`13241i2+2b2:0Y170m100B2M2~112}2l301/3234100x38253a2N2Y013f0W35040h3j2O123m3d0{3p3r0H3u3l2~3n3A100L3D3w3F3y3o0i333q100u3K3b2 1S3e3P3g040%3D1J2^1y2)2S0(1~2X3N0U2;2s0*1P1G2@0E2_393%3;0+3|3c3X0{0R100+0p3%3x43010o100r493M4b0F0p100s2f0E0Y0W2L1z3}4a2,010 040q4g424v0F10180b2I4A3W4v4x0e3D4f4u31100F4I3n4x0w0T4N060r4!4O4h4v45040g484s3k4$4B4Q044F4H4-2O4/4J2b0i4d4*1x4^044`3n0R0U100S1h0E4T3N4x4X514Z4#5h3V54102I0M0#0Y4S51535c100I0t3K5i4P3e100z0W0s5b4b4L4N5j3N4D040n4o0z1h2#5F4K104M5r5J4i5B0W0(5I5z0{0i100X5$4%4;4?5a5f5y5-1/4)4+5,4:5A045q2`5s4b5)040X5+5W5%010K0g365S2b5d5x5h4#5X4(5l0,5o5~39605T040I6c5|5N0Y5P0F5R516i6d105w5;6h674)5m6m5`4{5|4m2#4p4r2|674x4z6A675L5C5E6W5?0{5H666$3o4R6L3n620v6-3N696b6#5{6%100w6;61100C6}4C4l4n6Q0g1h6t6`4y786+045C5#6^6M795V5 6B5|6n4.7l5(106:6)6_686a04377g4U6{3U0$3 3{3(7F0$3+1y0M3-7K2V2Q0W1*7H3+1E417h012I0K0j0p0W0R0E0j0Q0h101q1s1u1w0r5e2|1L3a1F0N0,0M1,5P1e2D0r1w0M0r4p0n0g2F0W0r0G0U0Y0g2I0r170g0;0F8b1w2B7|0r0b0E0W0#3;0#0n0r0(000G0-5N0;2F0)842J2y0g5D1,0A8x1,1Z0z7|0z0V1J7^040J1i0E0p0p0,0r0m3P8D1,0U0Q0W7/0r0W0n5N0m848b5o2B0p0e0r1h0r7#2C4f7E3n1;1Y1!1$7V5k046J5p714;6O4o4q767n2O7p4w106V6S6*6Y5D7b6(7k6X6,7t7W6/9f1/6?7x9v7B9A6.6 9D3z736P9j777z5t7a9S5Y7d5!9H047j6o9n5L9l529n9C9J6=7w7y9r7u4V3%7D3=040V0r0d0Y8}1+0;0f3q0E8`8G0F0f0i0Z0G7:240Y0=8-8/0p1h2K9k8a0-0F830+0;8P8R8}0P0Z1 8 0(0i92az0F0U8:0(1O2D6P0=0E0ma00v0U0g8T7@7U0yaf8.1v8:8=aL8^0U8`4+auaw0QayaAapaj4f1r9c8H864o8%002f0z1r7R8Na1a38`1ya;a6a8aa7:0(250;0#2#0r2:0#0faL1+8%8i8o2F5P160E0Vbr0r7`211m3P7|2rao0r5N1f0r0z000W0f0G2Iae3;0D7|0#0kaR1M3*0,0.0:04.

On peut résoudre cet exercice à l'aide d'un parcours en largeur de l'arbre.

Pour ce faire on crée une liste actuelle qui contient tous les nœuds non vides de la génération actuelle.

On met alors à jour cette liste en remontant à la génération précédente jusqu'à atteindre le rang de la génération souhaité.

Évaluations restantes : 10/10

.128013beqn,49vi[3mo5_tPhklpwNf(: cg.a=ry0S6]u/72)s18d050V0c0q0F0j0u0S0B0C0u0F0S0S0G010q0j0v010406050S0N0m0m0F0H0I040K0n0u0N0:0n0e050O0`0|0~100^0v04051g191j0O1g0^0V0j0i0(0*0,0.0s0j0D0s0u1x0s0q0?050Z0b0u0c1s0+0-011w1y1A1y0q1G1I1E0q0H1h0q0s0(130S0v0F0e0.0Q011K1u010y0#0c0e0F0m0c1E1%1)1.1M1;1I1@1_0?0a0B0r0H0n0v0n0S0j160e0B0X1#0H0H0c0C2e191|0e1h0O1Z2r1W1Y1X1F0V1~0.1A0e1?2b1E1p1r0)1L2B0j2D0e0n2H1E0v2k1h2p2r2V0_1(2f2J1/2O0H0}0u0?0B0T2o2Z0@2Y1}2#1M2%2)2+0Q2.1)2:2p2A012^0F2*040B0l2|2q0^2 2?0.32340B0g382~2Z303e2+0o3i3a3k3c310n2(332+0L3p2;2!1t2@3u2_350P3z3b3C3d3E3w350U3I3r3K3t3v3f0h3Q2=3S3m040T0J3X3B2K3T3F0T2-1a2/3q3Y3*3!0T2{3/2}1k2T192H2u0V1Y2z3s0C2P1`1h3 1i3}2X3`2q05450X2U3R3*0t0?0X0y3i3A300w2+4p3J3?0y0?0D1?0c0H0F2n4d4i3=1/0=040z4u4j2$0?0~0b2k4M4H1M4J0f3i0B4q3s0e0?184F4!3S4J0R0A4Y060B4;4Z4v4O040F2m0N0c0u1I4Y4*3*0n0?0G504@4V0?0k4T3)4^4Q4S4)570.4J0M3p4=4?4N1M4l040y3u565o3d0?0p5u4U0.0n4s042M5z5c2@0b0?4C0e4z5b304J4L5g5v010m0j0?3.2X5h014W5G3l4%5O3s4,4.4F4:5m4=514^2S2l0c0X0e0q0c5%3s5304554F5n5A5#595k5.5:5;5!5q5s0H5~3Z4P6g525D5F635=2@4P4{4}4 5S654J5-2V5/6a5m6o5w040S0F0D5*4+0?4X6n5!4$040v4B0S172D6I3*5$6M5T6O6F0V6j1/60622V645H6D0F5l6A6B6c0?0j4o6Y656!6G6%1M5C6@0S6~5B5D2O0q73010t0C0?0x175}6u6-66046x3:6;6;6C310?5@0C5_1?5|6V6(0?0E7w6p4_0v6Q0e6$7g5P0?5R5Z6Z0?6F6H7H5+0?0R6:7m6,305q6^786|7G6+7o705E726`7h7)76787a7c7e7A5i0?7k2}6z7V6b7M6P2k7s5`7v7Q3S607z853?4P7D1?7$2/7o5Q7@7p6E0F8e3{5!4,7U5:7o6O4`0q4|4~7f7%5!6)7!7q817t5{8y7l7~655q2k8v0H4(8z5T4J5a895d8i8S8i5V5X8W0?688Q8K0?6e8C4_787)6m8(7h8t6r8x8#048%2/4;7o0C0T0?030B170B2D0B2k0e0i0n0j1J0d4|0B1I0%2O0m7+6y194g0c2r5@2r492s41192v9w0F1H9p3~1q2:0O0X0Z0#0S04.

On peut résoudre cet exercice à l'aide d'un parcours en profondeur de l'arbre.

Pour ce faire on utilise une structure de pile dans laquelle on ajoute initialement la racine de l'arbre ainsi que sa hauteur 1.

Attention toutefois à l'ordre dans lequel on empile les différents nœuds : une pile répond au modèle « Dernier Entré, Premier Sorti » !

Évaluations restantes : 10/10

.128013ben,49vi[+3mo5t;PhklpwNf(: cg.a=ry0S6]u/72)s18d050V0c0p0F0i0u0S0B0C0u0F0S0S0G010p0i0v010406050S0N0m0m0F0H0I040K0n0u0N0:0n0d050O0`0|0~100^0v04051g191j0O1g0^0V0i0h0(0*0,0.0s0i0D0s0u1x0s0p0?050Z0b0u0c1s0+0-011w1y1A1y0p1G1I1E0p0H1h0p0s0(130S0v0F0d0.0Q011K1u010y0#0c0d0F0m0c1E1%1)1.1M1;1I1@1_0?0a0B0r0H0n0v0n0S0i160d0B0X1#0H0H0c0C2e191|0d1h0O1Z2r1W1Y1X1F0V1~0.1A0d1?2b1E1p1r0)1L2B0i2D0d0n2H1E0v2k1h2p2r2V0_1(2f2J1/2O0H0}0u0?0B0T2o2Z0@2Y1}2#1M2%2)2+0Q2.1)2:2p2A012^0F2*040B0l2|2q0^2 2?0.32340B0f382~2Z303e2+0o3i3a3k3c310n2(332+0L3p2;2!1t2@3u2_350P3z3b3C3d3E3w350U3I3r3K3t3v3f0g3Q2=3S3m040T0J3X3B2K3T3F0T2-1a2/3q3Y3*3!0T2{3/2}3;3)2$3M340T373`393A3l3 0?0T3h432r2S0c2r2H2u0V1Y2z3s0C2P1`1h4g1i2T3A2W2/054m0X2U3R3*0t0?0X0y3i453s0w2+4G3J3?0y0?0D1?0c0H0F2n4b4H3S0=040z4L4A2$0?0~0b2k4$3=1/4Z0e3i0B4X3?0?184W4M4/0?0R0A4=060B534?4|2@0?0v1=4=4@1/0n0?0G5b560.4Z0j4#4{4%57044*4,5n4.1M4:5h5o0.0m0i484-3}5v4~0M3p54555y310?2k0`0u0Z0p5x5u0.5e045g4b5K5U015k5H4b52545c1M4C040w1w1I5T5E3d0b0?215D304Z5m2X5i5M04595=5t5@5$4~5?305W020D0p0q6a3s5A0?3%665}0?505)5J5J5,3d4)5|3s5w5Z6t620i6h3S5W5Y2V5!670d585a6m3s5W0E6w3Z58296R3*5~0R5I6r536A6K040S0F0D6V4}044;6z616%0v4S0S172D6,5F6.6D4^6(0F0V6~5d5f735p0F6Z6!6A5.0i4F6:5L6%6C7f5#6F6G2/6I3l4_6{5j6o796!5+6;5N0c5P5R7r016P7C6%0F0v6?0d726N4Y0?5 4v7x636@6_0c7C4Z6Y6q7v7b0?0c0$7V7M6W7t7Z7v7w5L7c7e6H6$0?6)7L7?610n4J040i0S765V7~2O5S7j670t0C0?0x177)605L4Z6p2V5*7.7a7R648e7Q5L7E7*4(5q7I1?7`8q5#5~7P2}7@708y8D616y7{7g0?7i8K7k0?0k82016j3#7W4~7Y8j8l7/5#7;8S6%6)6+876b7~808S7}4_0n868O888a048c6`8t6|8i3:8!8m8L636M8f8P046Q8~6u8v7J8G2q6A8B7F7^6*8W6}8,3s7h8:8Q8S8U3.97677X8Y918#887y0p0N0H4`8^7p045O0N5Q4U3z0O4x4e1k4s0O4q2s4i192v9Z0F1H9S9V1q2:9V0Y0!0$04.