De InOrder traversal is een van de drie populaire manieren om een binaire boom datastructuur te doorkruisen, de andere twee zijn de preOrder en postOrder. Tijdens het in-orde traversal algoritme, wordt eerst de linker subtree verkend, gevolgd door de root, en tenslotte de nodes in de rechter subtree. Je begint de traversal vanaf de root, gaat dan naar de linkerknoop, en gaat dan weer naar de linkerknoop tot je een bladknoop bereikt. Op dat moment drukt u de waarde van de node af of markeert u deze bezocht en gaat u naar de rechter subtree. Ga zo door met hetzelfde algoritme totdat alle nodes van de binaire boom zijn bezocht. De InOrder traversal is ook bekend als de left-node-right of left-root-right traversal of LNR traversal algoritme.
Gelijk aan het preOrder algoritme, is het ook een depth-first algoritme omdat het de diepte van een binaire boom verkent voordat het broers en zussen verkent. Aangezien het een van de fundamentele binaire boom algoritmen is het vrij populair in het programmeren interviews.
Deze traversal algoritmen zijn ook de basis om meer geavanceerde binaire boom algoritmen te leren, vandaar dat elke programmeur zou moeten leren, begrijpen, en weten hoe in-order en andere traversal algoritmen te implementeren.
De eenvoudigste manier om de inOrder traversal algoritme in Java of een programmeertaal te implementeren is door gebruik te maken van recursie. Aangezien de binaire boom een recursieve gegevensstructuur is, is recursie de natuurlijke keuze voor het oplossen van een boom-gebaseerd probleem. De inOrder() methode in de BinaryTree klasse implementeert de logica om een binaire boom te doorkruisen met behulp van recursie.
Vanuit het oogpunt van Interview is InOrder traversal uiterst belangrijk omdat het ook knooppunten van een binaire zoekboom in de gesorteerde volgorde afdrukt, maar alleen als de gegeven boom een binaire zoekboom is. Zoals u zich herinnert, is in BST de waarde van knooppunten in de linker subboom lager dan de wortel, en de waarden van knooppunten in de rechter subboom zijn hoger dan de wortel. De In order traversal betekent letterlijk IN volgorde, d.w.z. de noten worden afgedrukt in de volgorde of gesorteerde volgorde.
Btw, ook al zijn deze drie algoritmen (pre-order, in-order, en post-order) populaire binaire boom traversal algoritmen, maar ze zijn niet de enige. Er zijn ook andere breadth-first manieren om een binaire boom te doorkruisen, bijv. level order traversal (zie Data Structure and Algorithms: Deep Dive).

Het recursieve algoritme om InOrder traversal van een binaire boom te implementeren

Het recursieve algoritme van inorder traversal is heel eenvoudig. Je hoeft alleen maar de inOrder() methode van de BinaryTree klasse aan te roepen in de volgorde waarin je de boom wilt bezoeken. Het belangrijkste is om het basisgeval op te nemen, dat de sleutel is tot elk recursief algoritme.
Bij voorbeeld, in dit probleem, is het basisgeval dat je het bladknooppunt bereikt en er is geen knooppunt meer om te verkennen, op dat moment begint de recursie af te lopen. Hier zijn de exacte stappen om de binaire boom te doorkruisen met behulp van InOrder traversal:

1. bezoek linkerknooppunt
2. print waarde van de wortel
3. bezoek rechterknooppunt

en hier is de voorbeeldcode om dit algoritme met behulp van recursie in Java uit te voeren:
Gelijk aan de preOrder() methode in het laatste voorbeeld, is er nog een inOrder() methode die inorder traversal blootstelt aan het publiek en deze private methode aanroept die daadwerkelijk de InOrder traversal uitvoert.
Dit is de standaard manier om een recursieve methode te schrijven die input neemt, het maakt het makkelijker voor een client om de methode aan te roepen.

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

Je kunt zien dat we beginnen met root en dan recursief de inOrder() methode aanroepen met node.left, wat betekent dat we naar beneden gaan op de linker subtree totdat we node == null tegenkomen, wat betekent dat de laatste node een leaf node was.
Op dit punt in de tijd zal de inOrder() methode terugkeren en de volgende regel uitvoeren, die de node.data afdrukt. Daarna wordt opnieuw inOrder() aangeroepen met node.right, waarmee hetzelfde proces opnieuw wordt gestart.
Je kunt ook de cursussen Data Structure and Algorithms Part 1 en 2 op Pluralsight bekijken om meer te leren over algoritmen en hoe je je eigen algoritmen kunt ontwerpen.

