InOrder-traversal är ett av de tre populära sätten att traversera en binär träddatastruktur, de andra två är preOrder och postOrder. Under algoritmen In Order Traversal utforskas först det vänstra delträdet, följt av roten och slutligen noderna i det högra delträdet. Du börjar traversera från roten och går sedan till den vänstra noden, sedan återigen till den vänstra noden tills du når en bladnod. Vid den tidpunkten skriver du ut nodens värde eller markerar den som besökt och flyttar till det högra delträdet. Fortsätt samma algoritm tills alla noder i det binära trädet har besökts. InOrder-traversalen är också känd som vänster-nod-höger- eller vänster-rot-höger-traversal eller LNR-traversal-algoritmen.
Likt preOrder-algoritmen är det också en djup-först-algoritm eftersom den utforskar djupet av ett binärt träd innan den utforskar syskon. Eftersom det är en av de grundläggande binära trädalgoritmerna är den ganska populär i programmeringsintervjuer.
Dessa traversalgoritmer är också grunden för att lära sig mer avancerade binära trädalgoritmer, därför bör varje programmerare lära sig, förstå och veta hur man implementerar inOrder- och andra traversalgoritmer.
Det enklaste sättet att implementera inOrder-traversalalalgoritmen i Java eller något annat programmeringsspråk är genom att använda rekursion. Eftersom det binära trädet är en rekursiv datastruktur är rekursion det naturliga valet för att lösa ett trädbaserat problem. Metoden inOrder() i klassen BinaryTree implementerar logiken för att traversera ett binärt träd med hjälp av rekursion.
Från intervjuns synvinkel är InOrder-traversal ytterst viktig eftersom den också skriver ut noder i ett binärt sökträd i sorterad ordning, men bara om det givna trädet är ett binärt sökträd. Om du kommer ihåg att i BST är värdet av noderna i det vänstra delträdet lägre än roten och värdet av noderna i det högra delträdet är högre än roten. In order traversal betyder bokstavligen IN order dvs. noterna skrivs ut i ordning eller sorterad ordning.
Btw, även om dessa tre algoritmer (pre-order, in-order och post-order) är populära algoritmer för binär trädtraversal men de är inte de enda. Det finns även andra sätt att genomkorsa ett binärt träd, t.ex. level order traversal (se Data Structure and Algorithms: Deep Dive).

Den rekursiva algoritmen för att implementera InOrder traversal av ett binärt träd

Den rekursiva algoritmen för inorder traversal är mycket enkel. Du behöver bara anropa inOrder()-metoden i klassen BinaryTree i den ordning du vill besöka trädet. Det viktigaste är att inkludera basfallet, vilket är nyckeln till alla rekursiva algoritmer.

I det här problemet är basfallet till exempel att du når bladknuten och att det inte finns någon mer nod att utforska, vid den tidpunkten börjar rekursionen att avvecklas. Här är de exakta stegen för att genomkorsa det binära trädet med hjälp av InOrder traversal:

1. besök vänster nod
2. utskrift av rotvärdet
3. besök höger nod

och här är exempelkoden för att implementera den här algoritmen med hjälp av rekursion i Java:
Som liknar preOrder()-metoden i det senaste exemplet finns det ytterligare en inOrder()-metod som exponerar InOrder-traversal för allmänheten och anropar denna privata metod som faktiskt utför InOrder-traversal.
Detta är standardsättet att skriva en rekursiv metod som tar emot indata, det gör det lättare för en klient att anropa metoden.

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

Du kan se att vi börjar med root och sedan rekursivt anropar inOrder() metoden med node.left, vilket innebär att vi går nedåt i det vänstra delträdet tills vi träffar node == null, vilket innebär att den sista noden var en bladnod.
I det här läget kommer inOrder()-metoden att återvända och exekvera nästa rad, som skriver ut node.data. Efter det är det återigen ett rekursivt inOrder()-anrop med node.right, vilket kommer att initiera samma process igen.
Du kan också kolla in Data Structure and Algorithms Part 1 och 2-kurserna på Pluralsight för att lära dig mer om algoritmer och hur du designar dina egna algoritmer.

I övrigt behöver du ett medlemskap i Pluralsight för att få tillgång till den här kursen, vilket kostar cirka 29 dollar per månad eller 299 dollar per år (14 % besparing). Jag har ett och jag föreslår också att alla utvecklare har den planen eftersom Pluralsight är som NetFlix för mjukvaruutvecklare.
Det har mer än 5000+ kurser av god kvalitet om alla de senaste ämnena. Eftersom vi programmerare måste lära oss nya saker varje dag är en investering på $299 USD inte dålig.
Btw, det erbjuder också en 10-dagars gratis provperiod utan några förpliktelser som gör att du kan titta på 200 timmars innehåll. Du kan titta på dessa kurser gratis genom att registrera dig för denna 10-dagars gratis provperiod.

Java-program för att implementera InOrder traversal of a Binary tree

Här är vår kompletta lösning för inorder traversal-algoritmen i Java. Det här programmet använder en rekursiv algoritm för att skriva ut värdet av alla noder i ett binärt träd med hjälp av InOrder traversal.
Som jag har berättat tidigare skrivs värdet av det vänstra delträdet ut först under InOrder traversal, följt av roten och det högra delträdet. Om du är intresserad av den iterativa algoritmen kan du kolla vidare på den här handledningen för att implementera inOrder traversal utan rekursion.

Det är allt om hur man implementerar inOrder traversal av ett binärt träd i Java med hjälp av rekursion. Du kan se att koden är ganska lik den preOrder traversal med den enda skillnaden i den ordning vi rekursivt anropar metoden. I det här fallet kallar vi inOrder(node.left) först och skriver sedan ut nodens värde.
Det är värt att komma ihåg att inOrder traversal är en djupgående algoritm och skriver ut trädets noder i sorterad ordning om det givna binära trädet är ett binärt sökträd.
I nästa del av den här artikeln kommer jag att dela med mig av inOrder traversal utan rekursion, under tiden kan du prova att öva följande problem med datastrukturer och binära träd.
Fortsatt lärande
Datastrukturer och algoritmer: 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
Other data structure and algorithms tutorials for Java Programmer

• 10 Algorithm books Every Programmer Should Read (list)
• Hur implementerar man Quicksort-algoritmen i Java? (lösning)
• 5 böcker för att lära sig datastruktur och algoritmer i Java? (böcker)
• Top 50 Java-program från kodningsintervjuer (se här)
• 5 kostnadsfria kurser i datastruktur och algoritmer för programmerare (kurser)
• Hur kontrollerar man om en sträng är en palindrom i Java?
• Hur hittar man det felande numret i en sorterad matris i Java?
• 10 algoritmböcker som varje programmerare bör läsa (böcker)
• 10 kostnadsfria kurser i datastruktur och algoritmer för programmerare (kurser)
• 100+ Kodningsproblem för datastruktur från intervjuer (frågor)
• Hur skriver man ut Fibonacci-serien i Java utan att använda rekursion?
• Hur kontrollerar man om ett heltal är en potens av två utan att använda division eller modulo-operatorn?
• Hur hittar man alla permutationer av String i Java?
• Top 20 intervjufrågor om strängkodning (se här)
• 50+ Problem med datastruktur och algoritmer från intervjuer (frågor)
• Hur tar man bort ett element från matrisen utan att använda en tredje-party library (check here)
• Hur man hittar det största och minsta talet i en array i Java (läs här)
• Hur man hittar två maximala tal på heltalsarray i Java (check here)