Skip to content

2 4 3 structures

Structures de données récursives

Le récursivité est intensivement utilisée dans des structures de données telles que les graphes ou les arbres informatiques.

Graphe

Un graphe G = (V,E) est une structure de données, formée d'un ensemble V d'éléments et d'un ensemble de paires (ou de couples) établissant les liens entre ces éléments.

Si E est un ensemble de paires, on dit que le graphe est non orienté, s'il s'agit de couples, le graphe est orienté.

Le graphique suivant décrit un graphe orienté donnant un ensemble V de personnes (V= {Jean, Germaine, Catherine, Luc, Bernadette, Jules, Michel} avec la relation E (connaît).

E = { Jean -> Germaine ; Germaine -> Catherine ; Catherine -> Jean ; Bernadette -> Luc ; Bernadette -> Michel ; Michel -> Luc ; Bernadette -> Jules ; Jules -> Bernadette }

Une façon simple d'implémenter un tel graphe en python est avec un dictionnaire dont les éléments sont les clés, et la liste de leurs connaissances, leur valeur. Dans l'exemple plus haut on aurait :

 graphe = { "Jean"       : ["Germaine"] ,
            "Germaine"   : ["Catherine"],
            "Catherine"  : ["Jean"] ,
            "Luc"        : [],
            "Michel"     : ["Luc"],
            "Bernadette" : ["Luc", "Michel", "Jules"],
            "Jules"      : ["Bernadette"] }

Arbre binaire

L'exemple de l'expression à évaluer, vu plus haut, est en fait une implémentation python, avec des listes, de la notion d'arbre binaire.

Un arbre binaire est une structure de données soit vide soit formée d'un noeud et de deux sous-arbres binaires, appelés respectivement fils gauche et un fils droit.

Chaque noeud contient une information appelée contenu.

Ainsi l'expression `3 + 4 * 5`` est vu comme l'arbre binaire illustré par la figure suivante :

où les noeuds vides ne sont pas représentés.

Notre implémentation python donnait : exp = [3,'+',[4,'*',5]]

La récursivité ainsi que de nombreux algorithmes sur les arbres et les graphes seront vus plus en détails dans la partie algorithmique.