strutture dati efficienti ottimizzare 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 di dati più efficiente per la ricerca attraverso un set di dati ordinato . Sia che la vostra struttura dati è un albero binario di ricerca organizzata o un albero binario standard, è possibile trovare l'altezza del albero in Java tramite una semplice funzione ricorsiva . Struttura albero

Un albero binario consiste di 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 ha nodi padre . Java non ha un built-in class albero binario , ma è possibile creare il proprio da zero o scaricarne uno da Internet.
Albero Altezza

L'altezza della un albero binario è il numero massimo di nodi , non compresi il nodo radice , lungo un unico attraversamento verticale attraverso l'albero binario . Per esempio , un albero binario con un solo nodo avrebbe un'altezza pari a zero . Un albero binario con un nodo radice con due nodi figlio avrebbe un'altezza di uno. Se uno di quei nodi figlio aveva il suo nodo figlio , l'albero avrebbe una altezza di tre .
Teoria

Il modo più semplice per determinare l'altezza di un albero binario in Java è con un metodo iterativo . 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 figlio del nodo argomento e memorizza il risultato in una variabile intera . Esso confronta le due variabili , che rappresentano l'altezza di ciascuno dei suoi figli , aggiunge uno alla grande delle due variabili e restituisce il risultato . Se il nodo argomento passato al metodo è null, il metodo restituisce uno negativo .
Algoritmo

Il seguente metodo Java calcolare l'altezza di un albero binario . Si accetta il nodo radice di un albero binario come argomento . In alternativa , si potrebbe passare un diverso nodo dell'albero binario nel metodo per trovare l' altezza dell'albero al di sotto di 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 tale nodo chiamato " getLeftChild " e " getRightChild ".
< p > private int findHeight ( BinaryTreeNode nodoCorrente ) {if ( currentNode.equals ( null) ) {return -1 ; } int leftHeight = findHeight ( currentNode.getLeftChild ()); int rightHeight = findHeight ( currentNode.getRightChild ( ) ) ; int greatestHeight = Math.max ( leftHeight , rightHeight ) ; greatestHeight return; }