For å gjøre en " traversering " av et binært tre i Java betyr å gjøre en algoritmisk behandling av nodene i en slags orden . A " preorder " traversering betyr at rotnoden behandles først , og deretter resten av treets noder behandles rekursivt . Den traversering funksjonen vil bare skrive ut hver node det besøk til konsollen. Instruksjoner
en
Lag en enkel binært søketre klasse som har en grunnleggende konstruktør som initialiserer node verdi. Også inkludert bør være et innstikk metode for å bla i et tre og opprette en ny node på riktig sted . " " public class BinærTre { BinærTre venstre ; BinærTre høyre , int verdi ; offentlig BinærTre ( int v) { value = v ;} //Sett inn en verdi i treet public void insert ( int v ) { if ( v if ( venstre = = null ) venstre = new BinærTre ( v ) , ellers left.insert ( v ); } else if ( v > verdi) {if (høyre == null ) høyre = new BinærTre ( v ) , ellers right.insert ( v ) .;} } } " "
2
Konstruer rotnoden i binært tre , tilordne den en verdi som er nær gjennomsnittet for de objektene du skal lagre Dette vil sikre effektivitet , siden din binære treet må være ganske godt balansert Hvis du lagrer en fordeling av tallene fra 1 til 100, for eksempel , er 50 en god verdi for root node " " BinærTre b = new BinærTre ( 50 ), " . . "
3
Sett nodene i treet i en bestemt rekkefølge . den binære treet er ikke auto- balansering, så sette inn noder i en bestemt rekkefølge bidrar til å beholde balansen . Her nodene sted for å lage en kort og effektivt balansert tre " " 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
en preorder traversering ved traversering rotnoden først, deretter den venstre treet og til slutt den rette treet. det er lett å gjøre dette rekursivt med en liten binært tre , så det ikke koker over bunken. Hvis binært tre er svært stort , bør traversering funksjonen implementeres iterativt .
5
Legg til en ny metode , preorder , til BinærTre klassen . Her metoden bare skriver ut verdien av hver node det besøk . " " public void preorder ( ) { System.out.println (verdi ) ; if ( venstre = null ! ) left.preorder (); if ( høyre = null ! ) right.preorder (); } " "
6
Ring den nye metoden etter dine innsatser å skrive ut nodene i preorder " " b.preorder (); " .
