Die InOrder traversal ist eine der drei beliebten Möglichkeiten, eine binäre Baumdatenstruktur zu durchlaufen, die anderen beiden sind die preOrder und postOrder. Beim InOrder-Traversal-Algorithmus wird zuerst der linke Teilbaum, dann die Wurzel und schließlich die Knoten des rechten Teilbaums durchsucht. Sie beginnen mit dem Traversal von der Wurzel, gehen dann zum linken Knoten, dann wieder zum linken Knoten, bis Sie einen Blattknoten erreichen. Zu diesem Zeitpunkt geben Sie den Wert des Knotens aus oder markieren ihn als besucht und wechseln zum rechten Teilbaum. Der gleiche Algorithmus wird fortgesetzt, bis alle Knoten des Binärbaums besucht sind. Der InOrder-Traversal-Algorithmus ist auch als Links-Knoten-Rechts- oder Links-Wurzel-Rechts-Traversal-Algorithmus oder LNR-Traversal-Algorithmus bekannt.
Ähnlich wie der preOrder-Algorithmus ist auch er ein depth-first-Algorithmus, da er die Tiefe eines Binärbaums untersucht, bevor er die Geschwister untersucht. Da es sich um einen der grundlegenden Binärbaum-Algorithmen handelt, ist er in Programmiergesprächen sehr beliebt.
Diese Traversal-Algorithmen sind auch die Grundlage, um fortgeschrittenere Binärbaum-Algorithmen zu erlernen, daher sollte jeder Programmierer lernen, verstehen und wissen, wie man inOrder und andere Traversal-Algorithmen implementiert.
Der einfachste Weg, den inOrder-Traversal-Algorithmus in Java oder einer anderen Programmiersprache zu implementieren, ist die Verwendung von Rekursion. Da der Binärbaum eine rekursive Datenstruktur ist, ist die Rekursion die natürliche Wahl für die Lösung eines baumbasierten Problems. Die Methode inOrder() in der Klasse BinaryTree implementiert die Logik zur Durchquerung eines Binärbaums mit Hilfe von Rekursion.
Aus Sicht des Interviews ist die InOrder-Traversierung äußerst wichtig, da sie auch die Knoten eines binären Suchbaums in sortierter Reihenfolge ausgibt, allerdings nur, wenn der gegebene Baum ein binärer Suchbaum ist. Wie Sie sich erinnern, sind in einem BST die Werte der Knoten im linken Teilbaum niedriger als die der Wurzel und die Werte der Knoten im rechten Teilbaum höher als die der Wurzel. In order traversal bedeutet wörtlich IN order, d.h. die Noten werden in der Reihenfolge oder sortiert ausgegeben.
Btw, auch wenn diese drei Algorithmen (pre-order, in-order und post-order) populäre binäre Baumtraversal-Algorithmen sind, sind sie nicht die einzigen. Es gibt auch andere Möglichkeiten, einen Binärbaum zu traversieren, z.B. Level-Order-Traversal (siehe Datenstruktur und Algorithmen: Deep Dive).

Der rekursive Algorithmus zur Implementierung von InOrder-Traversal eines Binärbaums

Der rekursive Algorithmus von Inorder-Traversal ist sehr einfach. Man braucht nur die Methode inOrder() der Klasse BinaryTree in der Reihenfolge aufzurufen, in der man den Baum besuchen will. Das Wichtigste ist, den Basisfall einzubeziehen, der der Schlüssel zu jedem rekursiven Algorithmus ist.
In diesem Problem zum Beispiel ist der Basisfall, dass Sie den Blattknoten erreichen und es keinen weiteren Knoten mehr zu erforschen gibt, an diesem Punkt beginnt die Rekursion zu enden. Hier sind die genauen Schritte, um den Binärbaum mit Hilfe von InOrder Traversal zu durchlaufen:

1. Besuch des linken Knotens
2. Drucke Wert der Wurzel
3. Besuch des rechten Knotens

und hier ist der Beispielcode, um diesen Algorithmus mit Hilfe von Rekursion in Java zu implementieren:
Ähnlich wie die preOrder()-Methode im letzten Beispiel gibt es eine weitere inOrder()-Methode, die den InOrder-Traversal öffentlich macht und diese private Methode aufruft, die den InOrder-Traversal tatsächlich durchführt.
Dies ist der Standardweg, um eine rekursive Methode zu schreiben, die Eingaben annimmt, es macht es einfacher für einen Client, die Methode aufzurufen.

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

