Python - Algorithmes de traversée des arbres
La traversée est un processus permettant de visiter tous les nœuds d'un arbre et peut également imprimer leurs valeurs. Parce que tous les nœuds sont connectés via des bords (liens), nous partons toujours du nœud racine (tête). Autrement dit, nous ne pouvons pas accéder de manière aléatoire à un nœud dans un arbre. Il y a trois façons que nous utilisons pour traverser un arbre -
- Traversée en ordre
- Précommander Traversal
- Traversée post-commande
Traversée en ordre
Dans cette méthode de traversée, le sous-arbre gauche est visité en premier, puis la racine et plus tard le sous-arbre droit. Nous devons toujours nous rappeler que chaque nœud peut représenter un sous-arbre lui-même.
Dans le programme python ci-dessous, nous utilisons la classe Node pour créer des espaces réservés pour le nœud racine ainsi que pour les nœuds gauche et droit. Ensuite, nous créons une fonction d'insertion pour ajouter des données à l'arborescence. Enfin, la logique de traversée Inorder est implémentée en créant une liste vide et en ajoutant le nœud de gauche en premier suivi du nœud racine ou parent. Enfin, le nœud gauche est ajouté pour terminer le parcours Inorder. Veuillez noter que ce processus est répété pour chaque sous-arbre jusqu'à ce que tous les nœuds soient traversés.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -
[10, 14, 19, 27, 31, 35, 42]Précommander Traversal
Dans cette méthode de traversée, le nœud racine est visité en premier, puis le sous-arbre gauche et enfin le sous-arbre droit.
Dans le programme python ci-dessous, nous utilisons la classe Node pour créer des espaces réservés pour le nœud racine ainsi que pour les nœuds gauche et droit. Ensuite, nous créons une fonction d'insertion pour ajouter des données à l'arborescence. Enfin, la logique de parcours de précommande est implémentée en créant une liste vide et en ajoutant le nœud racine en premier suivi du nœud gauche. Enfin, le nœud droit est ajouté pour terminer le parcours de précommande. Veuillez noter que ce processus est répété pour chaque sous-arbre jusqu'à ce que tous les nœuds soient traversés.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -
[27, 14, 10, 19, 35, 31, 42]Traversée post-commande
Dans cette méthode de traversée, le nœud racine est visité en dernier, d'où le nom. Nous traversons d'abord le sous-arbre gauche, puis le sous-arbre droit et enfin le nœud racine.
Dans le programme python ci-dessous, nous utilisons la classe Node pour créer des espaces réservés pour le nœud racine ainsi que pour les nœuds gauche et droit. Ensuite, nous créons une fonction d'insertion pour ajouter des données à l'arborescence. Enfin, la logique de traversée post-ordre est implémentée en créant une liste vide et en ajoutant le nœud de gauche en premier suivi du nœud de droite. Enfin, le nœud racine ou parent est ajouté pour terminer le parcours post-ordre. Veuillez noter que ce processus est répété pour chaque sous-arbre jusqu'à ce que tous les nœuds soient traversés.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -
[10, 19, 14, 31, 42, 35, 27]