Comprendre les arbres, la récursivité et leur stockage

Cette fonction parcourt l’arbre en profondeur (parcours DFS) :

def parcourir(noeud):
    print(noeud.value)
    for enfant in noeud.children:
        parcourir(enfant)

Le principe est simple :

• On traite le nœud courant (affichage de sa valeur)
• On appelle récursivement la fonction sur chacun de ses enfants

Chaque appel applique exactement le même traitement, quelle que soit la profondeur.

Exemple d’arbre :

A
├── B
│   └── D
└── C

Ordre de parcours :

A
B
D
C

Le parcours suit une logique « profondeur d’abord » :

• On visite d’abord le nœud racine (A)
• Puis on descend dans le premier sous-arbre (B)
• On continue jusqu’à atteindre une feuille (D)
• On remonte ensuite pour explorer les autres branches (C)

Ce comportement est directement lié à la récursivité : chaque appel de fonction suspend son exécution le temps de traiter un sous-arbre, puis reprend là où il s’était arrêté.

Ce type de parcours est appelé DFS (Depth-First Search), ou parcours en profondeur.

La simplicité de cette implémentation masque un mécanisme puissant : la pile d’appels gère automatiquement le retour en arrière dans l’arbre.

Lorsqu’une fonction récursive est appelée, son contexte (variables locales, position dans le code, paramètres) est stocké dans une structure appelée pile d’appels.

Chaque nouvel appel est empilé au-dessus du précédent. Tant qu’un appel n’est pas terminé, le programme ne peut pas reprendre l’exécution de celui qui l’a invoqué.

Cela signifie que l’on descend dans l’arbre jusqu’à atteindre une feuille, puis que l’on remonte progressivement en dépilant les appels.

Exemple de déroulement pour l’arbre précédent :

parcourir(A)
  parcourir(B)
    parcourir(D)
  parcourir(C)

Chaque niveau d’indentation correspond à un appel empilé. Lorsque parcourir(D) se termine, l’exécution reprend dans parcourir(B), puis remonte jusqu’à parcourir(A).

On peut visualiser cela comme une pile d’assiettes : on empile les appels au fur et à mesure, puis on les retire dans l’ordre inverse (dernier entré, premier sorti).

Ce comportement est appelé LIFO (Last In, First Out) et constitue le fondement du fonctionnement de la récursivité.

Une récursivité trop profonde peut provoquer un dépassement de pile (stack overflow), entraînant l’arrêt du programme.

Dans ce cas, il est souvent préférable d’utiliser une version itérative avec une pile explicite, comme nous allons le voir dans la section suivante.

Cette version reproduit le comportement de la récursion, mais sans appel de fonction :

def dfs_iteratif(root):
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)
        stack.extend(reversed(node.children))

On utilise une pile explicite pour gérer les nœuds à visiter.

• On commence avec la racine dans la pile
• On dépile un nœud, on le traite
• On empile ses enfants

L’utilisation de reversed() permet de conserver le même ordre de parcours que la version récursive.

Cette approche évite les problèmes de dépassement de pile liés à la récursivité.

Après avoir exploré le parcours en profondeur, voyons maintenant une approche complémentaire : le parcours en largeur.

Dans ce modèle, chaque nœud contient une référence vers son parent.

CREATE TABLE nodes (
    id INTEGER PRIMARY KEY,
    value TEXT,
    parent_id INTEGER
);

La colonne parent_id contient l’identifiant du nœud parent. La racine de l’arbre est représentée par une valeur NULL.

Exemple de données :

id | value | parent_id
----------------------
1  | A     | NULL
2  | B     | 1
3  | C     | 1
4  | D     | 2

Ces données correspondent à l’arbre suivant :

A
├── B
│   └── D
└── C

Le nœud A est la racine (parent_id = NULL). Les nœuds B et C sont ses enfants, et D est un enfant de B.

Cette double représentation permet de faire le lien entre la structure relationnelle (table) et la structure hiérarchique (arbre).

Cette structure est simple à mettre en place et intuitive, mais elle nécessite des requêtes récursives pour reconstruire l’arbre.

Chaque nœud référence son parent, ce qui permet de reconstituer la hiérarchie.

Pour insérer un arbre complet en base, on peut utiliser une fonction récursive.

def inserer(noeud, parent_id=None):
    cursor.execute(
        "INSERT INTO nodes (value, parent_id) VALUES (?, ?)",
        (noeud.value, parent_id)
    )
    node_id = cursor.lastrowid

    for enfant in noeud.children:
        inserer(enfant, node_id)

