Hauteur et taille d'un arbre

On rappelle la définition d'un arbre : il s'agit d'une racine qui possède (souvent une étiquette et) \(0\), \(1\) ou plusieurs sous-arbres qui sont des arbres. Un arbre enraciné qui ne possède pas de sous-arbre est appelé feuille.

On modélise ici des arbres enracinés sans étiquette par des listes Python : la liste des sous-arbres.

Utilisation

Cette modélisation permet d'écrire des constructions du genre

Python
1
2
for sous_arbre in arbre:
    action(sous_arbre)

Ou alors des listes en compréhension

Python
1
[action(sous_arbre) for sous_arbre in arbre]

Dans cet exercice, la définition de la hauteur d'un arbre est le nombre maximal de filiations pour rejoindre la racine à une feuille.

  • Une feuille est donc modĂ©lisĂ©e par [] ; sa hauteur est zĂ©ro.

  • L'arbre reprĂ©sentĂ© par [[], [], [[]]]

    • dĂ©signe une racine qui possède trois sous-arbres :
      • le premier est une feuille,
      • le deuxième est une feuille,
      • le troisième est un arbre qui a un sous-arbre qui est une feuille.
    • Sa hauteur est \(2\).
    • Il se dessine ainsi : 
graph TD
    R{ } --> N1{ }
    R    --> N2{ }
    R    --> N3{ }
    N3   --> N4{ }

Écrire deux fonctions telles que :

  • hauteur(arbre) renvoie la hauteur de l'arbre enracinĂ© donnĂ© en paramètre.
  • taille(arbre) renvoie la taille de l'arbre enracinĂ© donnĂ© en paramètre.

Dans cet exercice, on pourra utiliser les fonctions prédéfinies max et sum.

Exemples 
1
2
3
4
5
6
7
8
>>> hauteur([])
0
>>> hauteur([[], [], [[]]])
2
>>> taille([])
1
>>> taille([[], [], [[]]])
5
###(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 : 5/5
.128013oPf 8lkg5:+bry2a1h3tvw=u6e[(Sn9]x_s-c)7im/4p0d050U0A0u0q0O0g0J0e0L0g0q0J0J0x010u0O0S010406050J0y0P0P0q0n0o040D0b0g0y0/0b0E050Q0_0{0}0 0@0S04051f181i0Q1f0@0U0O0v0%0)0+0-0)0E0i0y0q0i0A0K0S0o0u0s160e0s0O0i0s0g1K0s0u0=050Y0m0g0A1r0*0,011J1L1N1L0u1T1V1R0u0n1g1F0%120J0S0q0E0-0p011X1t010d0!0A0E0q0P0A1R1?1^1}1Z201V23250=0a0e0c0n0b0S0b0J0O150E0e0W1;0n0n0A0L2q18280E1g0Q1F2D1-1/1.1S0U2a1u0O0E222n1R1o1q0(1Y2N2P0E0b2T1R0S2w1g2B2D2*0^1@2r2V1~2Z0n0|0g1R0q1I2w0d0-030I0I0L2!0A1N2Y0b0K0t0K0r0=0e0r180q2+2.0?2-292:1Z2=2@2_2{0A2}012 3133352Q380K1{040e0p3f3h1^3j2B2M013o0q2^1g2`0s2|2~30320W3y2Z3A0t3c0t3G2A3i0@3K3m0-3N3P053R3T3u3V3x2O3z390R3c0R3(193*3k2/1s3n0b2?3O3q3S3s3U3w3X3`3Z390j3c0j402*3+2.3L3/4a3?3v3W344g37390z3c0z4m423,453.473p3Q3r3t4u3_363A0N3c0N4D3I4o3l4G3M4I494K4b4M3^4f4P390f3c0f4U2C4W442W4Z483:3=4c3@4e4w4+0K0F3c0F4:3J4p3-4^4J3;4L4d4v3Y4y3a0T0=0r0T554=4q4!4`5c4}5e4x3A0r3b045w5m435o4_4s4|4N4*3{3a3C0r3F0Q3g3)3I1j2(182T2G0U1/2L584v2S1p1g2%0A2)3i5P2C054v5*290O0U0-302B5v3q5=5@4~5f5`0e2e0A5}5t505x3(4F4@0h0=0W0d5,5:4?1~0w3c6f5B580E0d0=0s0q140A0y0n6l691~0;040C6x574Y0E0=0}0m2w6D4X4@6A0M0k6f0@415Q3K5|015^2.3A3C5b6W4)4 5I1{6124636X5~5u396#5N3D0e6_6m4Y6b040O6e6T2C0e6{4@6G046I6K713D741~0b0=0x0x6f736y1Z6A0B0G6Q7a6S2,6V5?6/5_393#4K6%6:503#6,25644O5I7y3G6_7L7L7c1Z6}2w0u6v177a7j6E4@0P0O0=5l7q6L2r7A7w0K3}7z7u6(5 3|1|627G5H4h7,1R6@7M7O0-6}340J0A7(3L6A7p4n857*6Z4i5{7/7B5I4j7E6.7:6;0K4j2D3g7M7~7k800=7R7T7i7 017Z5j8y8t017e040l8D7X2;0m0=0|0H85586A6C7a8z766r6t6v8Q4Y8S8!750=0J0b0y0J0I78848U8E6O8J6M1~6}0d478@6h3n8)8+8-8/8}3L0b6j6~7U2*7W8^8 770n6J8:7s8K7l0=0M6R8a8f7+4A7.7^6)7`4A8j9t7;0K9r3G7r5+7t5}7+4R9s6/655I4R9x9K7H7`9I9C9o9G8c0K4-9J8l504-9O9!5I9Y689j8u046d8%6i6k8;9,3M6p040Y0!1V9:9k6B9~3.6H9f799i9c0-6O88429?5;9p9W529Z8g7`529%ai5gag7K7N8E6}6 946na39gau4Y8G7gay6N0=7naa4V9U7v9W5k8e9y8maLal9L7`aL8p6^8r9b8~9-8w0n993iaX3L8B5y9nac7)ae1^5v672`7AaR5g5w7?6-aN66677}aq9@810#9h9E9@87a,a6a.9Va:395LaM9P7_a_6+7@bh9ubj7|8qaWa(587Q0X8x7V8za*3ebx8E8G8IbB9@0E8M041aa1018$a-4q0=9{0g9}bO8R0=8TbabPbJ918.a4b56Ub79laC8_0=8{6wbFa73M908,b$axb;aY8F972Ob,9d93bU8#b+7%8U0Q5/5R5)5T5$180u5Wce2J2E0q1Ucb0Q5U6S0WbR0J04.