Aller au contenu

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 filiation 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

###
bksl-nl# 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-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-nlNone

A

Z

Retour en haut de la page