Binaire bomen zijn complexe data structuren gebruikt in computer programma's om gegevens op te slaan in het geheugen met behulp van een gemeenschappelijke opslag -algoritme . Door deze soort algoritme , kan data worden opgeslagen in een stabiel patroon , waardoor het ophalen en doorzoeken van gegevens gemakkelijker . Java- programmeurs die zijn ontwerpen van binaire bomen zijn meer dan waarschijnlijk ook het ontwerpen van algoritmen om deze datastructuren doorkruisen . Er zijn drie manieren om binaire bomen doorkruisen : in - orde , pre -order , en post -order . Wat je nodig hebt
Java Development Kit ( JDK ) op Teksteditor
Toon Meer Aanwijzingen
1 Beweeg de binaire boom met behulp van in-order traversal . Ervan uitgaande dat de klasse " BT " vertegenwoordigt een binaire boom , de volgende code laat zien hoe u de boom in - volgorde af te drukken . Elk knooppunt heeft een linker en rechter pointer die wijst naar de linker en rechter knooppunten van de huidige knoop , samen met een gegevensitem dat zijn waarde vertegenwoordigt . De in-order traversal zal het linker knooppunt eerste traverse tot het raken van nul , en de druk van de bovenliggende node voor het doorkruisen van rechts en opnieuw beginnen . Het betekent dat elk knooppunt pas wordt afgedrukt als alle linkerkant kindknopen eerste zijn afgedrukt : public class BT
{ public void Inorder
( Node x ) {
if ( x == null ) { return ; //stopt recursie als er geen Node } inorder
( x.left ) ; //altijd doorkruisen links firstprint x.data ; //de gegevens een keer af te drukken het linker knooppunt returnsinOrder ( x.right ) ; //traverse rechts } kopen van 2 Traverse de boom in de pre -order . Deze volgorde is vergelijkbaar met in - orde , behalve dat het afdrukken van het knooppunt komt vóór elke traversal . Dus , zal het knooppunt zijn waarde af te drukken , en vervolgens doorkruisen vertrokken . Dan, wanneer de recursie terugkeert naar het knooppunt na verplaatsing links , het knooppunt zal dan doorkruisen rechts . Dit betekent dat de node zelf altijd zal drukken voordat elk kind knooppunten afdrukken : public void preorder
( Node x ) {
if ( x == null ) { return ; //stopt recursie als er is geen Node } afdruk x.data
; //printinOrder ( x.left ) ; //traverse leftinOrder ( x.right ) ; //traverse rechts }
3 Traverse de boom post- order . Dit is het tegenovergestelde van de pre-order traversal . Een knooppunt zal altijd kijken naar zijn linker of rechter Knooppunten voor het afdrukken zelf , wat betekent dat alle overige onderliggende knooppunten eronder zal eerst af te drukken : public void Postorder
( Node x ) {
if ( x == null ) { return ; //stopt recursie als er geen Node } inorder
( x.left ) ; //traverse leftinOrder ( x.right ) ; //traverse rightprint x.data ; //afdruk }
|
