Structures de données récursives
Reading time5 minEn bref
Résumé de l’article
Dans cet article, nous vous présentons ce qu’est une structure de données récursive. Une structure de données récursive est une structure qui peut être définie à partir de l’une au moins de ses sous-structures, permettant ainsi de créer des structures complexes à partir d’éléments plus simples. Nous verrons comment les structures de données récursives sont utilisées pour représenter des listes chaînées et des arbres binaires, et comment elles peuvent être implémentées en Python.
Points clés
-
Certaines structures de données peuvent également être définies récursivement.
-
Une liste chaînée est une structure de données où les éléments sont stockés dans des emplacements mémoires séparés et liés entre eux à l’aide de références.
-
Un arbre binaire est une structure de données où chaque nœud a au plus deux enfants, et peut être représenté par des nœuds composés de trois parties : données, lien vers l’enfant gauche et lien vers l’enfant droit. Chaque lien vers un descendant pointe vers un emplacement vide ou un (sous-)arbre binaire.
Contenu de l’article
1 — Structures de données récursives
La récursivité ne s’applique pas seulement aux fonctions mais également à la représentation des données (les classes en programmation).
Tout comme dans une méthode récursive, il y a (au moins) un appel à cette méthode,
dans une classe récursive, il y a une (ou plusieurs) variable dont le type est la classe elle-même.
Comme pour les fonctions récursives, deux cas sont nécessaires pour définir une structure de données récursive :
- Cas de base – La variable de la classe est fixée à une valeur de base (p-ex,
None
), c’est-à-dire qu’elle ne fait pas référence à une instance du même type. - Cas récursif – La variable de la classe est fixée à une instance de la même classe, c’est-à-dire qu’elle fait référence à un objet du même type.
class RecursiveClass:
"""
A class that demonstrates a recursive structure.
It can either be empty (base case) or contain a reference to another instance of the same class (recursive case).
"""
def __init__(self, value=None):
self.value = value
self.next = None # This can point to another instance of RecursiveClass
2 — Liste chaînée
L’exemple le plus courant est la liste chaînée.
Une liste chaînée est une structure de données où les éléments sont stockés dans des emplacements mémoires séparés et liés entre eux à l’aide de références. Chaque nœud a deux parties :
- Données – L’élément à stocker dans le nœud.
- Lien – Une référence vers le nœud suivant.
Le cas de base est le nœud qui ne fait référence à aucun autre nœud (sa référence est définie à None
), c’est-à-dire qu’il est le dernier de la liste.
Le cas récursif est le nœud qui fait référence à un autre nœud du même type, ce qui permet de créer une liste chaînée.
|
---|
Exemple de liste chaînée (src: wikipedia) |
La classe Node
En programmation, pour déclarer une liste chaînée, on utilise une classe Node récursive. Celle-ci contient non seulement des données, mais aussi une référence vers un autre objet de la même classe.
from typing import Any
type Node = Node
class Node:
"""
A class representing a node in a linked list.
Each node contains data and a reference to the next node.
"""
def __init__(self, data: Any):
"""
Initializes a new node with the given data and no next node.
:param data: The data to be stored in the node.
"""
self.data = data
self.next = None
def get_data(self):
"""
Returns the data stored in the node.
:return: The data of the node.
"""
return self.data
def get_next(self):
"""
Returns the next node in the linked list.
:return: The next node, or None if there is no next node.
"""
return self.next
def set_next(self, next_node: Node) :
"""
Sets the next node in the linked list.
:param next_node: The next node to be linked.
"""
self.next = next_node
if __name__ == "__main__":
# Example usage
node1 = Node(12)
node2 = Node(99)
node3 = Node(37)
node1.set_next(node2) # node1 points to node2
node2.set_next(node3) # node2 points to node3
print(node1.get_data()) # Output: 12
print(node1.get_next().get_data()) # Output: 99
print(node2.get_next().get_data()) # Output: 37
Cette structure est efficace pour insérer et supprimer des éléments car elle ne nécessite pas d’adapter la taille ou de décaler les éléments, comme dans un tableau.
La classe LinkedList
Pour simplifier l’usage des nœuds et en cacher l’existence, on peut créer une classe qui gère la liste chaînée dans son ensemble, en fournissant des méthodes pour ajouter des éléments, supprimer des éléments, et parcourir la liste. La notion de nœud devient alors une implémentation interne de la classe, et l’utilisateur de la classe n’a pas besoin de connaître les détails de sa structure.
# We suppose that the Node class is defined as above
# and is available in the same file or imported.
class LinkedList:
"""
A class representing a singly linked list.
It contains methods to add nodes and traverse the list.
"""
def __init__(self):
"""
Initializes an empty linked list with no head node.
"""
self.head = None
def add(self, data : Any):
"""
Adds the given data to the end of the list.
"""
new_node = Node(data)
if not self.head: # If the list is empty, set the new node as the head
self.head = new_node
return
current = self.head
while current.get_next(): # Look for the last node
current = current.get_next()
current.set_next(new_node)
def traverse(self):
"""
Traverses the list and prints the data of each node.
"""
current = self.head
while current:
print(current.get_data())
current = current.get_next()
# Example usage
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.add("Brest")
linked_list.add("Nantes")
linked_list.add("Rennes")
print("Les campus de l'IMT Atlantique sont :")
linked_list.traverse()
# Output:
# Brest
# Nantes
# Rennes
Les méthodes de la classe LinkedList
tirent parti de la structure récursive des nœuds pour ajouter des éléments et parcourir la liste.
Lorsque le dernier élément pointe vers le premier élément, la liste chaînée devient une liste chaînée circulaire.
Les notions de début et de fin de la liste deviennent alors floues, car il n’y a pas de nœud “dernier” qui pointe vers None
.
En maintenant une référence vers le dernier nœud, on peut toujours ajouter de nouveaux nœuds à la fin ou au début de la liste efficacement.
Il faut alors être vigilant pour éviter les boucles infinies lors du parcours de la liste mais cette structure est utile pour représenter des files d’attente circulaires ou des jeux en tour de rôle.
3 — Arbre binaire
Un autre exemple de structure de données récursive est l’arbre binaire. Un arbre binaire est une structure de données où chaque nœud a au plus deux enfants, appelés enfant gauche et enfant droit. Chaque nœud peut être vu comme un sous-arbre, et l’arbre entier est un ensemble de nœuds reliés entre eux.
|
---|
Exemple d’arbre binaire (src: wikipedia) |
La classe Node
pour un arbre binaire peut être définie comme suit :
from typing import Any
type BinaryTreeNode = BinaryTreeNode
class BinaryTreeNode:
"""
A class representing a node in a binary tree.
Each node contains data and references to the left and right children.
"""
def __init__(self, data : Any):
"""
Initializes a binary tree node with the given data.
"""
self.data = data
self.left = None
self.right = None
def get_data(self) -> Any:
"""
Returns the data stored in the node.
:return: The data of the node.
"""
return self.data
def get_left(self) -> BinaryTreeNode:
"""
Returns the left child of the node.
:return: The left child node, or None if there is no left child.
"""
return self.left
def get_right(self) -> BinaryTreeNode:
"""
Returns the right child of the node.
:return: The right child node, or None if there is no right child.
"""
return self.right
def set_left(self, left_node : BinaryTreeNode):
"""
Sets the left child of the node.
:param left_node: The left child node to be linked.
"""
self.left = left_node
def set_right(self, right_node : BinaryTreeNode):
"""
Sets the right child of the node.
:param right_node: The right child node to be linked.
"""
self.right = right_node
if __name__ == "__main__":
# Example usage
root = BinaryTreeNode(8)
left_child = BinaryTreeNode(3)
right_child = BinaryTreeNode(10)
root.set_left(left_child) # Set left child
root.set_right(right_child) # Set right child
# ...
print("Root data:", root.get_data())
Le parcours d’un arbre représenté de cette manière est simple à exprimer à l’aide d’une fonction récursive. Il est, par exemple, possible de parcourir un arbre binaire en profondeur (DFS) en visitant d’abord le nœud racine, puis en parcourant récursivement l’enfant gauche (et donc son sous-arbre), et enfin l’enfant droit. Ou de le parcourir en largeur (BFS) en visitant d’abord les nœuds de la même profondeur avant de descendre dans l’arbre.
L’arbre binaire présenté ci-dessus est particulier puisqu’il est ordonné, c’est-à-dire que les nœuds sont organisés de manière à ce que les valeurs des nœuds de l’enfant gauche soient inférieures à celles du nœud parent, et celles de l’enfant droit soient supérieures. Cette structure est appelée arbre binaire de recherche (ou BST pour Binary Search Tree).
Pour aller plus loin
- Recursively defined sets and structures.
Support from a course that gives details on recursive structures.