HOWTO · Python

Implémenter une structure de données arborescente en Python

Dans cet article, nous verrons comment implémenter une structure de données arborescente en Python.

Sur cette page

Un arbre organise les données en nœuds reliés par des arêtes. Chaque arête relie un parent à un enfant, et un nœud sans enfant est une feuille. Il existe notamment des arbres binaires, ternaires, binaires de recherche et AVL ; dans un arbre binaire, chaque nœud a au maximum deux enfants. Ce guide construit un petit arbre binaire avec une classe Node personnalisée, le parcourt selon trois ordres en profondeur d’abord et présente anytree comme solution de bibliothèque.

Arbre binaire dont la racine est 10, avec les enfants 34 et 89, et les enfants 45 et 50 sous 34

Implémenter une structure d’arbre à partir de zéro en Python

Un nœud d’arbre binaire simple doit stocker sa valeur et contenir des références vers ses deux enfants. La classe Node ci-dessous stocke la valeur dans data ; left et right valent initialement None et peuvent ensuite référencer des nœuds enfants. Relier ces objets permet de construire l’arbre.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

Ici, root est le parent de 34 et de 89. Les nœuds 45 et 50 sont les enfants de 34 ; 89, 45 et 50 sont des feuilles. Cette structure est précisément un arbre binaire, car chaque nœud possède au maximum deux références vers des enfants. D’autres types d’arbres peuvent nécessiter une représentation différente, par exemple une collection d’enfants plutôt que les attributs fixes left et right.

Parcourir un arbre binaire en Python

Un parcours traite chaque nœud une seule fois ; l’ordre dépend du moment où le nœud est visité par rapport aux appels récursifs. En préordre, on visite le nœud courant avant ses sous-arbres gauche et droit. En parcours infixe, on visite le sous-arbre gauche, le nœud courant, puis le sous-arbre droit. En postordre, on visite les deux sous-arbres avant le nœud courant. L’exemple complet ci-dessous construit le même arbre et affiche chacun de ces ordres.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)

Les appels récursifs suivent les mêmes références left et right que celles créées dans la première section. Pour parcourir un autre arbre, conservez les fonctions de parcours et remplacez la construction des nœuds ; la position choisie pour la visite détermine l’ordre des valeurs.

Implémenter un arbre avec une bibliothèque Python

Pour des arbres comportant de nombreux nœuds ou des fonctionnalités qui dépassent ce petit exemple d’arbre binaire, anytree fournit la gestion des relations entre nœuds ainsi qu’un outil d’affichage. Installez-le dans l’environnement de votre projet avec pip install anytree. Dans son API, Node reçoit le nom du nœud comme argument positionnel ; transmettez parent=root comme argument nommé pour rattacher un enfant. RenderTree parcourt la hiérarchie et fournit le préfixe qui sert à afficher chaque niveau.

Pour obtenir la même structure que ci-dessus, utilisez root = Node("10"), puis Node("34", parent=root) et Node("89", parent=root). Créez Node("45", parent=left_child) et Node("50", parent=left_child) pour placer les deux feuilles sous 34, puis parcourez for pre, fill, node in RenderTree(root) et affichez pre + node.name. Ces extraits décrivent l’API de la bibliothèque ; aucune preuve de leur exécution n’est fournie.