InOrder-kulkeminen on yksi kolmesta suositusta tavasta kulkea binääripuun tietorakennetta, kaksi muuta ovat preOrder ja postOrder. In-order-traversaalialgoritmin aikana tutkitaan ensin vasen alipuu, sitten juuri ja lopuksi oikean alipuun solmut. Läpikäynti aloitetaan juuresta, sitten siirrytään vasempaan solmuun, sitten taas vasempaan solmuun, kunnes päästään lehtisolmuun. Siinä vaiheessa tulostetaan solmun arvo tai merkitään se vierailuksi ja siirrytään oikeaan alipuuhun. Jatketaan samaa algoritmia, kunnes kaikki binääripuun solmut on käyty läpi. InOrder-traversaali tunnetaan myös nimellä left-node-right- tai left-root-right-traversaali tai LNR-traversaalialgoritmi.
Samankaltainen kuin preOrder-algoritmi, se on myös depth-first-algoritmi, koska se tutkii binääripuun syvyyden ennen sisarusten tutkimista. Koska se on yksi perustavanlaatuisista binääripuualgoritmeista, se on melko suosittu ohjelmointihaastatteluissa.
Nämä traversaalialgoritmit ovat myös perusta edistyneempien binääripuualgoritmien oppimiselle, joten jokaisen ohjelmoijan tulisi oppia, ymmärtää ja osata toteuttaa inOrder- ja muita traversaalialgoritmeja.
Helpoisin tapa toteuttaa inOrder-traversaalialgoritmi Javassa tai millä tahansa muullakin ohjelmointikielellä on rekursiota käyttämällä. Koska binääripuu on rekursiivinen tietorakenne, rekursio on luonnollinen valinta puupohjaisen ongelman ratkaisemiseen. BinaryTree-luokan inOrder()-metodi toteuttaa logiikan binääripuun läpikäymiseen rekursiota käyttäen.
Haastattelun kannalta InOrder-läpikäyminen on äärimmäisen tärkeää, koska se tulostaa myös binäärihakupuun solmut lajitellussa järjestyksessä, mutta vain jos annettu puu on binäärihakupuu. Jos muistat, BST:ssä vasemmanpuoleisen alipuun solmujen arvot ovat juurta pienempiä ja oikeanpuoleisen alipuun solmujen arvot ovat juurta suurempia. In order traversal tarkoittaa kirjaimellisesti IN order eli nuotit tulostetaan järjestyksessä tai lajitellussa järjestyksessä.
Btw, vaikka nämä kolme algoritmia (pre-order, in-order ja post-order) ovatkin suosittuja binary tree traversal -algoritmeja, mutta ne eivät ole ainoita. On olemassa myös muita leveyssuuntaisia tapoja binääripuun läpikäymiseen, esim. level order traversal (Katso Tietorakenne ja algoritmit: Syväsukellus).

Rekursiivinen algoritmi binääripuun InOrder-läpikäymisen toteuttamiseksi

Rekursiivinen inorder-läpikäymisen algoritmi on hyvin yksinkertainen. Sinun tarvitsee vain kutsua BinaryTree-luokan inOrder()-metodia siinä järjestyksessä, jossa haluat käydä puussa. Tärkeintä on sisällyttää mukaan perustapaus, joka on avainasemassa missä tahansa rekursiivisessa algoritmissa.

Esimerkiksi tässä ongelmassa perustapaus on, että saavutat lehtisolmun ja siellä ei ole enää yhtään solmua tutkittavana, jolloin rekursio alkaa päättyä. Tässä ovat tarkat vaiheet binääripuun läpikäymiseksi InOrder-traversaalin avulla:

1. vieraile vasemmassa solmussa
2. tulosta juuren arvo
3. vieraile oikeassa solmussa

ja tässä on esimerkkikoodi, jolla tämä algoritmi toteutetaan rekursiota käyttäen Javassa:
Viimeisen esimerkin preOrder()-metodin tapaan on olemassa toinen inOrder()-metodi, joka paljastaa inOrder-kierron julkiseksi ja kutsuu tätä yksityistä metodia, joka itse asiassa suorittaa InOrder-kierron.
Tämä on tavallinen tapa kirjoittaa rekursiivinen metodi, joka ottaa syötteen, se helpottaa asiakkaan kutsua metodia.

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

