Cet exercice demande d'écrire les fonctions calculant la taille et hauteur d'un arbre.
Il fait partie d'une série dans laquelle on utilise différentes représentations :
Dans tout le sujet, on considère des arbres enracinés. On rappelle que les arbres binaires ne sont pas des arbres enracinés.
On rappelle la définition d'un arbre enraciné : il s'agit d'une racine qui possède \(0\), \(1\) ou plusieurs sous-arbres qui sont eux-mêmes des arbres enracinés. Les arbres considérés dans cet exercice ne possèdent pas d'étiquettes.
Un arbre enraciné qui ne possède pas de sous-arbre est appelé feuille.
On représente un arbre enraciné par une liste Python contenant ses sous-arbres. Une feuille est donc représentée par [].
L'arbre représenté par [[], [], [[]]] a quant à lui une racine et 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.
Cet arbre se dessine ainsi :
graph TD
R{ } --> N1{ }
R --> N2{ }
R --> N3{ }
N3 --> N4{ }
Dans cet exercice, la définition de la hauteur d'un arbre est le nombre maximal de filiations pour rejoindre la racine à une feuille. Un arbre réduit à sa racine a donc une hauteur égale à \(0\).
1. Taille de l'arbre
Écrire la fonction taille qui prend en paramètre une liste représentant un arbre et renvoie sa taille.
Exemples
>>> 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
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)