Az InOrder traversal egyike a bináris fa adatszerkezetek átjárásának három népszerű módjának, a másik kettő a preOrder és a postOrder. Az in-order traversal algoritmus során először a bal oldali részfa, majd a gyökér, végül a jobb oldali részfa csomópontjai kerülnek feltárásra. A traverzálást a gyökérből kezdjük, majd a bal oldali csomópontra megyünk, majd ismét a bal oldali csomópontra, amíg el nem érünk egy levélcsomópontot. Ekkor kiírja a csomópont értékét, vagy megjelöli a meglátogatott csomópontot, és a jobb részfára lép. Folytatja ugyanezt az algoritmust, amíg a bináris fa összes csomópontját meg nem látogatja. Az InOrder traverzálást bal-csomópont-jobb vagy bal-gyökér-jobb traverzálási vagy LNR traverzálási algoritmusnak is nevezik.
A preOrder algoritmushoz hasonlóan ez is egy mélység-első algoritmus, mivel a bináris fa mélységét vizsgálja meg, mielőtt a testvéreket vizsgálná meg. Mivel ez az egyik alapvető bináris fa algoritmus, elég népszerű a programozási interjúkban.
Ezek a traverzálási algoritmusok képezik az alapját a fejlettebb bináris fa algoritmusok elsajátításának is, ezért minden programozónak meg kell tanulnia, meg kell értenie és tudnia kell, hogyan kell az inOrder és más traverzálási algoritmusokat megvalósítani.
Az inOrder traverzálási algoritmus Java-ban vagy bármely programozási nyelven történő megvalósításának legegyszerűbb módja a rekurzió használata. Mivel a bináris fa egy rekurzív adatszerkezet, a rekurzió a természetes választás egy fa alapú probléma megoldására. A BinaryTree osztály inOrder() metódusa valósítja meg a bináris fa rekurzióval történő átjárásának logikáját.
Az InOrder átjárás az Interjú szempontjából rendkívül fontos, mert a bináris keresőfa csomópontjait is rendezett sorrendben írja ki, de csak akkor, ha az adott fa bináris keresőfa. Ha emlékszel, a BST-ben a bal oldali részfa csomópontjainak értéke alacsonyabb, mint a gyökéré, a jobb oldali részfa csomópontjainak értéke pedig magasabb, mint a gyökéré. Az In order traversal szó szerint azt jelenti, hogy IN order, azaz a jegyzetek sorrendben vagy rendezett sorrendben kerülnek kiírásra.
Btw, bár ez a három algoritmus (pre-order, in-order és post-order) népszerű bináris fa traversal algoritmusok, de nem ezek az egyetlenek. A bináris fa átszelésének más, szélesség szerinti módjai is vannak, pl. a level order traversal (lásd Adatszerkezet és algoritmusok: Mélymerülés).

A bináris fa InOrder átszelésének megvalósítására szolgáló rekurzív algoritmus

A inorder traversal rekurzív algoritmusa nagyon egyszerű. Csak meg kell hívnunk a BinaryTree osztály inOrder() metódusát abban a sorrendben, ahogyan a fát szeretnénk bejárni. Ami a legfontosabb, az az alapeset, ami minden rekurzív algoritmus kulcsa.

Ez a probléma esetében például az alapeset az, hogy elérjük a levélcsomópontot, és nincs több felfedezésre váró csomópont, ekkor a rekurzió elkezdődik. Íme a bináris fa InOrder traversal segítségével történő bejárásának pontos lépései:

1. látogassuk meg a bal oldali csomópontot
2. nyomtassuk ki a gyökér értékét
3. látogassuk meg a jobb oldali csomópontot

és itt van a mintakód ennek az algoritmusnak a rekurzióval történő megvalósításához Java nyelven:
Az előző példában szereplő preOrder() metódushoz hasonlóan van egy másik inOrder() metódus, amely az inorder traversal-t a nyilvánosság elé tárja, és meghívja ezt a privát metódust, amely ténylegesen végrehajtja az InOrder traversal-t.
Ez a szokásos módja egy rekurzív metódus megírásának, amely bemenetet fogad, megkönnyíti a kliens számára a metódus meghívását.

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

Láthatjuk, hogy a gyökérrel kezdünk, majd rekurzívan meghívjuk az inOrder() metódust a node-dal.left, ami azt jelenti, hogy a bal oldali részfán haladunk lefelé, amíg el nem érjük, hogy node == null, ami azt jelenti, hogy az utolsó csomópont egy levélcsomópont volt.
Az inOrder() metódus ekkor visszatér és végrehajtja a következő sort, ami kiírja a node.data. Ezután ismét rekurzív inOrder() hívás következik a node.right-val, ami újra elindítja ugyanezt a folyamatot.
A Pluralsighton megtekintheti az Adatstruktúra és algoritmusok 1. és 2. rész tanfolyamokat is, ha többet szeretne megtudni az algoritmusokról és arról, hogyan tervezhet saját algoritmusokat.

