strutture dati efficienti ottimizzano le prestazioni di un programma, rendendo più facile per il programma per trovare i dati di cui ha bisogno. Alberi binari di ricerca sono una delle strutture dati più efficienti per la ricerca attraverso un insieme di dati ordinato. Sia che la vostra struttura dati è un organizzato albero binario di ricerca o di un albero binario standard, è possibile trovare l'altezza del albero in Java tramite una semplice funzione ricorsiva.

Struttura albero

Un albero binario è costituito da un insieme di nodi interconnessi. Ogni nodo ha tra zero e due nodi figlio. Ogni nodo ad eccezione del nodo radice ha esattamente un nodo genitore. Il nodo radice non ha nodi padre. Java non ha un built-in class albero binario, ma è possibile creare il proprio da zero o scaricare uno da Internet.

Albero Altezza

L'altezza di un albero binario è il numero massimo di nodi, escluso il nodo radice, lungo un unico attraversamento verticale attraverso l'albero binario. Ad esempio, un albero binario con un solo nodo avrà un'altezza pari a zero. Un albero binario con un nodo radice con due nodi figli avrebbe avuto una altezza di uno. Se uno di questi nodi figlio aveva il suo nodo figlio, l'albero avrebbe un'altezza di tre.

Teoria

Il modo più semplice per determinare l'altezza di un albero binario in Java è un metodo ricorsivo. Questo metodo accetta un singolo nodo come argomento e restituisce l'altezza dell'albero binario sotto il nodo argomento. Il metodo si chiama di nuovo per ciascuno dei nodi figli del nodo argomento e memorizza il risultato come una variabile intera. Esso confronta le due variabili, che rappresentano l'altezza di ciascuno dei suoi figli, aggiunge uno al più grande dei due variabili e restituisce il risultato. Se il nodo argomento passato al metodo è nullo, il metodo restituisce uno negativo.

Algoritmo

Il seguente metodo Java calcolerà l'altezza di un albero binario. Accetta il nodo radice di un albero binario come argomento. In alternativa, si potrebbe passare un nodo differente dell'albero binario nel metodo per trovare l'altezza dell'albero sotto quel nodo. Il codice seguente presuppone che ogni nodo dell'albero binario è del tipo "BinaryTreeNode" e ciascun nodo contiene metodi che restituiscono i bambini sinistro e destro di tale nodo chiamato "getLeftChild" e "getRightChild."

private int findHeight (BinaryTreeNode currentNode) {
if (currentNode.equals (null)) {

return -1;

}
int leftHeight = findHeight (currentNode.getLeftChild ());
int rightHeight = findHeight (currentNode.getRightChild ());
int greatestHeight = Math.max (leftHeight, rightHeight);
tornare greatestHeight;
}