Procházení InOrder je jedním ze tří oblíbených způsobů procházení binární stromové datové struktury, dalšími dvěma jsou preOrder a postOrder. Při algoritmu procházení v pořadí je nejprve prozkoumán levý podstrom, poté kořen a nakonec uzly pravého podstromu. Procházení začínáte od kořene, pak přejdete k levému uzlu, pak opět přejdete k levému uzlu, dokud nedosáhnete listového uzlu. V tomto okamžiku vypíšete hodnotu uzlu nebo jej označíte jako navštívený a přesunete se do pravého podstromu. Pokračujte stejným algoritmem, dokud nenavštívíte všechny uzly binárního stromu. Obcházení InOrder je také známé jako obcházení levý uzel-pravý nebo levý kořen-pravý nebo algoritmus LNR.
Podobně jako algoritmus preOrder je také algoritmem hloubkovým, protože před prozkoumáním sourozenců prozkoumává hloubku binárního stromu. Protože je to jeden ze základních algoritmů binárního stromu, je v rozhovorech o programování poměrně oblíbený.
Tyto algoritmy procházení jsou také základem pro učení pokročilejších algoritmů binárního stromu, proto by se každý programátor měl naučit, pochopit a umět implementovat algoritmus procházení v pořadí a další algoritmy.
Nejjednodušší způsob, jak implementovat algoritmus procházení v pořadí v jazyce Java nebo v jakémkoli programovacím jazyce, je pomocí rekurze. Protože binární strom je rekurzivní datová struktura, je rekurze přirozenou volbou pro řešení problému založeného na stromu. Metoda inOrder() ve třídě BinaryTree implementuje logiku procházení binárního stromu pomocí rekurze.
Z hlediska Interview je inOrder traversal nesmírně důležitý, protože také vypisuje uzly binárního vyhledávacího stromu v seřazeném pořadí, ale pouze v případě, že daný strom je binární vyhledávací strom. Pokud si vzpomínáte, v BST jsou hodnoty uzlů v levém podstromu nižší než kořen a hodnoty uzlů v pravém podstromu jsou vyšší než kořen. In order traversal doslova znamená IN order, tj. poznámky jsou vypsány v pořadí nebo seřazené.
Btw, i když tyto tři algoritmy (pre-order, in-order a post-order) jsou populární algoritmy procházení binárních stromů, nejsou jediné. Máte k dispozici i další způsoby procházení binárního stromu do šířky, např. procházení v pořadí úrovní (viz Struktura dat a algoritmy: Hluboký ponor).

Rekurzivní algoritmus pro implementaci procházení binárního stromu v pořadí

Rekurzivní algoritmus procházení v pořadí je velmi jednoduchý. Stačí zavolat metodu inOrder() třídy BinaryTree v pořadí, v jakém chcete strom navštívit. Nejdůležitější je zahrnout základní případ, který je klíčový pro každý rekurzivní algoritmus.

Například v tomto problému je základním případem to, že dosáhnete listového uzlu a už není žádný další uzel k prozkoumání, v tomto okamžiku se rekurze začne ukončovat. Zde jsou přesné kroky k procházení binárního stromu pomocí InOrder traversal:

1. navštívit levý uzel
2. vypsat hodnotu kořene
3. navštívit pravý uzel

a zde je ukázka kódu pro implementaci tohoto algoritmu pomocí rekurze v jazyce Java:
Podobně jako metoda preOrder() v minulém příkladu existuje další metoda inOrder(), která vystavuje inOrder traversal veřejnosti a volá tuto soukromou metodu, která skutečně provádí inOrder traversal.
Toto je standardní způsob zápisu rekurzivní metody, která přebírá vstup, usnadňuje to klientovi volání metody.

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

Vidíte, že začínáme s root a pak rekurzivně voláme metodu inOrder() s node.left, což znamená, že postupujeme dolů po levém podstromu, dokud nenarazíme na node == null, což znamená, že poslední uzel byl listový uzel.
V tomto okamžiku se metoda inOrder() vrátí a provede další řádek, který vypíše node.data. Poté následuje opět jeho rekurzivní volání inOrder() s node.right, které opět zahájí stejný proces.
Můžete se také podívat na kurzy Data Structure and Algorithms Part 1 a 2 na Pluralsight, kde se dozvíte více o algoritmech a o tom, jak navrhovat vlastní algoritmy.

