Traversée dans l'ordre d'un arbre en Python

1. Parcours dans l’ordre d’un arbre
2. Implémentation de la traversée de l’arbre d’ordre en Python

Un arbre est une structure de données hiérarchique constituée de nœuds reliés par des arêtes. Traverser un arbre signifie visiter chaque nœud de l’arbre exactement une fois.

Nous parcourons l’arbre à différentes fins comme afficher les nœuds, trouver le plus grand et le plus petit nœud, rechercher, trier, etc. Dans cet article, nous allons apprendre et implémenter le parcours inorder d’un arbre en Python.

Parcours dans l’ordre d’un arbre

Le parcours “dans l’ordre” est une sorte de parcours en profondeur d’abord. Supposons que nous ayons l’arbre suivant.

Si nous appliquons le parcours inorder, nous suivrons les étapes ci-dessous pour chaque nœud.

1. Tout d’abord, nous devons visiter tous les nœuds du sous-arbre de gauche.
2. Ensuite, nous visitons le nœud parent.
3. Ensuite, nous visitons tous les nœuds du sous-arbre de droite.

Nous obtiendrons les nœuds dans l’ordre 4, 2, 5, 1, 6, 3, 7.

Implémentation de la traversée de l’arbre d’ordre en Python

Il existe deux manières d’implémenter le parcours inorder en Python. Approche récursive et itérative.

Approche récursive

L’approche récursive est facile à mettre en œuvre et à comprendre. Dans le code suivant, nous avons créé une classe Node comme structure de données pour stocker l’arbre.

Chaque nœud se compose d’une valeur, de ses enfants gauche et droit. Le parcours inorder fonctionnera de manière récursive pour les sous-arbres gauche et droit.

Pour chaque nœud, la traversée inorder sera effectuée en visitant son nœud gauche, le parent et le nœud droit.

Exemple de code :

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


def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.val))
        inorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Production:

Inorder traversal of the Tree
4
2
5
1
6
3
7

Approche itérative

Dans une approche itérative, nous devons maintenir une pile pour stocker les nœuds que nous visiterons plus tard. Nous avons créé la classe Node dans le code suivant, comme avant.

Nous avons créé une pile vide et commencé à partir du nœud racine en en faisant le nœud actuel. Si le nœud actuel existe, nous allons le pousser vers la pile et aller vers son nœud de gauche.

Sinon, si le nœud n’existe pas, nous extrairons un élément de la pile et l’imprimerons. Lorsqu’aucun nœud de gauche n’existe, nous irons au nœud de droite en en faisant le nœud courant.

Nous répéterons la même procédure de manière itérative jusqu’à ce que la pile et l’élément courant soient vides.

Exemple de code :

from collections import deque


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


def inorder(root):
    stack = deque()
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            print(curr.val)
            curr = curr.right


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Production:

Inorder traversal of the Tree
4
2
5
1
6
3
7