Strutture di dati efficiente ottimizzare le prestazioni di un programma che lo rende più facile per il programma trovare i dati che ha bisogno. Alberi di ricerca binaria sono una delle strutture dati più efficiente per la ricerca attraverso un set di dati ordinato. Se la struttura dei dati è un albero binario-ricerca organizzato o un albero binario standard, è possibile trovare altezza dell'albero in Java attraverso una funzione ricorsiva semplice.

Struttura ad albero

Un albero binario è costituito da un insieme di nodi interconnessi. Ogni nodo ha tra zero e due nodi figlio. Ogni nodo con l'eccezione del nodo radice ha esattamente un nodo padre. Il nodo radice non ha nessun nodi padre. Java non dispone di un'albero binario built-in classe, ma è possibile crearne di nuovi partendo da zero o scaricarne uno da Internet.

Altezza dell'albero

L'altezza di un albero binario è il numero massimo di nodi, non incluso il nodo radice, lungo un singolo attraversamento verticale attraverso l'albero binario. Ad esempio, un albero binario con un solo nodo avrebbe un'altezza pari a zero. Un albero binario con un nodo principale con due nodi figlio avrebbe un'altezza di uno. Se uno di quei nodi figlio ha avuto un proprio nodo figlio, l'albero sarebbe avere un'altezza di tre.

Teoria

Il modo più semplice per determinare l'altezza di un albero binario in Java è con un metodo ricorsivo. Questo metodo accetta un singolo nodo come argomento e restituisce l'altezza dell'albero binario sotto il nodo di argomento. Il metodo chiama se stessa nuovamente per ciascuno dell'argomento nodi figlio del nodo e archivia il risultato come una variabile integer. Confronta le due variabili, che rappresentano l'altezza di ciascuno dei suoi figli, aggiunge uno al più grande delle due variabili e restituisce il risultato. Se il nodo di argomento passato al metodo è null, il metodo restituisce uno negativo.

Algoritmo

Il seguente metodo Java calcolerà l'altezza di un albero binario. Il nodo radice di un albero binario accetta come argomento. In alternativa, è possibile passare un altro nodo dell'albero binario nel metodo per trovare l'altezza dell'albero sotto tale nodo. Il codice seguente presuppone che ogni nodo dell'albero binario è del tipo "BinaryTreeNode" e ogni nodo contiene metodi che restituiscono i figli sinistro e destro di quel 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);
Return greatestHeight;
}