Hauteur et taille d'un arbre⚓︎

Dans tout le sujet, ici, arbre désigne un arbre enraciné.

On rappelle que les arbres binaires ne sont pas des arbres enracinés.

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

🐍 Script Python

for sous_arbre in arbre:
    action(sous_arbre)

Ou alors des listes en compréhension

🐍 Script 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

🐍 Console Python

>>> hauteur([])
0
>>> hauteur([[], [], [[]]])
2

🐍 Console Python

>>> taille([])
1
>>> taille([[], [], [[]]])
5

###

# testsbksl-nlbksl-nlassert hauteur([]) == 0bksl-nlassert hauteur([[], [], [[]]]) == 2bksl-nlbksl-nlassert taille([]) == 1bksl-nlassert taille([[], [], [[]]]) == 5bksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert hauteur([[]]) == 1bksl-nlassert hauteur([[], []]) == 1bksl-nlassert hauteur([[], [], []]) == 1bksl-nlbksl-nlassert hauteur([[], [[]], [[]], [], []]) == 2bksl-nlassert hauteur([[], [[]], []]) == 2bksl-nlassert hauteur([[[]], []]) == 2bksl-nlassert hauteur([[], [[]]]) == 2bksl-nlassert hauteur([[[]]]) == 2bksl-nlbksl-nlbksl-nlbranche = [[], [[[], []]]]bksl-nlarbre = [[branche[:]], [[branche[:]], [[branche[:]]]]]bksl-nlassert hauteur(arbre) == 7bksl-nlbksl-nlbksl-nlassert taille([[]]) == 2bksl-nlassert taille([[], []]) == 3bksl-nlassert taille([[], [], []]) == 4bksl-nlbksl-nlassert taille([[], [[]], [[]], [], []]) == 8bksl-nlassert taille([[], [[]], []]) == 5bksl-nlassert taille([[[]], []]) == 4bksl-nlassert taille([[], [[]]]) == 4bksl-nlassert taille([[[]]]) == 3bksl-nlbksl-nl 5/5

def hauteur(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nldef taille(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert hauteur([]) == 0bksl-nlassert hauteur([[], [], [[]]]) == 2bksl-nlbksl-nlassert taille([]) == 1bksl-nlassert taille([[], [], [[]]]) == 5bksl-nlbksl-nldef hauteur(arbre):bksl-nl if arbre == []:bksl-nl return 0bksl-nl else:bksl-nl return 1 + max(hauteur(souspy-undarbre) for souspy-undarbre in arbre)bksl-nlbksl-nlbksl-nldef taille(arbre):bksl-nl if arbre == []:bksl-nl return 1bksl-nl else:bksl-nl return 1 + sum(taille(souspy-undarbre) for souspy-undarbre in arbre)bksl-nlbksl-nl

A

Z