Sie können sehen, dass wir mit root beginnen und dann rekursiv die inOrder() Methode mit node aufrufen.left, was bedeutet, dass wir im linken Teilbaum nach unten gehen, bis wir auf node == null stoßen, was bedeutet, dass der letzte Knoten ein Blattknoten war.
Zu diesem Zeitpunkt kehrt die Methode inOrder() zurück und führt die nächste Zeile aus, die die node.data ausgibt. Danach folgt wieder ein rekursiver inOrder()-Aufruf mit node.right, der den gleichen Prozess erneut auslöst.
Sie können sich auch die Kurse Data Structure and Algorithms Part 1 und 2 auf Pluralsight ansehen, um mehr über Algorithmen zu erfahren und zu lernen, wie Sie Ihre eigenen Algorithmen entwerfen können.

Btw, Sie bräuchten eine Pluralsight-Mitgliedschaft, um auf diesen Kurs zuzugreifen, die etwa 29$ monatlich oder 299$ jährlich (14% Ersparnis) kostet. Ich habe eine solche Mitgliedschaft, und ich empfehle sie auch allen Entwicklern, denn Pluralsight ist wie NetFlix für Softwareentwickler.
Es gibt mehr als 5000+ qualitativ hochwertige Kurse zu allen aktuellen Themen. Da wir Programmierer jeden Tag neue Dinge lernen müssen, ist eine Investition von 299 USD nicht schlecht.
Übrigens bietet Pluralsight auch eine 10-tägige kostenlose und unverbindliche Testversion an, mit der Sie 200 Stunden an Inhalten ansehen können. Sie können diese Kurse kostenlos ansehen, indem Sie sich für die 10-tägige kostenlose Testversion anmelden.

Java-Programm zur Implementierung von InOrder-Traversal eines Binärbaums

Hier ist unsere vollständige Lösung für den InOrder-Traversal-Algorithmus in Java. Dieses Programm verwendet einen rekursiven Algorithmus, um den Wert aller Knoten eines Binärbaums mit Hilfe von InOrder Traversal zu drucken.
Wie ich Ihnen bereits gesagt habe, wird während der InOrder Traversal zuerst der Wert des linken Teilbaums gedruckt, gefolgt von der Wurzel und dem rechten Teilbaum. Wenn Sie sich für den iterativen Algorithmus interessieren, können Sie sich dieses Tutorial über die Implementierung von inOrder Traversal ohne Rekursion ansehen.
Das ist alles darüber, wie man inOrder Traversal eines Binärbaums in Java mit Rekursion implementiert. Wie Sie sehen können, ist der Code dem preOrder-Traversal ziemlich ähnlich, mit dem einzigen Unterschied in der Reihenfolge, in der wir die Methode rekursiv aufrufen. In diesem Fall rufen wir zuerst inOrder(node.left) auf und geben dann den Wert des Knotens aus.
Es sei daran erinnert, dass inOrder Traversal ein depth-first Algorithmus ist und die Baumknoten in sortierter Reihenfolge ausgibt, wenn der gegebene binäre Baum ein binärer Suchbaum ist.
Im nächsten Teil dieses Artikels werde ich inOrder Traversal ohne Rekursion teilen, in der Zwischenzeit können Sie versuchen, folgende Datenstruktur- und Binärbaumprobleme zu üben.
Weiteres Lernen
Datenstrukturen und Algorithmen: Deep Dive Using Java
Algorithmen und Datenstrukturen – Teil 1 und 2
Datenstrukturen in Java 9 von Heinz Kabutz
Cracking the Coding Interview – 189 Fragen und Lösungen
Grokking the Coding Interview: Patterns for Coding Questions
Weitere Datenstruktur- und Algorithmus-Tutorials für Java-Programmierer

• 10 Algorithmus-Bücher, die jeder Programmierer lesen sollte (Liste)
• Wie implementiert man den Quicksort-Algorithmus in Java? (Lösung)
• 5 Bücher zum Erlernen von Datenstrukturen und Algorithmen in Java? (Bücher)
• Top 50 Java-Programme von Coding Interviews (siehe hier)
• 5 kostenlose Kurse zu Datenstruktur und Algorithmen für Programmierer (Kurse)
• Wie prüft man in Java, ob ein String ein Palindrom ist?
• Wie findet man die fehlende Zahl in einem sortierten Array in Java?
• 10 Algorithmus-Bücher, die jeder Programmierer lesen sollte (Bücher)
• 10 kostenlose Datenstruktur- und Algorithmus-Kurse für Programmierer (Kurse)
• 100+ Datenstruktur-Codierprobleme aus Interviews (Fragen)
• Wie druckt man die Fibonacci-Reihe in Java ohne Rekursion?
• Wie prüft man, ob eine ganze Zahl eine Potenz von zwei ist, ohne Division oder Modulo-Operator zu verwenden?
• Wie findet man alle Permutationen von String in Java?
• Top 20 String coding interview questions (see here)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• How to remove an element from the array without using a third- party library (check here)
• Wie entfernt man ein Element aus einem Array ohne eineparty library (check here)
• Wie findet man die größte und kleinste Zahl in einem Array in Java (read here)
• Wie findet man zwei maximale Zahlen in einem Integer-Array in Java (check here)