Aller au contenu

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)]
###
# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[[], []], [], []]) == [bksl-nl (1, 1),bksl-nl (1, 1),bksl-nl (1, -1),bksl-nl (2, 0),bksl-nl (1, -1),bksl-nl]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], [[], []], []]) == [bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, 1),bksl-nl (1, -1),bksl-nl (1, -1),bksl-nl]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], [[], [[], []], [], [], []], []]) == [bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, 1),bksl-nl (1, -1),bksl-nl (2, 0),bksl-nl (2, 0),bksl-nl (1, -1),bksl-nl (1, -1),bksl-nl]bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([]) == []bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], []]) == [(1, 1), (1, -1)]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], [], []]) == [(1, 1), (2, 0), (1, -1)]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[[], [], []], [[], [], []]]) == [bksl-nl (1, 1),bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, -1),bksl-nl (1, -1),bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, -1),bksl-nl]bksl-nlbksl-nl ∞/∞

def arbrepy-undverspy-undchemin(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[[], []], [], []]) == [bksl-nl (1, 1),bksl-nl (1, 1),bksl-nl (1, -1),bksl-nl (2, 0),bksl-nl (1, -1),bksl-nl]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], [[], []], []]) == [bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, 1),bksl-nl (1, -1),bksl-nl (1, -1),bksl-nl]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], [[], [[], []], [], [], []], []]) == [bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, 1),bksl-nl (2, 0),bksl-nl (1, 1),bksl-nl (1, -1),bksl-nl (2, 0),bksl-nl (2, 0),bksl-nl (1, -1),bksl-nl (1, -1),bksl-nl]bksl-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-nlbksl-nl chemin = []bksl-nl parcourspy-undprefixe(arbre, chemin)bksl-nl return cheminbksl-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