Correspondance de Schröder
😀 On considère ici des arbres non étiquetés et ordonnés.
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 :
- Une feuille ne possède aucun sous-arbre ; (classique)
- Sinon, un nœud 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.
Exercice
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
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.
Guide
def arbre_vers_chemin(arbre):
def parcours_préfixe(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_préfixe(..., chemin)
chemin = []
parcours_préfixe(arbre, chemin)
return chemin
🥚 easter egg
Si vous résolvez cet exercice, vous aurez accès à un exercice caché : reconstruire un arbre avec le procédé inverse ; c'est bien plus délicat à implémenter.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)