Java heeft geen binaire boom klasse , al is het eenvoudig om een versie van de datastructuur te presenteren aan doen een inorder traversal . Een " traversal " van een binaire boom is een stereotiepe procedure voor een bezoek aan elk knooppunt op de binaire boom een keer. Een inorder traversal zal dit doen in gesorteerde volgorde . Traversal wordt vaak uitgevoerd als een soort iterator (zoals een lijst iterator ) of door een methode die een callback-methode voor elk knooppunt zullen noemen . U kunt echter , doe dit zonder gebruik te maken callbacks of iterators , in plaats daarvan afdrukken naar de console elk knooppunt bezocht. Instructies
1 Maak een eenvoudige binaire zoekboom klasse . Op dit punt, hoeft u alleen maar een basis constructor methode die waarde van het knooppunt en een insert methode initialiseert . De insert methode zal een boom doorkruisen en maak een nieuw knooppunt op de juiste plaats . " " public class BinaryTree { BinaryTree links; BinaryTree rechts; int waarde ; openbare BinaryTree ( int v ) { waarde = v ; } //Plaats een waarde in de boom public void insert ( int v ) { if ( v if ( links = = null ) links = new BinaryTree ( v ) ; anders left.insert ( v ) ; } else if ( v > value ) { if ( rechts == null ) rechts = new BinaryTree ( v ) ; anders right.insert ( v ) ; . . } } } " " kopen van 2 Maak de instantie ( knooppunt ) van de binaire boom die de root- knooppunt zal zijn als elk ander knooppunt , de wortel knooppunt moet een waarde hebben het is meestal het beste tot een waarde dicht bij de mediaan van de objecten die je opslaat kiest , als binaire bomen zo evenwichtig mogelijk moet zijn " " BinaryTree b = new BinaryTree ( 50 ) ; " . "
3 < . . p > Steek nodes in de boom in specifieke om het evenwicht te behouden , omdat dit binaire boom is niet auto - balancing dit voorbeeld maakt de kleinste boom mogelijk om de efficiëntie te handhaven " " b.insert ( 20 ) ; b.insert ( 40 ) ; b.insert ( 10 ) ; b.insert ( 5 ) ; b.insert ( 45 ) ; b.insert ( 70 ) ; b.insert ( 60 ) ; b.insert ( 80 ) ; b.insert ( 55 ) ; b.insert ( 85 ) ; " "
Move 4 in de boom met behulp van een inorder traversal de linker boom is eerst doorlopen , gevolgd door de wortel knooppunt , en vervolgens de juiste boom is . doorkruist . gebruik recursie , de code is slechts drie lijnen . Maar omdat recursie neemt stack ruimte , het moet zorgvuldig worden gebruikt . Met een klein en evenwichtig binaire boom , recursie zal niet een stack overflow .
5 Voeg een nieuwe methode om de Java BinaryTree klasse met de naam ommet " " public void ommet ( ) { if ( links = null ! ) left.inorder ( ) ; . System.out.println ( waarde ) ; ! if ( rechts = null ) right.inorder ( ) ;} " "
6 Roep de inorder methode na je voegt naar de knooppunten in gesorteerde volgorde af te drukken . " " b.inorder ( ) ; "
|