Le fonctionnement est le suivant :

• On insère le nœud courant
• On récupère son identifiant généré
• On appelle récursivement la fonction pour chaque enfant

Cette approche garantit que chaque nœud est correctement relié à son parent.

L’ordre d’insertion suit naturellement un parcours en profondeur de l’arbre.

Une fois les données stockées, il est nécessaire de reconstruire l’arbre pour l’exploiter.

Les bases modernes comme SQLite ou PostgreSQL permettent d’utiliser des requêtes récursives via WITH RECURSIVE.

WITH RECURSIVE tree AS (
    SELECT * FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.* FROM nodes n
    JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;

Cette requête fonctionne en deux étapes :

• On sélectionne la racine (condition initiale)
• On joint récursivement les enfants à partir des nœuds déjà trouvés

Le résultat contient tous les nœuds de l’arbre.

Il est possible d’ajouter une colonne de profondeur pour mieux visualiser la hiérarchie :

WITH RECURSIVE tree(id, value, parent_id, depth) AS (
    SELECT id, value, parent_id, 0
    FROM nodes
    WHERE parent_id IS NULL

    UNION ALL

    SELECT n.id, n.value, n.parent_id, t.depth + 1
    FROM nodes n
    JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;

Les requêtes récursives permettent de reconstruire dynamiquement toute la structure de l’arbre.

Cependant, ces requêtes peuvent devenir coûteuses sur de grandes structures.

Le modèle parent-enfant est simple, mais il devient rapidement limité lorsque l’on souhaite effectuer des requêtes complexes ou optimiser les performances.

D’autres modèles permettent de représenter efficacement les structures arborescentes en base de données, chacun étant adapté à des cas d’usage spécifiques.

V-D-1. Materialized Path▲

id | value | path
------------------------
1  | A     | /1
2  | B     | /1/2
3  | C     | /1/3
4  | D     | /1/2/4

SELECT * FROM nodes WHERE path LIKE '/1/2/%';

V-D-2. Nested Sets▲

id | value | left | right
--------------------------
1  | A     | 1    | 8
2  | B     | 2    | 5
4  | D     | 3    | 4
3  | C     | 6    | 7

SELECT * FROM nodes
WHERE left BETWEEN parent.left AND parent.right;

V-D-3. Closure Table▲

CREATE TABLE closure (
    ancestor INTEGER,
    descendant INTEGER,
    depth INTEGER
);

ancestor | descendant | depth
------------------------------
1        | 1          | 0
1        | 2          | 1
1        | 4          | 2
2        | 2          | 0
2        | 4          | 1

Le format JSON est particulièrement adapté pour représenter un arbre, car il supporte naturellement les structures imbriquées.

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

    def to_dict(self):
        return {
            "value": self.value,
            "children": [c.to_dict() for c in self.children]
        }

On peut ensuite sauvegarder l’arbre dans un fichier :

import json

with open("tree.json", "w") as f:
    json.dump(root.to_dict(), f, indent=2)

Exemple de contenu du fichier tree.json :

{
  "value": "A",
  "children": [
    {
      "value": "B",
      "children": [
        {
          "value": "D",
          "children": []
        }
      ]
    },
    {
      "value": "C",
      "children": []
    }
  ]
}

Et le reconstruire :

@staticmethod
def from_dict(data):
    node = Node(data["value"])
    node.children = [Node.from_dict(c) for c in data["children"]]
    return node

Le JSON est simple, lisible et largement utilisé pour les échanges de données.

Le XML est un autre format particulièrement adapté aux structures hiérarchiques.

Exemple de fichier XML représentant le même arbre :

<node value="A">
    <node value="B">
        <node value="D"/>
    </node>
    <node value="C"/>
</node>

Cette représentation est très proche de la structure logique de l’arbre.

On peut facilement la parser en Python :

import xml.etree.ElementTree as ET

def from_xml(elem):
    node = Node(elem.attrib["value"])
    node.children = [from_xml(e) for e in elem]
    return node

Le XML est particulièrement intéressant lorsque l’on manipule déjà des documents structurés.

Une autre approche consiste à représenter l’arbre sous forme de texte avec indentation.

Exemple de fichier texte :

A
  B
    D
  C

Chaque niveau d’indentation représente la profondeur dans l’arbre.

On peut parser ce format en utilisant une pile :

def parse_tree(lines):
    stack = []
    root = None

    for line in lines:
        level = len(line) - len(line.lstrip())
        node = Node(line.strip())

        if level == 0:
            root = node
            stack = [(level, node)]
        else:
            while stack[-1][0] >= level:
                stack.pop()
            stack[-1][1].children.append(node)
            stack.append((level, node))

    return root

Ce format est très lisible pour un humain et utile pour visualiser rapidement une structure.

Python propose également un mécanisme de sérialisation natif avec le module pickle.

import pickle

with open("tree.pkl", "wb") as f:
    pickle.dump(root, f)

with open("tree.pkl", "rb") as f:
    root = pickle.load(f)

Le fichier tree.pkl contient une représentation binaire de l’arbre, non lisible directement par un humain.

Contrairement aux formats précédents, il ne s’agit pas d’un format texte mais d’une sérialisation interne à Python.

Le format pickle n’est pas sécurisé : il ne faut jamais charger un fichier provenant d’une source non fiable.

Il est cependant très pratique pour des usages internes ou des prototypes.

Chaque solution présente des avantages selon le contexte :

• JSON : simple, portable, idéal pour les API
• XML : structuré, adapté aux documents hiérarchiques
• Texte indenté : lisible et pédagogique
• pickle : rapide et pratique en Python

Il n’existe pas de solution universelle : le bon choix dépend du besoin.

Dans de nombreux cas, ces approches suffisent largement et évitent la complexité d’un stockage en base de données.

Maintenant que nous avons exploré différentes manières de représenter et de stocker des arbres, il est utile d’illustrer ces concepts à travers des exemples concrets.

Après avoir exploré les concepts, les parcours et les différentes méthodes de stockage, voyons maintenant comment ces structures apparaissent concrètement dans des cas d’usage réels.

Un arbre peut être utilisé pour représenter une expression mathématique. Chaque nœud correspond à un opérateur ou une valeur :

Exemple : l’expression suivante :

(3 + 5) * 2

Peut être représentée sous forme d’arbre :

      *
     / \
    +   2
   / \
  3   5

Dans cet arbre :

• Les feuilles (3, 5, 2) sont des valeurs
• Les nœuds internes (+, *) sont des opérateurs

Cette structure permet d’évaluer l’expression de manière récursive :

def evaluer(noeud):
    if not noeud.children:
        return int(noeud.value)

    gauche = evaluer(noeud.children[0])
    droite = evaluer(noeud.children[1])

    if noeud.value == '+':
        return gauche + droite
    elif noeud.value == '*':
        return gauche * droite

Le calcul suit naturellement la structure de l’arbre : on évalue d’abord les sous-expressions, puis on applique l’opérateur.

On peut également parcourir cet arbre selon différentes stratégies :

• Parcours en profondeur (DFS) : permet d’évaluer naturellement l’expression
• Parcours postfixe : correspond directement à l’ordre de calcul

Parcours postfixe :
3 5 + 2 *

Ce type de parcours est utilisé par de nombreux interpréteurs pour évaluer efficacement les expressions.

Les arbres d’expression sont utilisés en compilation, en interprétation de code et dans les calculatrices.

Un arbre généalogique est un exemple très intuitif de structure arborescente :

Chaque personne peut être vue comme un nœud, avec des enfants représentant la descendance.

Grand-parent
├── Parent A
│   ├── Enfant 1
│   └── Enfant 2
└── Parent B
    └── Enfant 3

Cette structure permet de représenter les relations familiales de manière hiérarchique.

On peut facilement effectuer des opérations comme :

• afficher toute la descendance d’une personne
• calculer la profondeur (nombre de générations)
• rechercher un individu dans l’arbre

Exemple de recherche récursive :

def rechercher(noeud, valeur):
    if noeud.value == valeur:
        return noeud

    for enfant in noeud.children:
        resultat = rechercher(enfant, valeur)
        if resultat:
            return resultat

    return None

Ce type de structure est utilisé dans :

• les logiciels de généalogie
• les systèmes de recommandation sociale
• la modélisation des relations humaines

Les parcours d’arbre permettent également d’explorer efficacement la structure :

• Parcours en profondeur (DFS) : explorer toute une branche familiale
• Parcours en largeur (BFS) : analyser les générations niveau par niveau

Par exemple, un parcours en largeur permet d’obtenir les individus par génération :

Niveau 0 : Grand-parent
Niveau 1 : Parent A, Parent B
Niveau 2 : Enfant 1, Enfant 2, Enfant 3

Les arbres permettent de représenter naturellement toute structure hiérarchique du monde réel.