Att göra en " traversering " av ett binärt träd i Java innebär att göra en algoritmisk behandling av noderna i någon form av ordning . En " förbeställa " traversering innebär att root noden behandlas först , och sedan resten av trädets noder bearbetas rekursivt . Den traversal funktionen kommer helt enkelt skriva ut varje nod den besöker till konsolen . Instruktioner
1
Skapa en enkel binär klass sökträd som har en grundläggande konstruktor som initierar nodens värde . Dessutom ingår bör vara en insats sätt att förflytta sig ett träd och skapa en ny nod i rätt plats. " " public class binaryTREE { binaryTREE vänster , binaryTREE höger , int value ; offentliga binaryTREE ( int v ) { value = v ; } //Sätt ett värde i trädet public void insert ( int v ) {if ( v om ( vänster = = null ) vänster = ny binaryTREE ( v ) , annars left.insert ( v ) ;} else if ( v > värde ) {if ( höger == null ) höger = ny binaryTREE ( v ) , annars right.insert ( v ) ; . } } } " "
2
Konstruera rotnod binära trädet , tilldela det ett värde som är nära medelvärdet för de objekt som du kommer att lagra Detta kommer att säkerställa effektivitet , eftersom din binära träd måste vara ganska väl avvägd Om du lagrar en uppsättning tal från 1 till 100 , till exempel , är 50 ett bra värde för root noden " " binaryTREE b = ny binaryTREE ( 50 ) , " . . " Addera 3
Infoga noder i trädet i en viss ordning . den binära trädet är inte automatisk balansering , så infoga noder i en viss ordning bidrar till att behålla balansen . Här noderna är plats att göra en kort och effektivt balanserat träd " " 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 ) ; " "
4
Gör en preorder traversering genom att korsa rotnoden först , därefter den vänstra trädet och slutligen rätt träd . det är lätt att göra detta rekursivt med en liten binärt träd , eftersom det inte rinner stapeln . Om din binära träd är mycket stor , bör traversering funktionen implementeras iterativt .
5
Lägg till en ny metod , förbeställa , till binaryTREE klassen . här metoden bara skriver ut värdet för varje nod den besöker . " " public void preorder ( ) { System.out.println ( värde ) , om ( vänster = null ! ) left.preorder ( ) , om ( höger = null ! ) right.preorder ( ) ;} " "
6
Ring den nya metoden efter dina inlägg att skriva ut noder i preorder " " b.preorder ( ) ; " .
