Effektiv datastrukturer optimalisere et program ytelse ved å gjøre det enklere for programmet å finne dataene den trenger. Binære søk trær er en av de mest effektive datastrukturer for å søke gjennom et ordnet datasett. Enten datastruktur er en organisert binær - søketre eller en standard binært tre , kan du finne treets høyde i Java gjennom en enkel rekursiv funksjon . Trestruktur

binærtreet består av et sett av sammenkoblede noder. Hver node har mellom null og to barn noder . Hver node med unntak av rotnoden har nøyaktig en foreldrenode . Rotnoden har ingen foreldre noder. Java har ikke en innebygd binært tre klassen , men du kan lage dine egne fra bunnen av eller laste ned en fra Internett .
Trehøyden

Høyden et binært tre er det maksimale antall noder , ikke inkludert root node, langs en enkelt vertikal traversering gjennom binære treet . For eksempel vil et binært tre med bare en node ha en høyde på null. Et binært tre med en rotnode med to barn noder vil ha en høyde på en. Hvis en av disse underordnede noder hadde sitt eget barn node, vil treet ha en høyde på tre.
Theory

Den enkleste måten å bestemme høyden av et binært tre i Java er en rekursiv metode. Denne metoden kan brukes med en enkelt node som argument og returnerer høyden på binærtreet under argumentet node. Metoden kaller seg igjen for hver av argumentet node sin underordnede noder og lagrer resultatet som et heltall variabel. Den sammenligner de to variable , som representerer høyden av hver av sine barn , legger man til den største av de to variablene og returnerer resultatet . Hvis argumentet node gått inn i metoden er null, returnerer metoden negativ en.
Algoritme

Følgende Java metoden vil beregne høyden på et binært tre . Det aksepterer rotnoden av et binært tre som et argument . Alternativt kan passerer en forskjellig node i det binære tre inn i metoden for å finne høyden av treet under den noden . Følgende kode legger til grunn at hver node i det binære treet er av typen " BinaryTreeNode " og hver node inneholder metoder som returnerer venstre og høyre barn av den noden som kalles " getLeftChild " og " getRightChild . "
< p> 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 ), tilbake greatestHeight ;} ​​