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
.128013/p:i+vl4P)h=obk56uancgrtS_xef12w y]0m[-s789(d3050T0C0y0t0e0h0O0H0v0h0t0O0O0m010y0e0c010406050O0s0L0L0t0x0I040z0n0h0s0/0n0u050b0_0{0}0 0@0c04051f181i0b1f0@0T0e0g0%0)0+0-0)0u0w0s0t0w0C0N0c0I0y0l160H0l0e0w0l0h1K0l0y0=050Y0o0h0C1r0*0,011J1L1N1L0y1T1V1R0y0x1g1F0%120O0c0t0u0-0F011X1t010D0!0C0u0t0L0C1R1?1^1}1Z201V23250=0a0H0j0x0n0c0n0O0e150u0H0W1;0x0x0C0v2q18280u1g0b1F2D1-1/1.1S0T2a1u0e0u222n1R1o1q0(1Y2N2P0u0n2T1R0c2w1g2B2D2*0^1@2r2V1~2Z0x0|0h1R0t1I2w0D0-030A0A0v2!0C1N2Y0n0N0U0N0E0=0H0E180t2+2.0?2-292:1Z2=2@2_2{0C2}012 3133352Q380N1{040H0F3f3h1^3j2B2M013o0t2^1g2`0l2|2~30320W3y2Z3A0U3c0U3G2A3i0@3K3m0-3N3P053R3T3u3V3x2O3z390i3c0i3(193*3k2/1s3n0n2?3O3q3S3s3U3w3X3`3Z390q3c0q402*3+2.3L3/4a3?3v3W344g37390r3c0r4m423,453.473p3Q3r3t4u3_363A0P3c0P4D3I4o3l4G3M4I494K4b4M3^4f4P390Q3c0Q4U2C4W442W4Z483:3=4c3@4e4w4+0N0R3c0R4:3J4p3-4^4J3;4L4d4v3Y4y3a0K0=0E0K554=4q4!4`5c4}5e4x3A0E3b045w5m435o4_4s4|4N4*3{3a3C0E3F0b3g3)3I1j2(182T2G0T1/2L584v2S1p1g2%0C2)3i5P2C054v5*290e0T0-302B5v3q5=5@4~5f5`0H2e0C5}5t505x3(4F4@0p0=0W0D5,5:4?1~0G3c6f5B580u0D0=0l0t140C0s0x6l691~0;040S6x574Y0u0=0}0o2w6D4X4@6A0k0d6f0@415Q3K5|015^2.3A3C5b6W4)4 5I1{6124636X5~5u396#5N3D0H6_6m4Y6b040e6e6T2C0H6{4@6G046I6K713D741~0n0=0m0m6f736y1Z6A0M0J6Q7a6S2,6V5?6/5_393#4K6%6:503#6,25644O5I7y3G6_7L7L7c1Z6}2w0y6v177a7j6E4@0L0e0=5l7q6L2r7A7w0N3}7z7u6(5 3|1|627G5H4h7,1R6@7M7O0-6}340O0C7(3L6A7p4n857*6Z4i5{7/7B5I4j7E6.7:6;0N4j2D3g7M7~7k800=7R7T7i7 017Z5j8y8t017e040f8D7X2;0o0=0|0B85586A6C7a8z766r6t6v8Q4Y8S8!750=0O0n0s0O0A78848U8E6O8J6M1~6}0D478@6h3n8)8+8-8/8}3L0n6j6~7U2*7W8^8 770x6J8:7s8K7l0=0k6R8a8f7+4A7.7^6)7`4A8j9t7;0N9r3G7r5+7t5}7+4R9s6/655I4R9x9K7H7`9I9C9o9G8c0N4-9J8l504-9O9!5I9Y689j8u046d8%6i6k8;9,3M6p040Y0!1V9:9k6B9~3.6H9f799i9c0-6O88429?5;9p9W529Z8g7`529%ai5gag7K7N8E6}6 946na39gau4Y8G7gay6N0=7naa4V9U7v9W5k8e9y8maLal9L7`aL8p6^8r9b8~9-8w0x993iaX3L8B5y9nac7)ae1^5v672`7AaR5g5w7?6-aN66677}aq9@810#9h9E9@87a,a6a.9Va:395LaM9P7_a_6+7@bh9ubj7|8qaWa(587Q0X8x7V8za*3ebx8E8G8IbB9@0u8M041aa1018$a-4q0=9{0h9}bO8R0=8TbabPbJ918.a4b56Ub79laC8_0=8{6wbFa73M908,b$axb;aY8F972Ob,9d93bU8#b+7%8U0b5/5R5)5T5$180y5Wce2J2E0t1Ucb0b5U6S0WbR0O04.