Correspondance de Schröder⚓︎

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

🐍 Console Python

>>> arbre_vers_chemin([[[], []], [], []])
[(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]

donne

🐍 Console Python

>>> arbre_vers_chemin([[], [[], []], []])
[(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]

donne

🐍 Console Python

>>> arbre_vers_chemin([[], [[], [[], []], [], [], []], []])
[(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]

###

∞/∞

def arbrepy-undverspy-undchemin(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin(bksl-nl [[[], []], [], []]bksl-nl) == [(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin(bksl-nl [[], [[], []], []]bksl-nl) == [(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin(bksl-nl [[], [[], [[], []], [], [], []], []]bksl-nl) == [(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]bksl-nlbksl-nlbksl-nlbksl-nldef arbrepy-undverspy-undchemin(arbre):bksl-nl def parcourspy-undprefixe(arbre, chemin):bksl-nl ipy-undpremier = 0bksl-nl ipy-unddernier = len(arbre) - 1bksl-nl for i, souspy-undarbre in enumerate(arbre):bksl-nl if i == ipy-undpremier:bksl-nl chemin.append((1, 1))bksl-nl elif i == ipy-unddernier:bksl-nl chemin.append((1, -1))bksl-nl else:bksl-nl chemin.append((2, 0))bksl-nl parcourspy-undprefixe(souspy-undarbre, chemin)bksl-nl bksl-nl chemin = []bksl-nl parcourspy-undprefixe(arbre, chemin)bksl-nl return cheminbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin(bksl-nl [[[], []], [], []]bksl-nl) == [(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin(bksl-nl [[], [[], []], []]bksl-nl) == [(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin(bksl-nl [[], [[], [[], []], [], [], []], []]bksl-nl) == [(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]bksl-nlbksl-nlbksl-nlbksl-nl

A

Z

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

🐍 Script Python

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