Comment parcourir un arbre de recherche binaire

Les arbres binaires sont l’une des structures de données les plus utilisées en programmation. Un arbre de recherche binaire (BST) permet de stocker des données sous la forme de nœuds (nœud parent et nœud enfant) de telle sorte que le nœud enfant de gauche est plus petit que le nœud parent et que le nœud enfant de droite est plus grand.

Les arbres de recherche binaires permettent des opérations efficaces de traversée, de recherche, de suppression et d’insertion. Dans cet article, vous découvrirez les trois façons de parcourir un arbre de recherche binaire : la traversée avant ordre, la traversée dans l’ordre et la traversée après ordre.

Parcours dans l’ordre

Le parcours dans l’ordre consiste à parcourir les nœuds d’un arbre de recherche binaire en traitant récursivement le sous-arbre de gauche, puis le nœud racine, et enfin le sous-arbre de droite. Puisqu’elle traite les nœuds dans l’ordre croissant des valeurs, la technique est appelée traversée d’ordre.

Le parcours est le processus qui consiste à visiter chaque nœud d’une structure de données arborescente exactement une fois.

Algorithme du parcours dans l’ordre

Répétez l’opération pour parcourir tous les nœuds de la BST :

  1. Traverser récursivement le sous-arbre de gauche.
  2. Visitez le noeud racine.
  3. Traverse récursivement le sous-arbre de droite.

Visualisation du parcours de l’ordre

Un exemple visuel peut aider à expliquer le parcours d’un arbre de recherche binaire. Cette figure montre la traversée dans l’ordre d’un exemple d’arbre de recherche binaire :

Dans cet arbre de recherche binaire, 56 est le nœud racine. Vous devez d’abord parcourir le sous-arbre gauche 32, puis le nœud racine 56 et enfin le sous-arbre droit 62.

Pour le sous-arbre 32, il faut d’abord parcourir le sous-arbre gauche, 28. Ce sous-arbre n’a pas d’enfant, donc parcourez ensuite le nœud 32. Ensuite, on parcourt le sous-arbre de droite, 44, qui n’a pas non plus d’enfants. Par conséquent, l’ordre de parcours du sous-arbre enraciné à 32 est 28 -> 32 -> 44.

Voir aussi :  Comment utiliser Mongoose dans les applications Express

Visitez ensuite le nœud racine, 56.

Traversez ensuite le sous-arbre de droite, dont la racine est 62. Commencez par parcourir son sous-arbre gauche, enraciné à 58. Il n’a pas d’enfant, donc visitez le noeud 62 ensuite. Enfin, parcourez le sous-arbre de droite, 88, qui n’a pas non plus d’enfant.

L’algorithme visite donc les nœuds de l’arbre dans l’ordre suivant :

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

Application de l’inversion d’ordre

Vous pouvez utiliser le parcours dans l’ordre pour obtenir les valeurs des éléments d’un nœud dans l’ordre croissant. Pour obtenir les valeurs dans l’ordre décroissant, il suffit d’inverser le processus : visiter 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 préfixe d’un arbre d’expression.

Traversée d’une commande préalable

Le parcours préordre est similaire au parcours inordre, mais il traite le nœud racine avant de traiter récursivement le sous-arbre gauche, puis le sous-arbre droit.

Algorithme du parcours préordonné

Répéter pour parcourir tous les nœuds de la BST :

  1. Visitez le nœud racine.
  2. Traverser récursivement le sous-arbre de gauche.
  3. Traverse récursivement le sous-arbre de droite.

Visualisation du parcours du préordre

La figure suivante illustre le parcours du 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 gauche, 32, puis le sous-arbre droit, 62.

Pour le sous-arbre gauche, traitez la valeur du nœud racine, 32. Ensuite, parcourez le sous-arbre gauche, 28, puis finalement le sous-arbre droit, 44. Ceci termine la traversée du sous-arbre gauche dont la racine est 32. Le parcours s’effectue dans l’ordre suivant : 56 -> 32 -> 28 -> 44.

Voir aussi :  Comment construire un composant Web en utilisant Stencil.js

Pour le sous-arbre de droite, traitez la valeur du nœud racine, 62. Ensuite, parcourez le sous-arbre de gauche, 58, puis le sous-arbre de droite, 88. Une fois encore, aucun des deux nœuds n’a d’enfant, la traversée est donc terminée à ce stade.

Vous avez parcouru l’arbre complet dans l’ordre suivant :

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

Application du Preorder Traversal

Vous pouvez utiliser la méthode du parcours avant ordre pour créer une copie de l’arbre le plus facilement possible.

Traversée post-ordre

Le parcours post-ordre consiste à parcourir les nœuds d’un arbre de recherche binaire en traitant récursivement le sous-arbre de gauche, puis le sous-arbre de droite, et enfin le nœud racine. Puisqu’elle traite le nœud racine après les deux sous-arbres, cette méthode est appelée « postorder traversal ».

Algorithme de la traversée post-ordre

Répétez l’opération pour parcourir tous les nœuds de la BST :

  1. Traverser récursivement le sous-arbre de gauche.
  2. Traverse récursivement le sous-arbre de droite.
  3. Visitez le noeud racine.

Visualisation de la traversée récursive

La figure suivante illustre la traversée post-ordre de l’arbre de recherche binaire :

Commencez par parcourir le sous-arbre gauche, 32, puis le sous-arbre droit, 62. Terminez en traitant le nœud racine, 56.

Pour traiter le sous-arbre, enraciné à 32, parcourez son sous-arbre gauche, 28. Puisque 28 n’a pas d’enfant, passez au sous-arbre de droite, 44. Traitez 44 puisqu’il n’a pas non plus d’enfant. Enfin, traitez le nœud racine, 32. Vous avez parcouru ce sous-arbre dans l’ordre 28 -> 44 -> 32.

Voir aussi :  Comment trouver des voyelles, des consonnes, des chiffres et des caractères spéciaux dans une chaîne

Traitez le sous-arbre de droite 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 parcourrez l’arbre complet dans cet ordre :

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

Application du Postorder Traversal

Vous pouvez utiliser le postorder traversal pour supprimer un arbre de la feuille à la racine. Vous pouvez également l’utiliser pour trouver l’expression postfixe d’un arbre d’expression.

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 du postorder traversal.

Complexité temporelle et spatiale des parcours d’arbres de recherche binaires

La complexité temporelle des trois techniques de parcours est la suivante O(n), où n est la taille de l’arbre binaire. La complexité spatiale de toutes les techniques de traversée est la suivante O(h)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 recherche binaire dans l’arbre

Vous trouverez ci-dessous un programme Python permettant d’effectuer les trois parcours d’arbre de recherche binaire :

Ce programme devrait produire la sortie suivante :

Algorithmes incontournables pour les programmeurs

Les algorithmes sont une partie essentielle du parcours de tout programmeur. Il est crucial pour un programmeur de bien connaître les algorithmes. Vous devez être familier avec certains algorithmes tels que le tri par fusion, le tri rapide, la recherche binaire, la recherche linéaire, la recherche par profondeur, etc.

Cliquez pour évaluer cet article !
[Total: Moyenne : ]

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *