Arbres enracinés, 😀🏷️🧓🧮 Intro 🎁🥚💥

Une section dédiée aux arbres enracinés.

• Il n'y a pas d'arbre vide dans cette section.
• Le point commun à toutes les variétés présentées ici, c'est qu'il y a au moins un nœud par arbre et qu'un nœud est désigné racine de l'arbre. Ensuite, il y a des différences...
• Les arbres peuvent avoir des arités variables (un nombre d'enfants par nœud).
• Les arbres peuvent être étiquetés ou non.
• Les arbres peuvent être ordonnés ou non.
• ...

Les arbres binaires sont bien enracinés... sauf l'arbre binaire vide... Ils sont étudiés à part ; La modélisation est assez différente, l'arbre vide est omniprésent.

Certains exercices de cette section comportent de nombreuses difficultés.

Nous allons essayer d'être très progressif. Il y a des exercices :

• 😀 : sur les arbres non étiquetés.
• 🏷️ : sur les arbres étiquetés.
• 🧓 : sur les arbres non ordonnés.
• 🧮 : sur des arbres syntaxiques d'expression arithmétique simple.
• Avec plusieurs niveaux de difficulté :
  • Application directe du cours et des méthodes.
  • 💥 Nécessite une autre technique ou structure, comme un dictionnaire...
  • 💥💥 Nécessite des techniques variées, comme des constructions de fonctions auxiliaires...
  • 💥💥💥 Nécessite de réfléchir plus sérieusement...
• Une correction détaillée écrite avec soin est proposée ; ne pas hésiter pas à l'étudier !
• 🎁 : En cas de succès à l'exercice, un complément de cours est proposé ; souvent pour donner une variante avec un style fonctionnel.
• 🥚 : En cas de succès à l'exercice, un exercice caché sera débloqué ; dans le prolongement du premier. Ou bien une surprise !

Mutable ou immuable

Pour cette section (Arbre), on fera souvent le choix d'une structure mutable (avec liste et non tuple) pour une unique raison :

• il est plus simple de construire le résultat avec une liste des enfants qui s'agrandit.

Mais tous les arbres en entrée ou en sortie sont à considérer comme des objets immuables dans cette section.

On s'évite la peine de devoir écrire des return (racine, tuple(enfants)).

Le choix du tuple était parfaitement possible également. On l'utilisera dans certains exercices.