Effektiv datastrukturer optimera en programmets prestanda genom att göra det lättare för programmet att hitta de uppgifter den behöver . Binära sökträd är en av de mest effektiva datastrukturer för att söka igenom en ordnad datamängd . Oavsett om din datastruktur är en organiserad binär - sökträd eller en vanlig binärt träd , kan du hitta trädets höjd i Java genom en enkel rekursiv funktion . Trädstruktur
Ett binärt träd består av en uppsättning av sammankopplade noder. Varje nod har mellan noll och två underordnade noder . Varje nod med undantag för rotnoden har exakt en modernod . Rotnoden har inga överordnade noder . Java har inte en inbyggd klass binärt träd , men du kan skapa dina egna från scratch eller hämta en från Internet .
Trädhöjd
höjd ett binärt träd är det maximala antalet noder , exklusive rotnoden , längs en enda vertikal förflyttning genom den binära trädstrukturen . Till exempel skulle ett binärt träd med endast en nod ha en höjd av noll. Ett binärt träd med en rotnod med två underordnade noder skulle ha en höjd av en . Om någon av dessa barnnoder hade sitt eget barn nod , skulle trädet ha en höjd av tre .
Teori
Det enklaste sättet att bestämma höjden av ett binärt träd i Java är med en iterativ metod . Denna metod accepterar en enda nod som ett argument och returnerar höjden av den binära trädstrukturen nedanför argumentet noden. Metoden kallar sig igen för varje argument nodens barn noder och lagrar resultatet som ett heltal variabel . Den jämför de två variablerna , som representerar höjden av var och en av dess barn , tillägger en mot den större av de två variablerna och returnerar resultatet . Om argumentet noden skickas till metoden är null , returnerar metoden negativa ett .
Algoritm
Följande Java metod kommer att beräkna höjden av ett binärt träd . Den accepterar rotnoden av ett binärt träd som ett argument. Alternativt kan du skicka en annan nod i binärt träd i metoden för att hitta höjden på trädet under den noden . Följande kod förutsätter att varje nod i den binära trädstrukturen är av typen " BinaryTreeNode " och varje nod innehåller metoder som returnerar de vänstra och högra barn till denna nod kallas " getLeftChild " och " 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 ) , avkastning greatestHeight ; } Addera
