Traversarea InOrder este una dintre cele trei modalități populare de a traversa o structură de date de arbore binar, celelalte două fiind preOrder și postOrder. În timpul algoritmului de traversare în ordine, subarborele din stânga este explorat mai întâi, urmat de rădăcină și, în cele din urmă, de nodurile din subarborele din dreapta. Se începe parcurgerea de la rădăcină, apoi se merge la nodul din stânga, apoi se merge din nou la nodul din stânga până când se ajunge la un nod frunză. În acel moment, se tipărește valoarea nodului sau se marchează ca fiind vizitat și se trece la subarboretul din dreapta. Se continuă același algoritm până când toate nodurile arborelui binar sunt vizitate. Parcurgerea InOrder este cunoscută și sub numele de algoritmul de parcurgere stânga-nod-dreapta sau stânga-rădăcină-dreapta sau algoritmul de parcurgere LNR.
Similar cu algoritmul preOrder, acesta este, de asemenea, un algoritm de tip depth-first, deoarece explorează adâncimea unui arbore binar înainte de a explora frații. Deoarece este unul dintre algoritmii fundamentali ai arborelui binar, este destul de popular în interviurile de programare.
Acești algoritmi de traversare sunt, de asemenea, baza pentru a învăța algoritmi mai avansați ai arborelui binar, prin urmare fiecare programator ar trebui să învețe, să înțeleagă și să știe cum să implementeze algoritmii de traversare inOrder și alți algoritmi de traversare.
Cel mai simplu mod de a implementa algoritmul de traversare inOrder în Java sau în orice alt limbaj de programare este prin utilizarea recursivității. Deoarece arborele binar este o structură de date recursivă, recursivitatea este alegerea naturală pentru a rezolva o problemă bazată pe arbore. Metoda inOrder() din clasa BinaryTree implementează logica de parcurgere a unui arbore binar folosind recursivitatea.
Din punctul de vedere al interviului, parcurgerea InOrder este extrem de importantă deoarece imprimă, de asemenea, nodurile unui arbore binar de căutare în ordinea ordonată, dar numai dacă arborele dat este un arbore binar de căutare. Dacă vă amintiți, în BST, valoarea nodurilor din subarborele din stânga este mai mică decât cea a rădăcinii, iar valorile nodurilor din subarborele din dreapta sunt mai mari decât cele ale rădăcinii. Traversarea în ordine înseamnă literalmente ÎN ordine, adică notele sunt tipărite în ordine sau în ordine sortată.
Btw, chiar dacă acești trei algoritmi (pre-order, in-order și post-order) sunt algoritmi populari de traversare a arborilor binari, dar nu sunt singurii. Aveți, de asemenea, și alte modalități de parcurgere a unui arbore binar, de exemplu, parcurgerea în ordine de nivel (a se vedea Data Structure and Algorithms: Deep Dive).

Algoritmul recursiv pentru a implementa parcurgerea InOrder a unui arbore binar

Algoritmul recursiv de parcurgere în ordine este foarte simplu. Trebuie doar să apelați metoda inOrder() a clasei BinaryTree în ordinea în care doriți să vizitați arborele. Ceea ce este cel mai important este să includeți cazul de bază, care este cheia oricărui algoritm recursiv.
De exemplu, în această problemă, cazul de bază este că ați ajuns la nodul frunză și nu mai există niciun nod de explorat, în acel moment recursivitatea începe să se termine. Iată pașii exacți pentru parcurgerea arborelui binar utilizând traversarea InOrderal:

1. vizitează nodul din stânga
2. imprimă valoarea rădăcinii
3. vizitează nodul din dreapta

și iată exemplul de cod pentru a implementa acest algoritm utilizând recursivitatea în Java:
Asemănător metodei preOrder() din ultimul exemplu, există o altă metodă inOrder() care expune public traversarea InOrder și apelează această metodă privată care efectuează efectiv traversarea InOrder.
Aceasta este modalitatea standard de a scrie o metodă recursivă care primește date de intrare, aceasta facilitează apelarea metodei de către un client.

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

Vezi că începem cu root și apoi apelăm recursiv metoda inOrder() cu node.left, ceea ce înseamnă că mergem în jos pe subarboretul stâng până când ajungem la node == null, ceea ce înseamnă că ultimul nod a fost un nod frunză.
În acest moment, metoda inOrder() se va întoarce și va executa următoarea linie, care tipărește node.data. După aceea, este din nou apelarea recursivă a metodei inOrder() cu node.right, care va iniția din nou același proces.
Puteți, de asemenea, să consultați cursurile Data Structure and Algorithms Part 1 și 2 de pe Pluralsight pentru a afla mai multe despre algoritmi și cum să vă proiectați proprii algoritmi.

