Correspondance Schröder (1)
Généralités
On rappelle qu'un arbre est dit :
- enraciné : s'il possède au moins un nœud ; la racine
- sans étiquette : les nœuds ne portent pas ici d'identifiant ni de valeurs
- ordonné : l'ordre de ses sous-arbres compte
Dans ce cas, un arbre peut être modélisé avec une liste Python :
- Une feuille (un nœud externe) sera représentée par une liste vide
[]; la liste de ses sous-arbres est vide. - Un nœud interne sera représenté par la liste de ses sous-arbres donnés dans l'ordre.
- Un arbre sera donné par la représentation de sa racine.
Arbres de Schröder
Un arbre de Schröder est un arbre enraciné ordonné sans étiquette, ayant la propriété suivante :
un nœud ne possède jamais un unique sous-arbre ; soit aucun, soit au moins deux sous-arbres.
Ainsi, pour un arbre de Schröder :
- un nœud externe (une feuille) ne possède aucun sous-arbre ; (classique)
- un nœud interne possède au moins deux sous-arbres ; (particularité)
Exemples
est représenté en interne avec [[[], []], [], []]
est représenté en interne interne avec [[], [[], []], []]
Les deux arbres ci-dessus sont différents, d'où la qualification ordonné.
est représenté en interne avec [[], [[], [[], []], [], [], []], []]
Correspondance de Schröder
Pour un arbre de Schröder, on effectue un parcours préfixe et pour chaque nœud rencontré hormis la racine, on ajoute une étape à un chemin sur une grille qui part de l'origine :
- ↗, codée \((1, 1)\), si le nœud est le plus à gauche (parmi ceux de son ancêtre direct)
- ↘, codée \((1, -1)\), si le nœud est le plus à droite (parmi ceux de son ancêtre direct)
- →→, codée \((2, 0)\), sinon.
L'objectif de l'exercice est de construire une fonction telle que arbre_vers_chemin(arbre) renvoie la description du chemin de l'arbre de Schröder passé en paramètre.
Exemples
donne 
>>> arbre_vers_chemin([[[], []], [], []])
[(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]
donne 
>>> arbre_vers_chemin([[], [[], []], []])
[(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]
donne 
>>> arbre_vers_chemin([[], [[], [[], []], [], [], []], []])
[(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]
Indice 1
En réalisant le parcours préfixe, pour chaque nœud, on veillera à identifier le premier et le dernier sous-arbre. Pour cela, on pourra obtenir d'abord le nombre de sous-arbres, puis en itérant, savoir s'il s'agit du premier, du dernier ou un autre cas.
Indice 2
On pourra compléter le code suivant
def arbre_vers_chemin(arbre):
def parcours_prefixe(arbre, chemin):
i_premier = 0
i_dernier = ...
for i, sous_arbre in enumerate(arbre):
if i == i_premier:
chemin.append(...)
elif i == i_dernier:
...
else:
...
parcours_prefixe(..., chemin)
chemin = []
parcours_prefixe(arbre, chemin)
return chemin
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)