L’InOrder traversal è uno dei tre modi popolari per attraversare una struttura dati ad albero binario, gli altri due sono il preOrder e il postOrder. Durante l’algoritmo di in-order traversal, il sottoalbero di sinistra viene esplorato per primo, seguito dalla radice e infine dai nodi del sottoalbero di destra. Si inizia l’attraversamento dalla radice, poi si va al nodo di sinistra, poi di nuovo al nodo di sinistra fino a raggiungere un nodo foglia. A quel punto, si stampa il valore del nodo o lo si segna come visitato e si passa al sottoalbero di destra. Continuando lo stesso algoritmo fino a quando tutti i nodi dell’albero binario sono visitati. L’InOrder traversal è anche conosciuto come left-node-right o left-root-right traversal o LNR traversal algorithm.
Simile all’algoritmo preOrder, è anche un algoritmo depth-first perché esplora la profondità di un albero binario prima di esplorare i fratelli. Poiché è uno degli algoritmi fondamentali dell’albero binario è abbastanza popolare nelle interviste di programmazione.
Questi algoritmi di attraversamento sono anche la base per imparare algoritmi di albero binario più avanzati, quindi ogni programmatore dovrebbe imparare, capire e sapere come implementare l’algoritmo in-order e altri algoritmi di attraversamento.
Il modo più semplice per implementare l’algoritmo di attraversamento inOrder in Java o qualsiasi linguaggio di programmazione è usando la ricorsione. Poiché l’albero binario è una struttura dati ricorsiva, la ricorsione è la scelta naturale per risolvere un problema basato sull’albero. Il metodo inOrder() nella classe BinaryTree implementa la logica per attraversare un albero binario usando la ricorsione.
Dal punto di vista di Interview, InOrder traversal è estremamente importante perché stampa anche i nodi di un albero di ricerca binario nell’ordine ordinato ma solo se l’albero dato è un albero di ricerca binario. Se vi ricordate, in BST, il valore dei nodi nel sottoalbero di sinistra è inferiore alla radice, e i valori dei nodi nel sottoalbero di destra sono superiori alla radice. L’In order traversal significa letteralmente IN order cioè le note sono stampate nell’ordine o nell’ordine ordinato.
Btw, anche se questi tre algoritmi (pre-order, in-order, e post-order) sono algoritmi popolari di traversata dell’albero binario ma non sono gli unici. Ci sono anche altri modi per attraversare un albero binario, per esempio il level order traversal (vedi Struttura dei dati e algoritmi: Deep Dive).

L’algoritmo ricorsivo per implementare InOrder traversal di un albero binario

L’algoritmo ricorsivo di inorder traversal è molto semplice. Hai solo bisogno di chiamare il metodo inOrder() della classe BinaryTree nell’ordine in cui vuoi visitare l’albero. La cosa più importante è includere il caso base, che è la chiave di ogni algoritmo ricorsivo.
Per esempio, in questo problema, il caso base è che si raggiunge il nodo foglia e non c’è più nessun nodo da esplorare, a quel punto la ricorsione inizia a finire. Ecco i passi esatti per attraversare l’albero binario usando InOrder traversal:

1. visita il nodo sinistro
2. stampa il valore della radice
3. visita il nodo destro

ed ecco il codice di esempio per implementare questo algoritmo usando la ricorsione in Java:
Simile al metodo preOrder() nell’ultimo esempio, c’è un altro metodo inOrder() che espone l’inorder traversal al pubblico e chiama questo metodo privato che effettivamente esegue l’inOrder traversal.
Questo è il modo standard di scrivere un metodo ricorsivo che prende input, rende più facile per un client chiamare il metodo.

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

Si può vedere che iniziamo con root e poi chiamiamo ricorsivamente il metodo inOrder() con node.left, il che significa che stiamo scendendo nel sottoalbero di sinistra fino a quando colpiamo node == null, il che significa che l’ultimo nodo era un nodo foglia.
A questo punto, il metodo inOrder() ritornerà ed eseguirà la prossima linea, che stampa i node.data. Dopo di che la sua chiamata inOrder() ricorsiva con node.right, che inizierà di nuovo lo stesso processo.
Puoi anche controllare i corsi Data Structure and Algorithms Part 1 e 2 su Pluralsight per imparare di più sugli algoritmi e come progettare i tuoi algoritmi.

