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.
Un arbre enraciné qui ne possède pas de sous-arbre est appelé feuille.
On représente un arbre enraciné par un tuple contenant deux éléments : la valeur portée par la racine et la liste des sous-arbres. Une feuille est donc représentée par (x,[]) où x est une valeur quelconque.
L'arbre représenté par ("a",[("b",[]),("c",[]),("d",[("e",[])])]) a quant à lui une racine portant la valeur "a" 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{a} --> N1{b}
R --> N2{c}
R --> N3{d}
N3 --> N4{e}
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.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)