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

1. Implémenter un arbre à partir de zéro en Python
2. Traverser un arbre binaire en Python
3. Implémenter une arborescence à l’aide d’une bibliothèque Python

Un arbre est l’une des structures de données. Une structure de données n’est rien d’autre que la façon dont nous organisons les données en mémoire. Un arbre est une combinaison de nœuds (également appelés sommets) et d’arêtes. Un arbre peut avoir n’importe quel nombre de nœuds et d’arêtes. Un nœud est l’endroit où nous stockons les données, et une arête est un chemin entre 2 nœuds. Il existe différents types d’arbres disponibles comme un arbre binaire, un arbre ternaire, un arbre de recherche binaire, un arbre AVL, etc.

Types de nœuds dans un arbre:

1. Nœud parent: un nœud qui a un ou plusieurs enfants.
2. Nœud enfant: un nœud qui a un nœud parent.
3. Nœud feuille: un nœud qui n’a pas d’enfants.

Dans cet article, voyons d’abord comment implémenter un arbre à partir de zéro sans utiliser de bibliothèque, et plus tard, vous verrez comment implémenter un arbre à l’aide d’une bibliothèque Python.

Implémenter un arbre à partir de zéro en Python

Pour créer un arbre en Python, il faut d’abord créer une classe Node qui représentera un seul nœud. Cette classe Node contiendra 3 variables; la première est la left pointant vers l’enfant gauche, la seconde variable data contenant la valeur de ce nœud, et la variable right pointant vers l’enfant droit.

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

Initialisons un arbre.

root = Node(10)

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

L’arbre ressemble à ci-dessous.

          10
        /    \
       34      89
     /    \ 
    45    50 

Chaque fois que vous créez un objet de classe Node, le constructeur __init__ sera appelé, et toutes les variables à l’intérieur de ce constructeur seront initialisées. La root contient le nœud racine de l’arbre, qui a une valeur de 10, et root.left et root.right à l’aide desquels nous insérerons l’enfant de gauche avec la valeur 34 et celui de droite enfant au nœud racine avec la valeur 89. Puisqu’il s’agit d’un arbre binaire, chaque nœud contiendra au plus deux nœuds.

À la fin, nous insérons deux autres nœuds dans l’arbre c’est-à-dire 45 et 50, comme les enfants du nœud 34. Vous pouvez insérer autant de nœuds que vous le souhaitez dans une arborescence en fonction du type d’arbre que vous créez.

Traverser un arbre binaire en Python

Maintenant que nous avons créé un arbre, parcourons l’arbre pour imprimer les éléments de l’arbre. Un parcours visite tous les nœuds d’un arbre. Chaque nœud d’un arbre sera visité trois fois dans le parcours. Une façon dont nous traversons un arbre est de haut en bas et de gauche à droite.

Traversée en préordre

En parcourant un arbre, chaque fois que nous voyons le nœud pour la première fois, nous imprimons ce nœud, puis nous effectuons une récursivité sur le nœud gauche puis sur le nœud droit.

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

Production:

10 
34 
45 
50 
89

Traversée dans l’ordre

Tout en effectuant une traversée dans l’ordre, nous effectuons d’abord une récursivité sur le nœud gauche, puis lorsque nous visitons le même nœud pour la deuxième fois, nous imprimons ce nœud. Ensuite, nous effectuons une récursion sur le noeud de droite.

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

Production:

45 
34 
50 
10 
89

Traversée post-ordre

Pour la traversée post-ordre, nous effectuons une récursivité sur le nœud gauche et le nœud droit, puis lorsque nous visitons le même nœud pour la troisième fois, nous imprimons ce nœud.

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

Production:

45
50
34
89
10

Implémenter une arborescence à l’aide d’une bibliothèque Python

Comme nous l’avons vu, l’implémentation d’un arbre à partir de zéro prend du temps et nécessite beaucoup de code. Un moyen plus simple d’implémenter un arbre en Python est d’utiliser une bibliothèque appelée anytree. La bibliothèque anytree vous permet de créer un arbre sans écrire une tonne de code.

Pour utiliser la bibliothèque anytree, nous devons d’abord l’installer avec l’aide de la commande ci-dessous.

pip install anytree

Ici aussi, nous créons le même arbre que nous avons créé précédemment. Nous pouvons maintenant importer Node et RenderTree depuis la bibliothèque anytree.

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

Production:

10
├── 34
│   └── 45
└── 89
    └── 50

Ici, le Node créera pour nous un nœud qui prend deux paramètres; le premier est la valeur du nœud et le second est le nom du nœud parent (il s’agit d’un paramètre facultatif). Puisque dans notre arbre le nœud root est le seul nœud qui n’a pas de parent, lors de la création du nœud root, nous ne passerons que le premier paramètre: la valeur du nœud et non le deuxième paramètre. La méthode RenderTree nous aidera à imprimer l’arborescence entière comme indiqué dans la sortie.