Btw, avresti bisogno di un abbonamento Pluralsight per accedere a questo corso, che costa circa $29 mensili o $299 annuali (14% di risparmio). Io ne ho uno e suggerisco anche a tutti gli sviluppatori di avere questo piano perché Pluralsight è come NetFlix per gli sviluppatori di software.
Ha più di 5000+ corsi di buona qualità su tutti gli ultimi argomenti. Dato che noi programmatori dobbiamo imparare cose nuove ogni giorno, un investimento di 299 dollari non è male.
Btw, offre anche una prova gratuita di 10 giorni senza alcun obbligo che ti permette di guardare 200 ore di contenuti. Puoi guardare questi corsi gratuitamente firmando per quei 10 giorni di prova gratuita.

Programma Java per implementare InOrder traversal di un albero binario

Ecco la nostra soluzione completa all’algoritmo inorder traversal in Java. Questo programma usa un algoritmo ricorsivo per stampare il valore di tutti i nodi di un albero binario usando InOrder traversal.

Come vi ho detto prima, durante l’in-order traversal viene stampato prima il valore del sottoalbero di sinistra, seguito dalla radice e dal sottoalbero di destra. Se siete interessati all’algoritmo iterativo, potete controllare ulteriormente questo tutorial sull’implementazione dell’in order traversal senza ricorsione.
Questo è tutto su come implementare l’inOrder traversal di un albero binario in Java usando la ricorsione. Potete vedere che il codice è abbastanza simile al preOrder traversal con l’unica differenza nell’ordine in cui chiamiamo il metodo in modo ricorsivo. In questo caso, chiamiamo prima inOrder(node.left) e poi stampiamo il valore del nodo.
Va ricordato che in order traversal è un algoritmo depth-first e stampa il nodo dell’albero in ordine ordinato se l’albero binario dato è un albero di ricerca binario.
Nella prossima parte di questo articolo, condividerò inOrder traversal senza ricorsione, nel frattempo, puoi provare a praticare i seguenti problemi di struttura dei dati e albero binario.
Apprendimento ulteriore
Strutture di dati e algoritmi: Deep Dive Using Java
Algoritmi e strutture di dati – Parte 1 e 2
Strutture di dati in Java 9 di Heinz Kabutz
Cracking the Coding Interview – 189 domande e soluzioni
Grokking the Coding Interview: Patterns for Coding Questions
Altri tutorial su strutture dati e algoritmi per programmatori Java

• 10 libri sugli algoritmi che ogni programmatore dovrebbe leggere (elenco)
• Come implementare l’algoritmo Quicksort in Java? (soluzione)
• 5 libri per imparare la struttura dei dati e gli algoritmi in Java? (libri)
• Top 50 programmi Java da Coding Interviews (vedi qui)
• 5 corsi gratuiti di struttura dati e algoritmi per programmatori (corsi)
• Come controllare se una stringa è un palindromo in Java?
• Come trovare il numero mancante in un array ordinato in Java?
• 10 libri sugli algoritmi che ogni programmatore dovrebbe leggere (libri)
• 10 corsi gratuiti sulla struttura dei dati e sugli algoritmi per programmatori (corsi)
• 100+ problemi di codifica della struttura dei dati dalle interviste (domande)
• Come stampare la serie Fibonacci in Java senza usare la ricorsione?
• Come controllare se un intero è una potenza di due senza usare la divisione o l’operatore modulo?
• Come trovare tutte le permutazioni di stringa in Java?
• Top 20 domande di intervista sulla codifica delle stringhe (vedi qui)
• 50+ Problemi di struttura dei dati e algoritmi dalle interviste (domande)
• Come rimuovere un elemento dall’array senza usare una libreria di terze parti (controlla qui)
• Come rimuovere un elemento dall’array senza usare una
• Come trovare il numero più grande e più piccolo in una matrice in Java (leggi qui)
• Come trovare due numeri massimi su una matrice intera in Java (controlla qui)