Inversione di un albero binario in Java

1. Panoramica

L'inversione di un albero binario è uno dei problemi che ci potrebbe essere chiesto di risolvere durante un colloquio tecnico .

In questo breve tutorial, vedremo un paio di modi diversi per risolvere questo problema.

2. Albero binario

Un albero binario è una struttura di dati in cui ogni elemento ha al massimo due figli , che vengono indicati come figlio sinistro e figlio destro. L'elemento superiore dell'albero è il nodo radice, mentre i figli sono i nodi interni .

Tuttavia, se un nodo non ha elementi secondari, si chiama foglia.

Detto questo, creiamo il nostro oggetto che rappresenta un nodo:

public class TreeNode { private int value; private TreeNode rightChild; private TreeNode leftChild; // Getters and setters }

Quindi, creiamo il nostro albero che useremo nei nostri esempi:

 TreeNode leaf1 = new TreeNode(1); TreeNode leaf2 = new TreeNode(3); TreeNode leaf3 = new TreeNode(6); TreeNode leaf4 = new TreeNode(9); TreeNode nodeRight = new TreeNode(7, leaf3, leaf4); TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2); TreeNode root = new TreeNode(4, nodeLeft, nodeRight); 

Nel metodo precedente, abbiamo creato la seguente struttura:

Invertendo l'albero da sinistra a destra, finiremo per avere la seguente struttura:

3. Inversione dell'albero binario

3.1. Metodo ricorsivo

Nel primo esempio, useremo la ricorsione per invertire l'albero .

Per prima cosa chiameremo il nostro metodo usando la radice dell'albero, poi lo applicheremo rispettivamente ai figli di sinistra e di destra fino a raggiungere le foglie dell'albero:

public void reverseRecursive(TreeNode treeNode) { if(treeNode == null) { return; } TreeNode temp = treeNode.getLeftChild(); treeNode.setLeftChild(treeNode.getRightChild()); treeNode.setRightChild(temp); reverseRecursive(treeNode.getLeftChild()); reverseRecursive(treeNode.getRightChild()); }

3.2. Metodo iterativo

Nel secondo esempio, invertiremo l'albero utilizzando un approccio iterativo. Per questo, useremo una LinkedList , che inizializzeremo con la radice del nostro albero .

Quindi, per ogni nodo che interroghiamo dalla lista, aggiungiamo i suoi figli a quella lista prima di permutarli .

Continuiamo ad aggiungere e rimuovere dalla LinkedList fino a raggiungere le foglie dell'albero:

public void reverseIterative(TreeNode treeNode) { List queue = new LinkedList(); if(treeNode != null) { queue.add(treeNode); } while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(node.getLeftChild() != null){ queue.add(node.getLeftChild()); } if(node.getRightChild() != null){ queue.add(node.getRightChild()); } TreeNode temp = node.getLeftChild(); node.setLeftChild(node.getRightChild()); node.setRightChild(temp); } }

4. Conclusione

In questo rapido articolo, abbiamo esplorato i due modi per invertire un albero binario. Abbiamo iniziato utilizzando un metodo ricorsivo per invertirlo. Quindi, abbiamo finito per utilizzare un modo iterativo per ottenere lo stesso risultato.

Il codice sorgente completo di questi esempi e casi di unit test può essere trovato su Github.