La traversée InOrder est l’une des trois façons populaires de traverser une structure de données d’arbre binaire, les deux autres étant le preOrder et le postOrder. Au cours de l’algorithme de traversée dans l’ordre, le sous-arbre de gauche est exploré en premier, suivi de la racine, et enfin des nœuds du sous-arbre de droite. Vous commencez la traversée à partir de la racine, puis vous allez vers le nœud de gauche, puis encore vers le nœud de gauche jusqu’à ce que vous atteigniez un nœud feuille. À ce moment-là, vous imprimez la valeur du nœud ou vous le marquez comme visité et vous vous déplacez vers le sous-arbre de droite. On continue le même algorithme jusqu’à ce que tous les nœuds de l’arbre binaire soient visités. La traversée InOrder est également connue sous le nom de traversée gauche-nœud-droit ou traversée gauche-racine-droite ou algorithme de traversée LNR.
Similaire à l’algorithme preOrder, c’est aussi un algorithme de profondeur d’abord car il explore la profondeur d’un arbre binaire avant d’explorer les frères et sœurs. Comme c’est l’un des algorithmes d’arbre binaire fondamentaux, il est assez populaire dans les entretiens de programmation.
Ces algorithmes de traversée sont également la base pour apprendre des algorithmes d’arbre binaire plus avancés, donc chaque programmeur devrait apprendre, comprendre et savoir comment mettre en œuvre l’algorithme inOrder et les autres algorithmes de traversée.
La façon la plus simple de mettre en œuvre l’algorithme inOrder traversal en Java ou dans n’importe quel langage de programmation est d’utiliser la récursion. Puisque l’arbre binaire est une structure de données récursive, la récursion est le choix naturel pour résoudre un problème basé sur l’arbre. La méthode inOrder() de la classe BinaryTree implémente la logique pour traverser un arbre binaire en utilisant la récursion.
Du point de vue de l’Interview, la traversée InOrder est extrêmement importante car elle imprime également les nœuds d’un arbre de recherche binaire dans l’ordre trié mais seulement si l’arbre donné est un arbre de recherche binaire. Si vous vous souvenez, dans un arbre de recherche binaire, la valeur des nœuds du sous-arbre de gauche est inférieure à celle de la racine, et les valeurs des nœuds du sous-arbre de droite sont supérieures à celles de la racine. Le In order traversal signifie littéralement IN order c’est-à-dire que les notes sont imprimées dans l’ordre ou l’ordre trié.
Btw, même si ces trois algorithmes (pre-order, in-order, et post-order) sont des algorithmes populaires de traversée d’arbres binaires mais ils ne sont pas les seuls. Vous avez également d’autres façons breadth-first de traverser un arbre binaire, par exemple la traversée par ordre de niveau (Voir Structure de données et algorithmes : Deep Dive).

L’algorithme récursif pour implémenter la traversée InOrder d’un arbre binaire

L’algorithme récursif de la traversée inorder est très simple. Il suffit d’appeler la méthode inOrder() de la classe BinaryTree dans l’ordre où l’on souhaite visiter l’arbre. Le plus important est d’inclure le cas de base, qui est la clé de tout algorithme récursif.
Par exemple, dans ce problème, le cas de base est que vous atteignez le nœud de la feuille et qu’il n’y a plus de nœud à explorer, à ce moment-là, la récursion commence à s’épuiser. Voici les étapes exactes pour traverser l’arbre binaire en utilisant InOrder traversal:

1. visiter le nœud gauche
2. imprimer la valeur de la racine
3. visiter le nœud droit

et voici l’exemple de code pour mettre en œuvre cet algorithme en utilisant la récursion en Java :
Similaire à la méthode preOrder() du dernier exemple, il existe une autre méthode inOrder() qui expose la traversée de l’ordre au public et appelle cette méthode privée qui effectue réellement la traversée de l’ordre.
C’est la façon standard d’écrire une méthode récursive qui prend des entrées, cela facilite l’appel de la méthode par un client.

public void inOrder() { inOrder(root);}

Vous pouvez voir que nous commençons par root et que nous appelons ensuite récursivement la méthode inOrder() avec node.left, ce qui signifie que nous descendons sur le sous-arbre gauche jusqu’à ce que nous atteignions node == null, ce qui signifie que le dernier nœud était un nœud feuille.
À ce moment-là, la méthode inOrder() reviendra et exécutera la ligne suivante, qui imprime le node.data. Après cela, son appel récursif inOrder() avec node.right, qui lancera à nouveau le même processus.
Vous pouvez également consulter les cours Data Structure and Algorithms Part 1 and 2 sur Pluralsight pour en savoir plus sur les algorithmes et comment concevoir vos propres algorithmes.

