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
for sous_arbre in arbre:
    action(sous_arbre)

Ou alors des listes en compréhension

Python
[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 
>>> hauteur([])
0
>>> hauteur([[], [], [[]]])
2
>>> taille([])
1
>>> taille([[], [], [[]]])
5
###(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 : 5/5
.128013kp+n7=(32vx[fah1:-tS6dm0]P)cu8_swl4obiery5g9/ 050w0N0t0o0M0I0G0U0C0I0o0G0G0g010t0M0c010406050G0D0x0x0o0O0P040u0K0I0D0/0K0e050T0_0{0}0 0@0c04051f181i0T1f0@0w0M0k0%0)0+0-0)0e0R0D0o0R0N0s0c0P0t0p160U0p0M0R0p0I1K0p0t0=050Y0L0I0N1r0*0,011J1L1N1L0t1T1V1R0t0O1g1F0%120G0c0o0e0-0j011X1t010n0!0N0e0o0x0N1R1?1^1}1Z201V23250=0a0U0A0O0K0c0K0G0M150e0U0W1;0O0O0N0C2q18280e1g0T1F2D1-1/1.1S0w2a1u0M0e222n1R1o1q0(1Y2N2P0e0K2T1R0c2w1g2B2D2*0^1@2r2V1~2Z0O0|0I1R0o1I2w0n0-030F0F0C2!0N1N2Y0K0s0i0s0q0=0U0q180o2+2.0?2-292:1Z2=2@2_2{0N2}012 3133352Q380s1{040U0j3f3h1^3j2B2M013o0o2^1g2`0p2|2~30320W3y2Z3A0i3c0i3G2A3i0@3K3m0-3N3P053R3T3u3V3x2O3z390J3c0J3(193*3k2/1s3n0K2?3O3q3S3s3U3w3X3`3Z390Q3c0Q402*3+2.3L3/4a3?3v3W344g37390v3c0v4m423,453.473p3Q3r3t4u3_363A0f3c0f4D3I4o3l4G3M4I494K4b4M3^4f4P390E3c0E4U2C4W442W4Z483:3=4c3@4e4w4+0s0S3c0S4:3J4p3-4^4J3;4L4d4v3Y4y3a0y0=0q0y554=4q4!4`5c4}5e4x3A0q3b045w5m435o4_4s4|4N4*3{3a3C0q3F0T3g3)3I1j2(182T2G0w1/2L584v2S1p1g2%0N2)3i5P2C054v5*290M0w0-302B5v3q5=5@4~5f5`0U2e0N5}5t505x3(4F4@0b0=0W0n5,3D5B580e0n0=0p0o140N0D0O6f6h4Y0;040h6s692;0=0}0L2w6y576u0=0B0r6f0@415Q3K5|015^2.3A3C5b6Q4)4 5I1{6124636R5~5u396V5N3D0U6:6t6a0=0M6e6N2C0U6=6A046C6E6`6g6z1Z0K0=0g0g6f6|740-6v0m0z6K726M2,6P5?6)5_393#4K6X6*503#6$25644O5I7q3G6:7D7D6}1Z6b042w0t6q17727b6G4@0x0M0=5l7i6F5;7m6S1^3A3}7r7Z7t5I3}7w6(6Y5 3|1R6.7E7G0-7I340G0N7X4?1~6v7h4n7~0U7s7o0s4j7(7y5H4h881|628b6Z8d897C7E7F7c017I7K7M7a7^017S5j8t8o76040d8y7Q2;0L0=0|0l84586v6x728u0e6l6n0t6p6r8O8o8M8K4Y8Q040G0K0D0G0F707}8W8E1Z6v0B8D4X6?040n478?7 3n0=8%8)8+0O6D8-2*7P8@1~0K0H6@7N968P6B93717k8/7d6I6L84866T4z5{7)655I4A7-8h7:0s4A2D3g7j5+7l5}874R8a6)9u8d4R9x9L7z9N7=9D9o7)874-9K7/6+0s4-9P9!509Y689k8p6c3s8|4q6k040Y0!1V8Z4@8Y8.988~6 9h959F9-8;82429~2r9p7#39529Z7*8d529(ag5gae8l6;8o7I6^9;6i9g94as4Y8A78aw9|0=7fa74V9V9H9q5h9s9y9#5k8f6%aL665i9C6/8m978}7_0=8r0O9d3iaW3L8w5y9na9859WaI5waK9Q8c5ga;aj9Ma^677?8n9-7`0#a36Oa50=aE4;aG7na:6V2`7sa{5v6#8ga?8ia^6-3gaVaob0aZ0X8s7O8ua*3ebu8z0=8Cby9-0e8G8$0`9{800=8N9j9 3.0=9^0I9`a-8LbKbIa0908*8,bW9l048=bCbN9.8_8{b)aX3M8 8(bZa2aA999b042Ob^a0b!bT6Hb%a,2,0T5/5R5)5T5$180t5Wcb2J2E0o1Uc80T5U6M0WbQ0G04.