Effektive datastrukturer optimere et programs ydeevne ved at gøre det lettere for programmet for at finde de data, den har brug for . Binære søgetræer er en af de mest effektive datastrukturer til at søge gennem en ordnet datasæt . Uanset om din datastruktur er en organiseret binary- search træ eller en standard binært træ , kan du finde træets højde i Java ved hjælp af en simpel rekursiv funktion . Træstruktur
Et binært træ består af et sæt af indbyrdes forbundne knudepunkter . Hver node har mellem nul og to underordnede noder. Hvert knudepunkt med undtagelse af rodknuden har præcis én forælder node . Rodknuden har ingen forælder noder. Java har ikke en indbygget binært træ klasse, men du kan oprette din egen fra bunden eller hente en fra internettet.
Træhøjde
højde et binært træ er det maksimale antal knuder , herunder ikke rodnoden , langs en enkelt lodret traversal gennem binært træ . For eksempel ville et binært træ med kun én node har en højde på nul . Et binært træ med en rodnoden med to barn noder ville have en højde på én . Hvis en af disse barn noder havde sin egen barneknudepunkt ville træet have en højde på tre.
Theory
Den enkleste måde at bestemme højden af et binært træ i Java er med en iterativ proces . Denne metode accepterer en enkelt node som argument og returnerer højden af binært træ under argumentet knudepunktet. Metoden kalder sig igen for hver af argumentet nodens barn noder og gemmer resultatet som et heltal variabel. Den sammenligner de to variabler , der repræsenterer højden af hver af sine børn , tilføjer den ene til den største af de to variabler og returnerer resultatet . Hvis argumentet node passeret ind i metoden er nul, returnerer metoden negativ.
Algoritme
Følgende Java metode vil beregne højden af et binært træ. Det accepterer roden node i et binært træ som et argument. Alternativt kan man passere en anden node i binært træ i fremgangsmåden at finde højden af træet under dette knudepunkt . Følgende kode antager, at hvert knudepunkt i binært træ er af typen " BinaryTreeNode " og hvert knudepunkt indeholder metoder der returnerer venstre og højre børn i denne node kaldet " 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 ) tilbagevenden greatestHeight ;}