A tanfolyam eléréséhez egyébként Pluralsight-tagságra lenne szüksége, ami körülbelül 29 $ havonta vagy 299 $ évente (14% megtakarítás). Nekem van ilyenem, és minden fejlesztőnek is javaslom, hogy legyen ilyen tervem, mert a Pluralsight olyan, mint a NetFlix a szoftverfejlesztők számára.
Több mint 5000+ jó minőségű tanfolyamot tartalmaz az összes legújabb témában. Mivel nekünk, programozóknak minden nap új dolgokat kell tanulnunk, egy 299 dolláros befektetés nem rossz.
Mellesleg 10 napos ingyenes próbaidőszakot is kínál minden kötelezettség nélkül, amely lehetővé teszi 200 órányi tartalom megtekintését. Ezeket a tanfolyamokat ingyenesen megnézheted, ha regisztrálsz erre a 10 napos ingyenes próbaverzióra.

Java program egy bináris fa InOrder traversaljának megvalósítására

Itt a teljes megoldásunk az inorder traversal algoritmusra Java nyelven. Ez a program egy rekurzív algoritmust használ egy bináris fa összes csomópontjának értékének kiírására az InOrder traversal segítségével.
Mint azt már korábban elmondtam, az in-order traversal során először a bal oldali részfa értéke kerül kiírásra, majd a gyökér és a jobb oldali részfa. Ha érdekli az iteratív algoritmus, akkor tovább nézze meg ezt a bemutatót az in order traversal rekurzió nélküli megvalósításáról.

Ez minden arról, hogyan lehet egy bináris fa inOrder traversalját rekurzióval Java-ban megvalósítani. Láthatjuk, hogy a kód nagyjából hasonló a preOrder traversalhoz, az egyetlen különbség a sorrendben van, amelyben rekurzívan hívjuk a módszert. Ebben az esetben először meghívjuk az inOrder(node.left) algoritmust, majd kiírjuk a csomópont értékét.
Érdemes megjegyezni, hogy az in order traversal egy depth-first algoritmus, és a fa csomópontjait rendezett sorrendben írja ki, ha az adott bináris fa egy bináris keresőfa.
A cikk következő részében a rekurzió nélküli inOrder traversal-t fogom megosztani, addig is megpróbálhatod gyakorolni a következő adatszerkezeti és bináris fa feladatokat.
Továbbtanulás
Adatszerkezetek és algoritmusok: 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 kérdés és megoldás
Grokking the Coding Interview: Patterns for Coding Questions
Other data structure and algorithms tutorials for Java Programmers

• 10 Algorithm books Every Programmer Should Read (list)
• How to implement the Quicksort algorithm in Java? (megoldás)
• 5 könyv adatszerkezet és algoritmusok tanulására Java nyelven? (könyvek)
• Top 50 Java program a Kódolási interjúkból (lásd itt)
• 5 ingyenes adatszerkezeti és algoritmus tanfolyam programozóknak (tanfolyamok)
• Hogyan lehet ellenőrizni, hogy egy karakterlánc palindrom-e Java-ban?
• Hogyan keressük meg a hiányzó számot egy rendezett tömbben Java-ban?
• 10 Algoritmus könyv, amit minden programozónak el kell olvasnia (könyvek)
• 10 ingyenes adatszerkezeti és algoritmus tanfolyam programozóknak (tanfolyamok)
• 100+ adatszerkezeti kódolási probléma interjúkból (kérdések)
• Hogyan nyomtassuk ki a Fibonacci sorozatot Java-ban rekurzió használata nélkül?
• Hogyan lehet ellenőrizni, hogy egy egész szám kettő hatványa-e osztás vagy modulo operátor használata nélkül?
• Hogyan lehet megtalálni a String összes permutációját Javában?
• Top 20 string kódolással kapcsolatos interjúkérdés (lásd itt)
• 50+ adatszerkezeti és algoritmus-probléma interjúkról (kérdések)
• Hogyan lehet eltávolítani egy elemet a tömbből anélkül, hogy egy harmadik…party könyvtár nélkül (nézd meg itt)
• Hogyan találjuk meg a legnagyobb és a legkisebb számot egy tömbben Java-ban (olvasd el itt)
• Hogyan találjunk két maximális számot egész szám tömbben Java-ban (nézd meg itt)