Traversal InOrder jest jednym z trzech popularnych sposobów trawersowania struktury danych drzewa binarnego, pozostałe dwa to preOrder i postOrder. W algorytmie in-order traversal najpierw eksplorowane jest lewe poddrzewo, następnie korzeń, a na końcu węzły w prawym poddrzewie. Rozpoczynasz traversal od korzenia, następnie przechodzisz do lewego węzła, potem znowu do lewego węzła, aż dojdziesz do węzła liścia. W tym momencie wypisujesz wartość węzła lub oznaczasz go jako odwiedzony i przenosisz do prawego poddrzewa. Kontynuując ten sam algorytm, aż wszystkie węzły drzewa binarnego zostaną odwiedzone. InOrderal traversal jest również znany jako left-node-right lub left-root-right traversal lub LNR traversal algorithm.
Podobnie do algorytmu preOrder, jest to również algorytm depth-first, ponieważ bada głębokość drzewa binarnego przed zbadaniem rodzeństwa. Ponieważ jest to jeden z podstawowych algorytmów drzewa binarnego, jest dość popularny w rozmowach programistycznych.
Te algorytmy traversal są również podstawą do nauki bardziej zaawansowanych algorytmów drzewa binarnego, dlatego każdy programista powinien się nauczyć, zrozumieć i wiedzieć, jak zaimplementować inOrder i inne algorytmy traversal.
Najprostszym sposobem implementacji algorytmu traversal inOrder w Javie lub dowolnym języku programowania jest użycie rekurencji. Ponieważ drzewo binarne jest rekurencyjną strukturą danych, rekurencja jest naturalnym wyborem do rozwiązania problemu opartego na drzewie. Metoda inOrder() w klasie BinaryTree implementuje logikę pozwalającą na trawersowanie drzewa binarnego przy użyciu rekurencji.
Z punktu widzenia wywiadu, traversal InOrder jest niezwykle ważny, ponieważ wypisuje węzły drzewa wyszukiwania binarnego w posortowanej kolejności, ale tylko wtedy, gdy dane drzewo jest drzewem wyszukiwania binarnego. Jeśli pamiętasz, w BST wartość węzłów w lewym poddrzewie jest niższa niż korzeń, a wartości węzłów w prawym poddrzewie są wyższe niż korzeń. In order traversal dosłownie oznacza IN order i.e. notatki są drukowane w kolejności lub posortowanej kolejności.
Btw, nawet jeśli te trzy algorytmy (pre-order, in-order i post-order) są popularnymi algorytmami traversal drzewa binarnego, ale nie są jedynymi. Istnieją również inne sposoby przemieszczania się po drzewie binarnym, np. wyrównywanie kolejności poziomów (patrz Struktura danych i algorytmy: Deep Dive).

Rekursywny algorytm implementacji InOrder traversal of a Binary tree

Rekursywny algorytm przemieszczania inorder jest bardzo prosty. Wystarczy wywołać metodę inOrder() klasy BinaryTree w takiej kolejności, w jakiej chcemy odwiedzić drzewo. Co jest najważniejsze, to uwzględnienie przypadku bazowego, który jest kluczowy dla każdego algorytmu rekurencyjnego.

Na przykład w tym problemie, przypadek bazowy to osiągnięcie węzła liścia i nie ma więcej węzłów do zbadania, w tym momencie rekurencja zaczyna się zwijać. Oto dokładne kroki, aby przemierzyć drzewo binarne za pomocą InOrder traversal:

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

i tutaj jest przykładowy kod do implementacji tego algorytmu za pomocą rekurencji w Javie:
Podobnie jak metoda preOrder() w ostatnim przykładzie, istnieje inna metoda inOrder(), która wystawia inorder traversal na widok publiczny i wywołuje tę prywatną metodę, która faktycznie wykonuje InOrder traversal.
Jest to standardowy sposób pisania metody rekurencyjnej, która pobiera dane wejściowe, ułatwia to klientowi wywołanie metody.

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

