Il existe plusieurs façons de visiter tous les nœuds d'un BST.
Les arbres binaires sont l'une des structures de données les plus utilisées en programmation. Un arbre binaire de recherche (BST) permet le stockage des données sous forme de nœuds (nœud parent et nœud enfant nœud) de sorte que le nœud enfant gauche soit plus petit que le nœud parent et que le nœud enfant droit soit plus grand.
Les arbres de recherche binaires permettent des opérations de parcours, de recherche, de suppression et d'insertion efficaces. Dans cet article, vous découvrirez les trois manières de parcourir un arbre de recherche binaire: parcours pré-ordre, parcours in-ordre et parcours post-ordre.
Parcours dans l'ordre
Le parcours dans l'ordre est le processus de traversée des nœuds d'un arbre de recherche binaire en traitant récursivement le sous-arbre gauche, puis en traitant le nœud racine, et enfin en traitant récursivement le sous-arbre droit. Puisqu'elle traite les nœuds dans l'ordre croissant des valeurs, la technique est appelée parcours dans l'ordre.
La traversée est le processus consistant à visiter chaque nœud d'une structure de données arborescente exactement une fois.
Algorithme de parcours dans l'ordre
Répétez l'opération pour parcourir tous les nœuds du BST :
- Parcourir récursivement le sous-arbre gauche.
- Visitez le nœud racine.
- Traverser récursivement le sous-arbre droit.
Visualisation de la traversée de l'ordre
Un exemple visuel peut aider à expliquer la traversée de l'arbre de recherche binaire. Cette figure montre le parcours dans l'ordre d'un exemple d'arbre de recherche binaire :
Dans cet arbre de recherche binaire, 56 est le nœud racine. Tout d'abord, vous devez parcourir le sous-arbre gauche 32, puis le nœud racine 56, puis le sous-arbre droit 62.
Pour le sous-arbre 32, parcourez d'abord le sous-arbre de gauche, 28. Ce sous-arbre n'a pas d'enfants, alors traversez ensuite le nœud 32. Ensuite, traversez le sous-arbre de droite, 44, qui n'a pas non plus d'enfants. Par conséquent, l'ordre de parcours pour le sous-arbre enraciné à 32 est 28 -> 32 -> 44.
Ensuite, visitez le nœud racine, 56.
Ensuite, traversez le sous-arbre de droite, enraciné à 62. Commencez par parcourir son sous-arbre gauche, enraciné à 58. Il n'a pas d'enfants, alors visitez ensuite le nœud 62. Enfin, traversez le sous-arbre de droite, 88, qui n'a pas non plus d'enfants.
L'algorithme visite donc les nœuds de l'arbre dans l'ordre suivant :
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Application du parcours dans l'ordre
Vous pouvez utiliser la traversée dans l'ordre pour obtenir les valeurs des éléments de nœud dans l'ordre croissant. Pour obtenir les valeurs dans l'ordre décroissant, inversez simplement le processus: visitez le sous-arbre de droite, puis le nœud racine, puis le sous-arbre de gauche. Vous pouvez utiliser l'algorithme pour trouver l'expression de préfixe d'une arborescence d'expressions.
Traversée de précommande
La traversée de préordre est similaire à inorder, mais elle traite le nœud racine avant de traiter de manière récursive le sous-arbre gauche, puis le sous-arbre droit.
Algorithme de traversée de précommande
Répétez pour parcourir tous les nœuds du BST :
- Visitez le nœud racine.
- Parcourir récursivement le sous-arbre gauche.
- Traverser récursivement le sous-arbre droit.
Visualisation de la traversée des précommandes
La figure suivante montre le parcours de préordre de l'arbre de recherche binaire :
Dans cet arbre de recherche binaire, commencez par traiter le nœud racine, 56. Traversez ensuite le sous-arbre de gauche, 32, suivi du sous-arbre de droite, 62.
Pour le sous-arbre de gauche, traitez la valeur au nœud racine, 32. Ensuite, traversez le sous-arbre de gauche, 28, puis enfin le sous-arbre de droite, 44. Ceci termine la traversée du sous-arbre gauche enraciné à 32. Le parcours s'effectue dans l'ordre suivant: 56 -> 32 -> 28 -> 44.
Pour le sous-arbre de droite, traitez la valeur au nœud racine, 62. Ensuite, traversez le sous-arbre de gauche, 58, puis enfin le sous-arbre de droite, 88. Encore une fois, aucun nœud n'a d'enfant, donc la traversée est terminée à ce stade.
Vous avez parcouru l'arborescence complète dans l'ordre suivant :
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Application de la traversée des précommandes
Vous pouvez utiliser la traversée de préordre pour créer plus facilement une copie de l'arbre.
Traversée de post-commande
La traversée post-ordre est le processus de traversée des nœuds d'un arbre de recherche binaire en récursivement traiter le sous-arbre gauche, puis traiter récursivement le sous-arbre droit, et enfin traiter le Noeud principal. Puisqu'il traite le nœud racine après les deux sous-arbres, cette méthode est appelée traversée post-ordre.
Algorithme de Postorder Traversal
Répétez l'opération pour parcourir tous les nœuds du BST :
- Parcourir récursivement le sous-arbre gauche.
- Traverser récursivement le sous-arbre droit.
- Visitez le nœud racine.
Visualisation de Postorder Traversal
La figure suivante montre le parcours post-ordre de l'arbre de recherche binaire :
Commencez par parcourir le sous-arbre de gauche, 32, puis le sous-arbre de droite, 62. Terminez en traitant le nœud racine, 56.
Pour traiter le sous-arbre, enraciné à 32, traversez son sous-arbre gauche, 28. Puisque 28 n'a pas d'enfants, déplacez-vous vers le sous-arbre de droite, 44. Processus 44 puisqu'il n'a pas non plus d'enfants. Enfin, traitez le nœud racine, 32. Vous avez parcouru ce sous-arbre dans l'ordre 28 -> 44 -> 32.
Traitez le sous-arbre droit en utilisant la même approche pour visiter les nœuds dans l'ordre 58 -> 88 → 62.
Enfin, traitez le nœud racine, 56. Vous allez parcourir l'arborescence complète dans cet ordre :
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Application de Postorder Traversal
Vous pouvez utiliser la traversée post-ordre pour supprimer un arbre de la feuille à la racine. Vous pouvez également l'utiliser pour trouver l'expression postfixée d'une arborescence d'expressions.
Pour visiter tous les nœuds feuilles d'un certain nœud avant de visiter le nœud lui-même, vous pouvez utiliser la technique de traversée post-ordre.
Complexité temporelle et spatiale des traversées d'arbres de recherche binaires
La complexité temporelle des trois techniques de traversée est Sur), où n est la taille du arbre binaire. La complexité spatiale de toutes les techniques de parcours est Oh), où h est la hauteur de l'arbre binaire.
La taille de l'arbre binaire est égale au nombre de nœuds de cet arbre. La hauteur de l'arbre binaire est le nombre d'arêtes entre le nœud racine de l'arbre et son nœud feuille le plus éloigné.
Code Python pour la traversée de l'arbre de recherche binaire
Vous trouverez ci-dessous un programme Python permettant d'effectuer les trois traversées binaires de l'arbre de recherche :
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(root):
if root:
# Traverse left subtree
inorder(root.left)# Traverse root
print(str(root.value) + ", ", end='')# Traverse right subtree
inorder(root.right)# Function to perform the postorder tree traversal
defpostorder(root):
if root:
# Traverse left subtree
postorder(root.left)# Traverse right subtree
postorder(root.right)# Traverse root
print(str(root.value) + ", ", end='')# Function to perform the preorder tree traversal
defpreorder(root):
if root:
# Traverse root
print(str(root.value) + ", ", end='')# Traverse left subtree
preorder(root.left)# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
Ce programme devrait produire la sortie suivante :
Algorithmes indispensables pour les programmeurs
Les algorithmes sont une partie essentielle du parcours de chaque programmeur. Il est crucial pour un programmeur de bien connaître les algorithmes. Vous devez être familiarisé avec certains des algorithmes tels que le tri par fusion, le tri rapide, la recherche binaire, la recherche linéaire, la recherche en profondeur, etc.
