InOrder-traversal er en af de tre populære måder at gennemløbe en binær trædatastruktur på, de to andre er preOrder og postOrder. Under inorder-traversal-algoritmen udforskes først det venstre undertræ, derefter roden og til sidst knuder i det højre undertræ. Man starter traverseringen fra roden og går derefter til den venstre knude, hvorefter man igen går til den venstre knude, indtil man når en bladknude. På det tidspunkt udskriver du værdien af knuden eller markerer den som besøgt og går videre til den højre undertræ. Fortsæt den samme algoritme, indtil alle knuder i det binære træ er besøgt. InOrder-traversal er også kendt som left-node-right eller left-root-right-traversal eller LNR-traversal-algoritmen.
Som preOrder-algoritmen er det også en depth-first-algoritme, fordi den udforsker dybden af et binært træ, før den udforsker søskende. Da det er en af de grundlæggende binære træalgoritmer, er den ret populær i programmeringsinterviews.
Disse traversalgoritmer er også grundlaget for at lære mere avancerede binære træalgoritmer, og derfor bør enhver programmør lære, forstå og vide, hvordan man implementerer inOrder- og andre traversalgoritmer.
Den nemmeste måde at implementere inOrder-traversalalalgoritmen i Java eller ethvert programmeringssprog er ved at bruge rekursion. Da det binære træ er en rekursiv datastruktur, er rekursion det naturlige valg til løsning af et træbaseret problem. Metoden inOrder() i BinaryTree-klassen implementerer logikken til at travertere et binært træ ved hjælp af rekursion.
Fra Interview-synspunktet er InOrder-traversal ekstremt vigtig, fordi den også udskriver noder i et binært søgetræ i den sorterede rækkefølge, men kun hvis det givne træ er et binært søgetræ. Hvis du husker det, er værdien af noder i det venstre undertræ lavere end roden i BST, og værdierne af noder i det højre undertræ er højere end roden. In order traversal betyder bogstaveligt talt IN order dvs. at noterne udskrives i rækkefølge eller sorteret rækkefølge.
Btw, selv om disse tre algoritmer (pre-order, in-order og post-order) er populære binære trætraversal-algoritmer, men de er ikke de eneste. Du har også andre bredde-første måder at traversere et binært træ på, f.eks. level order traversal (se Datastruktur og algoritmer: Deep Dive).

Den rekursive algoritme til implementering af InOrder traversal af et binært træ

Den rekursive algoritme for inorder traversal er meget enkel. Du skal blot kalde inOrder()-metoden i BinaryTree-klassen i den rækkefølge, du ønsker at besøge træet. Det vigtigste er at medtage grundtilfældet, som er nøglen til enhver rekursiv algoritme.

For eksempel er grundtilfældet i dette problem, at du når bladknuden, og at der ikke er flere knuder at udforske, på det tidspunkt begynder rekursionen at afvikle. Her er de nøjagtige trin til at gennemgå det binære træ ved hjælp af InOrder traversal:

1. visit left node
2. print value of the root
3. visit right node

og her er kodeeksemplet til at implementere denne algoritme ved hjælp af rekursion i Java:
I lighed med preOrder()-metoden i det sidste eksempel er der en anden inOrder()-metode, som udsætter inOrder-traversal til offentligheden og kalder denne private metode, som faktisk udfører InOrder-traversal.
Dette er standardmetoden til at skrive en rekursiv metode, der tager input, det gør det nemmere for en klient at kalde metoden.

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

Du kan se, at vi starter med root og derefter rekursivt kalder inOrder()-metoden med node.left, hvilket betyder, at vi går nedad i venstre undertræ, indtil vi rammer node == null, hvilket betyder, at den sidste knude var en bladknude.
På dette tidspunkt vender inOrder()-metoden tilbage og udfører den næste linje, som udskriver node.data. Derefter er det igen et rekursivt inOrder() kald med node.right, som vil starte den samme proces igen.
Du kan også tjekke kurserne Data Structure and Algorithms Part 1 og 2 på Pluralsight for at lære mere om algoritmer og hvordan du designer dine egne algoritmer.

Btw, du skal have et Pluralsight-medlemskab for at få adgang til dette kursus, som koster omkring 29 dollars om måneden eller 299 dollars årligt (14% besparelse). Jeg har et, og jeg foreslår også, at alle udviklere har det abonnement, fordi Pluralsight er som NetFlix for softwareudviklere.
Det har mere end 5000+ kurser af god kvalitet om alle de nyeste emner. Da vi programmører skal lære nye ting hver dag, er en investering på 299 USD ikke dårligt.
Btw, det tilbyder også en 10-dages gratis prøveperiode uden nogen forpligtelse, som giver dig mulighed for at se 200 timers indhold. Du kan se disse kurser gratis ved at tilmelde dig denne 10-dages gratis prøveperiode.

Java-program til implementering af InOrder traversal af et binært træ

Her er vores komplette løsning til InOrder traversal-algoritmen i Java. Dette program bruger en rekursiv algoritme til at udskrive værdien af alle knuder i et binært træ ved hjælp af InOrder traversal.
Som jeg har fortalt før, udskrives under in-order traversal værdien af venstre undertræ først, efterfulgt af rod og højre undertræ. Hvis du er interesseret i den iterative algoritme, kan du yderligere tjekke denne tutorial om implementering af inOrder traversal uden rekursion.

Det er alt om, hvordan man implementerer inOrder traversal af et binært træ i Java ved hjælp af rekursion. Du kan se, at koden er temmelig meget lig preOrder traversal med den eneste forskel i den rækkefølge, vi rekursivt kalder metoden. I dette tilfælde kalder vi inOrder(node.left) først og udskriver derefter værdien af knuden.
Det er værd at huske, at inOrder-traversal er en dybdeførste algoritme og udskriver træets knude i sorteret rækkefølge, hvis det givne binære træ er et binært søgetræ.
I næste del af denne artikel vil jeg dele inOrder traversal uden rekursion, i mellemtiden kan du prøve at øve dig i følgende datastruktur- og binære træproblemer.
Videregående læring
Datastrukturer og algoritmer: Deep Dive Using Java
Algoritms 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 Programmers

• 10 Algorithm books Every Programmer Should Read (list)
• Hvordan implementerer man Quicksort-algoritmen i Java? (løsning)
• 5 bøger til at lære datastruktur og algoritmer i Java? (bøger)
• Top 50 Java-programmer fra Coding Interviews (se her)
• 5 gratis kurser i datastruktur og algoritmer for programmører (kurser)
• Hvordan tjekker man, om en streng er et palindrom i Java?
• Hvordan finder man det manglende tal i et sorteret array i Java?
• 10 algoritmebøger, som enhver programmør bør læse (bøger)
• 10 gratis datastruktur- og algoritmekurser for programmører (kurser)
• 100+ Datastrukturkodningsproblemer fra interviews (spørgsmål)
• Hvordan udskriver man Fibonacci-serien i Java uden at bruge rekursion?
• Hvordan kan man kontrollere, om et heltal er en potens af to uden at bruge division eller modulo-operatoren?
• Hvordan finder man alle permutationer af String i Java?
• Top 20 String kodning interview spørgsmål (se her)
• 50+ Datastruktur og Algoritmer Problemer fra interviews (spørgsmål)
• Hvordan man fjerner et element fra arrayet uden at bruge en tredje-party library (check her)
• Sådan finder du det største og mindste tal i et array i Java (læs her)
• Sådan finder du to maksimale tal på heltal array i Java (check her)