Btw, je hebt een Pluralsight-lidmaatschap nodig om toegang te krijgen tot deze cursus, die ongeveer $29 per maand of $299 per jaar kost (14% besparing). Ik heb er een en ik raad alle ontwikkelaars aan om er een te nemen, want Pluralsight is als NetFlix voor softwareontwikkelaars.
Het heeft meer dan 5000+ cursussen van goede kwaliteit over alle nieuwste onderwerpen. Aangezien wij programmeurs elke dag nieuwe dingen moeten leren, is een investering van $ 299 USD niet slecht.
Btw, het biedt ook een 10-daagse gratis proefversie zonder enige verplichting waarmee je 200 uur aan inhoud kunt bekijken. U kunt deze cursussen gratis bekijken door u aan te melden voor die gratis proefperiode van 10 dagen.

Java-programma om InOrder-traversal van een binaire boom te implementeren

Hier is onze complete oplossing voor het inOrder-traversal-algoritme in Java. Dit programma gebruikt een recursief algoritme om de waarde van alle knooppunten van een binaire boom af te drukken met behulp van InOrder traversal.
Zoals ik je al eerder heb verteld, wordt tijdens de in-order traversal eerst de waarde van de linker subtree afgedrukt, gevolgd door de root en de rechter subtree. Als je geïnteresseerd bent in het iteratieve algoritme, kun je verder kijken naar deze tutorial over het implementeren van in order traversal zonder recursie.
Dat is alles over hoe je inOrder traversal van een binaire boom in Java implementeert met behulp van recursie. U kunt zien dat de code is vrijwel vergelijkbaar met de preOrder traversal met het enige verschil in de volgorde waarin we recursief roepen de methode. In dit geval roepen we eerst inOrder(node.left) aan en drukken dan de waarde van de node af.
Het is de moeite waard om te onthouden dat in order traversal een depth-first algoritme is en boomknopen in gesorteerde volgorde afdrukt als de gegeven binaire boom een binaire zoekboom is.
In het volgende deel van dit artikel, zal ik delen inOrder traversal zonder recursie, ondertussen, kunt u proberen het beoefenen van de volgende data structuur en binaire boom problemen.
Verder leren
Data Structuren en Algoritmen: Deep Dive Using Java
Algorithms and Data Structures – Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz
Cracking the Coding Interview – 189 Questions and Solutions
Grokking the Coding Interview: Patterns for Coding Questions
Andere tutorials over datastructuren en algoritmen voor Java-programmeurs

• 10 Algoritme-boeken die elke programmeur zou moeten lezen (lijst)
• Hoe implementeer je het Quicksort-algoritme in Java? (oplossing)
• 5 Boeken om datastructuur en algoritmen in Java te leren? (boeken)
• Top 50 Java-programma’s van Coding Interviews (zie hier)
• 5 Gratis Data Structuur en Algoritmen cursussen voor programmeurs (cursussen)
• Hoe om te controleren of een String is een Palindroom in Java?
• Hoe vind je het ontbrekende getal in een gesorteerde array in Java?
• 10 Algoritmen Boeken Elke Programmeur moet lezen (boeken)
• 10 Gratis Data Structuur en Algoritme Cursussen voor Programmeurs (cursussen)
• 100 + Data Structuur Codering Problemen uit Interviews (vragen)
• Hoe de Fibonacci serie in Java af te drukken zonder gebruik te maken Recursie?
• Hoe om te controleren of een geheel getal is een macht van twee zonder gebruik van deling of modulo operator?
• Hoe alle permutatie van String vinden in Java?
• Top 20 String codering interview vragen (bekijk hier)
• 50+ Data Structuur en Algoritmen Problemen van Interviews (vragen)
• Hoe verwijder je een element uit de array zonder gebruik te maken van een third-partij bibliotheek (controleer hier)
• Hoe vind je het grootste en kleinste getal in een array in Java (lees hier)
• Hoe vind je twee maximum aantal op integer array in Java (controleer hier)