Widzisz, że zaczynamy od root, a następnie wywołujemy rekurencyjnie metodę inOrder() z node.left, co oznacza, że schodzimy w dół po lewym poddrzewie, aż trafimy na node == null, co oznacza, że ostatni węzeł był węzłem liściowym.
W tym momencie metoda inOrder() powróci i wykona następną linię, która wypisze node.data. Po tym jego ponownie rekurencyjne wywołanie inOrder() z node.right, które zainicjuje ten sam proces ponownie.
Możesz również sprawdzić Data Structure i Algorithms Part 1 i 2 kursy na Pluralsight, aby dowiedzieć się więcej o algorytmach i jak projektować własne algorytmy.

Btw, potrzebujesz członkostwa Pluralsight, aby uzyskać dostęp do tego kursu, który kosztuje około $29 miesięcznie lub $299 rocznie (14% oszczędności). Mam jeden i również sugeruję wszystkim deweloperom mieć ten plan, ponieważ Pluralsight jest jak NetFlix dla programistów.
Ma ponad 5000+ dobrej jakości kursów na wszystkie najnowsze tematy. Ponieważ my programiści musimy uczyć się nowych rzeczy każdego dnia, inwestycja 299 USD nie jest zła.
Btw, oferuje również 10-dniową darmową wersję próbną bez żadnych zobowiązań, która pozwala na obejrzenie 200 godzin treści. Możesz oglądać te kursy za darmo, zapisując się na tę 10-dniową bezpłatną wersję próbną.

Program Java do implementacji InOrder traversal of a Binary tree

Tutaj jest nasze kompletne rozwiązanie algorytmu inorder traversal w Javie. Ten program używa rekurencyjnego algorytmu do drukowania wartości wszystkich węzłów drzewa binarnego używając InOrder traversal.
Jak mówiłem wcześniej, podczas in-order traversal wartość lewego poddrzewa jest drukowana jako pierwsza, a następnie korzeń i prawe poddrzewo. Jeśli jesteś zainteresowany algorytmem iteracyjnym, możesz dalej sprawdzić ten tutorial implementacji in-order traversal bez rekurencji.

To wszystko o tym, jak zaimplementować inOrder traversal drzewa binarnego w Javie przy użyciu rekurencji. Możesz zobaczyć, że kod jest dość podobny do traversal preOrder z jedyną różnicą w kolejności, w jakiej wywołujemy metodę rekurencyjnie. W tym przypadku najpierw wywołujemy inOrder(node.left), a następnie wypisujemy wartość węzła.
Warto pamiętać, że in order traversal jest algorytmem depth-first i wypisuje węzły drzewa w posortowanej kolejności, jeśli dane drzewo binarne jest drzewem wyszukiwania binarnego.
W następnej części tego artykułu, podzielę się inOrder traversal bez rekurencji, w międzyczasie, możesz spróbować przećwiczyć następujące problemy związane ze strukturami danych i drzewami binarnymi.
Dalsza nauka
Data Structures and Algorithms: 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
Inne struktury danych i algorytmy – tutoriale dla programistów Java

• 10 książek o algorytmach, które każdy programista powinien przeczytać (lista)
• Jak zaimplementować algorytm Quicksort w Javie? (rozwiązanie)
• 5 książek do nauki struktury danych i algorytmów w Javie? (książki)
• Top 50 Java Programs from Coding Interviews (zobacz tutaj)
• 5 Free Data Structure and Algorithms Courses for Programmers (kursy)
• Jak sprawdzić czy łańcuch jest palindromem w Javie?
• Jak znaleźć brakującą liczbę w posortowanej tablicy w Javie?
• 10 książek o algorytmach, które każdy programista powinien przeczytać (książki)
• 10 darmowych kursów o strukturze danych i algorytmach dla programistów (kursy)
• 100+ problemów z kodowaniem struktury danych z wywiadów (pytania)
• Jak wydrukować serię Fibonacciego w Javie bez użycia rekursji?
• Jak sprawdzić, czy liczba całkowita jest potęgą dwójki bez użycia operatora dzielenia lub modulo?
• Jak znaleźć wszystkie permutacje ciągu znaków w Javie?
• Top 20 String coding questions interview (sprawdź tutaj)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• Jak usunąć element z tablicy bez użycia 3rd- partystrony biblioteki (sprawdź tutaj)
• Jak znaleźć największą i najmniejszą liczbę w tablicy w Javie (przeczytaj tutaj)
• Jak znaleźć dwie maksymalne liczby na tablicy liczb całkowitych w Javie (sprawdź tutaj)