Btw, veți avea nevoie de un abonament Pluralsight pentru a accesa acest curs, care costă în jur de 29 de dolari lunar sau 299 de dolari anual (14% economie). Eu am unul și, de asemenea, sugerez tuturor dezvoltatorilor să aibă acest plan, deoarece Pluralsight este ca NetFlix pentru dezvoltatorii de software.
Acesta are peste 5000+ cursuri de bună calitate pe toate subiectele de ultimă oră. Având în vedere că noi, programatorii, trebuie să învățăm lucruri noi în fiecare zi, o investiție de 299 USD nu este rea.
Btw, oferă și o perioadă de încercare gratuită de 10 zile, fără nicio obligație, care vă permite să vizionați 200 de ore de conținut. Puteți viziona aceste cursuri gratuit dacă vă înscrieți pentru acea perioadă de încercare gratuită de 10 zile.

Program Java pentru a implementa traversarea InOrder a unui arbore binar

Iată soluția noastră completă pentru algoritmul de traversare InOrder în Java. Acest program utilizează un algoritm recursiv pentru a imprima valoarea tuturor nodurilor unui arbore binar folosind traversarea în ordine.
Așa cum v-am mai spus, în timpul traversării în ordine se imprimă mai întâi valoarea subarborelui din stânga, urmată de rădăcină și subarborele din dreapta. Dacă sunteți interesat de algoritmul iterativ, puteți verifica în continuare acest tutorial de implementare a traversării în ordine fără recursivitate.
Acesta este tot despre cum să implementați traversarea în ordine a unui arbore binar în Java folosind recursivitatea. Puteți vedea că codul este destul de asemănător cu traversarea preOrder, cu singura diferență în ordinea în care apelăm metoda prin recursivitate. În acest caz, apelăm mai întâi inOrder(node.left) și apoi tipărim valoarea nodului.
Merită să ne amintim că traversarea în ordine este un algoritm de tip depth-first și tipărește nodurile arborelui în ordine sortată dacă arborele binar dat este un arbore binar de căutare.
În următoarea parte a acestui articol, voi împărtăși înOrder traversal fără recursivitate, între timp, puteți încerca să exersați următoarele probleme de structură de date și arbore binar.
Învățare suplimentară
Structuri de date și algoritmi: Deep Dive Using Java
Algoritmi și structuri de date – Partea 1 și 2
Structuri de date în Java 9 de Heinz Kabutz
Cracking the Coding Interview – 189 de întrebări și soluții
Groking the Coding Interview: Patterns for Coding Questions
Alte tutoriale de structură de date și algoritmi pentru programatorii Java

• 10 cărți despre algoritmi pe care orice programator ar trebui să le citească (listă)
• Cum se implementează algoritmul Quicksort în Java? (soluție)
• 5 cărți pentru a învăța structura de date și algoritmi în Java? (cărți)
• Top 50 de programe Java de la Interviuri de codare (vezi aici)
• 5 cursuri gratuite de structură de date și algoritmi pentru programatori (cursuri)
• Cum să verificați dacă un șir este un palindrom în Java?
• Cum să găsiți numărul lipsă într-o matrice sortată în Java?
• 10 cărți despre algoritmi pe care orice programator ar trebui să le citească (cărți)
• 10 cursuri gratuite de structură de date și algoritmi pentru programatori (cursuri)
• 100+ probleme de codificare a structurii de date de la interviuri (întrebări)
• Cum se tipărește seria Fibonacci în Java fără a folosi Recursiunea?
• Cum să verificați dacă un număr întreg este o putere de doi fără a folosi diviziunea sau operatorul modulo?
• Cum să găsiți toate permutările de String în Java?
• Top 20 de întrebări de interviu de codificare String (vezi aici)
• 50+ Probleme de structură de date și algoritmi de la interviuri (întrebări)
• Cum să eliminați un element din matrice fără a folosi un al treilea-…party party library (vezi aici)
• Cum găsiți cel mai mare și cel mai mic număr dintr-un array în Java (citește aici)
• Cum găsiți două numere maxime pe un array de numere întregi în Java (vezi aici)