Btw, pro přístup k tomuto kurzu byste potřebovali členství na Pluralsight, které stojí přibližně 29 dolarů měsíčně nebo 299 dolarů ročně (úspora 14 %). Já ho mám a také doporučuji všem vývojářům, aby měli tento plán, protože Pluralsight je jako NetFlix pro vývojáře softwaru
Má více než 5000+ kvalitních kurzů na všechna nejnovější témata. Protože se my programátoři musíme každý den učit nové věci, investice 299 USD není špatná.
Btw, nabízí také 10denní nezávaznou zkušební verzi, která vám umožní zhlédnout 200 hodin obsahu. Tyto kurzy můžete sledovat zdarma, pokud se přihlásíte k této 10denní bezplatné zkušební verzi.

Program v jazyce Java pro implementaci InOrder traverzování binárního stromu

Tady je naše kompletní řešení algoritmu InOrder traverzování v jazyce Java. Tento program používá rekurzivní algoritmus k vypsání hodnoty všech uzlů binárního stromu pomocí InOrder traversalu.
Jak jsem vám již řekl, při InOrder traversalu se nejprve vypíše hodnota levého podstromu, poté kořenového a pravého podstromu. Pokud vás zajímá iterační algoritmus, můžete se dále podívat na tento návod implementace inOrder traversalu bez rekurze.
To je vše o tom, jak implementovat inOrder traversal binárního stromu v Javě pomocí rekurze. Vidíte, že kód je do značné míry podobný jako u preOrder traversal s jediným rozdílem v pořadí, v jakém rekurzivně voláme metodu. V tomto případě nejprve zavoláme inOrder(node.left) a poté vypíšeme hodnotu uzlu.
Stojí za to si uvědomit, že in order traversal je hloubkový algoritmus a vypíše uzel stromu v seřazeném pořadí, pokud je daný binární strom binární vyhledávací strom.
V příští části tohoto článku se s vámi podělím o inOrder traversal bez rekurze, mezitím si můžete zkusit procvičit následující úlohy na datové struktury a binární stromy.
Další učení
Datové struktury a algoritmy: Hluboký ponor s využitím Javy
Algoritmy a datové struktury – 1. a 2. část
Datové struktury v Javě 9 podle Heinze Kabutze
Prolamování kódovacího pohovoru – 189 otázek a řešení
Prolamování kódovacího pohovoru: Další výukové materiály o datových strukturách a algoritmech pro programátory v Javě

• 10 knih o algoritmech, které by si měl přečíst každý programátor (seznam)
• Jak implementovat algoritmus Quicksort v Javě? (řešení)
• 5 knih pro výuku datové struktury a algoritmů v Javě? (knihy)
• Top 50 programů v Javě z kódovacích rozhovorů (viz zde)
• 5 bezplatných kurzů datové struktury a algoritmů pro programátory (kurzy)
• Jak zjistit, zda je řetězec palindrom v Javě?
• Jak v Javě zjistit chybějící číslo v setříděném poli?
• 10 knih o algoritmech, které by si měl přečíst každý programátor (knihy)
• 10 bezplatných kurzů datové struktury a algoritmů pro programátory (kurzy)
• 100+ problémů kódování datové struktury z rozhovorů (otázky)
• Jak vypsat Fibonacciho řadu v Javě bez použití rekurze?
• Jak zjistit, zda je celé číslo mocninou dvou bez použití operátoru dělení nebo modulo?
• Jak najít všechny permutace řetězce v Javě?
• Top 20 otázek z pohovoru na kódování řetězců (viz zde)
• 50+ úloh o datových strukturách a algoritmech z pohovorů (otázky)
• Jak odstranit prvek z pole bez použití tercie-knihovny třetí strany (podívejte se zde)
• Jak najít největší a nejmenší číslo v poli v jazyce Java (přečtěte si zde)
• Jak najít dvě maximální čísla na celočíselném poli v jazyce Java (podívejte se zde)