Btw, vous auriez besoin d’une adhésion à Pluralsight pour accéder à ce cours, qui coûte environ 29 $ par mois ou 299 $ par an (14% d’économie). J’en ai un et je suggère également à tous les développeurs d’avoir ce plan parce que Pluralsight est comme NetFlix pour les développeurs de logiciels.
Il a plus de 5000+ cours de bonne qualité sur tous les derniers sujets. Puisque nous, les programmeurs, devons apprendre de nouvelles choses tous les jours, un investissement de 299 USD n’est pas mauvais.
Btw, il offre également un essai gratuit de 10 jours sans aucune obligation qui vous permet de regarder 200 heures de contenu. Vous pouvez regarder ces cours gratuitement en signant pour cet essai gratuit de 10 jours.

Programme Java pour mettre en œuvre la traversée InOrder d’un arbre binaire

Voici notre solution complète à l’algorithme de traversée inorder en Java. Ce programme utilise un algorithme récursif pour imprimer la valeur de tous les nœuds d’un arbre binaire en utilisant InOrder traversal.
Comme je vous l’ai déjà dit, pendant le in-order traversal la valeur du sous-arbre gauche est imprimée en premier, suivie de la racine et du sous-arbre droit. Si vous êtes intéressé par l’algorithme itératif, vous pouvez vérifier plus loin ce tutoriel de mise en œuvre de la traversée en ordre sans récursion.
C’est tout sur la façon de mettre en œuvre la traversée en ordre d’un arbre binaire en Java en utilisant la récursion. Vous pouvez voir que le code est assez similaire à la traversée preOrder avec la seule différence dans l’ordre où nous appelons récursivement la méthode. Dans ce cas, nous appelons inOrder(node.left) d’abord et ensuite nous imprimons la valeur du nœud.
Il est utile de se rappeler que la traversée inOrder est un algorithme de profondeur d’abord et imprime le nœud de l’arbre dans l’ordre trié si l’arbre binaire donné est un arbre de recherche binaire.
Dans la prochaine partie de cet article, je partagerai inOrder traversal sans récursion, en attendant, vous pouvez essayer de pratiquer les problèmes de structure de données et d’arbre binaire suivants.
Apprentissage supplémentaire
Structures de données et algorithmes : Deep Dive Using Java
Algorithmes et structures de données – Partie 1 et 2
Structures de données en Java 9 par Heinz Kabutz
Cracking the Coding Interview – 189 questions et solutions
Grokking the Coding Interview : Patterns pour les questions de codage
Autres tutoriels sur les structures de données et les algorithmes pour les programmeurs Java

• 10 livres sur les algorithmes que chaque programmeur devrait lire (liste)
• Comment mettre en œuvre l’algorithme Quicksort en Java ? (solution)
• 5 Livres pour apprendre la structure de données et les algorithmes en Java ? (livres)
• Le top 50 des programmes Java des entretiens de codage (voir ici)
• 5 Cours gratuits sur la structure de données et les algorithmes pour les programmeurs (cours)
• Comment vérifier si une chaîne est un palindrome en Java ?
• Comment trouver le nombre manquant dans un tableau trié en Java ?
• 10 livres sur les algorithmes que tout programmeur devrait lire (livres)
• 10 cours gratuits sur la structure de données et les algorithmes pour les programmeurs (cours)
• 100+ problèmes de codage de structure de données issus d’entretiens (questions)
• Comment imprimer la série de Fibonacci en Java sans utiliser la récursion ?
• Comment vérifier si un entier est une puissance de deux sans utiliser l’opérateur division ou modulo ?
• Comment trouver toutes les permutations d’une chaîne de caractères en Java ?
• Top 20 questions d’entretien sur le codage des chaînes de caractères (voir ici)
• 50+ problèmes de structure de données et d’algorithmes issus d’entretiens (questions)
• Comment supprimer un élément du tableau sans utiliser une bibliothèque tierce.bibliothèque tierce (vérifier ici)
• Comment trouver le plus grand et le plus petit nombre dans un tableau en Java (lire ici)
• Comment trouver deux nombres maximums sur un tableau d’entiers en Java (vérifier ici)