Voit nähdä, että aloitamme rootista ja sitten kutsumme rekursiivisesti inOrder()-metodia noden kanssa.left, mikä tarkoittaa, että menemme alaspäin vasemmalla alipuulla, kunnes osumme node == null, mikä tarkoittaa, että viimeinen solmu oli lehtisolmu.
Tässä vaiheessa inOrder()-metodi palaa ja suorittaa seuraavan rivin, joka tulostaa node.data. Sen jälkeen sen jälleen rekursiivinen inOrder()-kutsu node.right:lla, joka käynnistää saman prosessin uudelleen.
Voit myös tutustua Pluralsightin kursseihin Data Structure and Algorithms Part 1 ja 2 oppiaksesi lisää algoritmeista ja siitä, miten voit suunnitella omia algoritmejasi.

Tämän kurssin käyttämiseen tarvittaisiin Pluralsightin jäsenyyskortteli, joka kustantaa n. 29 dollaria kuukaudessa tai 299 dollaria vuodessa (14 %:n säästö). Minulla on sellainen ja suosittelen myös kaikille kehittäjille kyseistä suunnitelmaa, koska Pluralsight on kuin NetFlix ohjelmistokehittäjille.
Se sisältää yli 5000+ laadukasta kurssia kaikista uusimmista aiheista. Koska meidän ohjelmoijien on opittava uusia asioita joka päivä, 299 dollarin sijoitus ei ole paha.
Btw, se tarjoaa myös 10 päivän ilmaisen kokeilujakson ilman mitään velvoitteita, jonka avulla voit katsoa 200 tuntia sisältöä. Voit katsoa nämä kurssit ilmaiseksi kirjautumalla tuohon 10 päivän ilmaiseen kokeilujaksoon.

Java-ohjelma binääripuun InOrder-traversaalin toteuttamiseksi

Tässä on täydellinen ratkaisumme InOrder-traversaalialgoritmiin Javassa. Tämä ohjelma käyttää rekursiivista algoritmia tulostaakseen kaikkien binääripuun solmujen arvon käyttäen InOrder-traversaalia.
Kuten olen aiemmin kertonut, in-order-traversaalin aikana tulostetaan ensin vasemman alipuun arvo, sitten juuren ja oikean alipuun arvo. Jos olet kiinnostunut iteratiivisesta algoritmista, voit tutustua tarkemmin tähän opetusohjelmaan, jossa toteutetaan inOrder-traversaalia ilman rekursiota.

Siinä kaikki siitä, miten toteutetaan binääripuun inOrder-traversaalia Javassa rekursiota käyttäen. Näet, että koodi on melko samanlainen kuin preOrder-traversal, ainoa ero on järjestyksessä, jossa kutsumme metodia rekursiivisesti. Tässä tapauksessa kutsumme ensin inOrder(node.left) ja sitten tulostamme solmun arvon.
On syytä muistaa, että in order traversal on depth-first-algoritmi ja tulostaa puun solmun lajitellussa järjestyksessä, jos annettu binääripuu on binäärihakupuu.
Tämän artikkelin seuraavassa osassa kerron inOrder traversalista ilman rekursiota, sillä välin voit kokeilla harjoitella seuraavia tietorakenne- ja binääripuuongelmia.
Jatko-opiskelu
Datarakenteet ja algoritmit: 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 kysymystä ja ratkaisuja
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? (ratkaisu)
• 5 kirjaa tietorakenteen ja algoritmien oppimiseen Javassa? (kirjat)
• Top 50 Java-ohjelmaa koodaushaastatteluista (katso tästä)
• 5 ilmaista tietorakenne- ja algoritmikurssia ohjelmoijille (kurssit)
• Miten tarkistetaan onko merkkijono palindromi Javassa?
• Miten löytää puuttuva numero lajitellusta joukosta Javassa?
• 10 algoritmikirjaa, jotka jokaisen ohjelmoijan pitäisi lukea (kirjat)
• 10 ilmaista tietorakenne- ja algoritmikurssia ohjelmoijille (kurssit)
• 100+ tietorakenteiden koodausongelmaa haastatteluista (kysymykset)
• Miten tulostetaan Fibonacci-sarja Javalla käyttämättä rekursiota?
• Miten tarkistetaan, onko kokonaisluku kahden potenssi ilman jako- tai modulo-operaattoria?
• Miten löydetään kaikki Stringin permutaatiot Javassa?
• Top 20 String-koodauksen haastattelukysymystä (katso täältä)
• 50+ Tietorakenne- ja algoritmiongelmaa haastatteluista (kysymykset)
• Miten poistaa elementti joukosta käyttämättä kolmatta-osapuolen kirjastoa (katso täältä)
• Miten löydetään suurin ja pienin luku joukosta Javassa (lue täältä)
• Miten löydetään kaksi maksimilukua kokonaislukumassasta Javassa (katso täältä)