Hvordan gjøre forhåndsbestilling Traversal i binærtreet i Java

For å gjøre en "traversering" av et binært tre i Java betyr å gjøre en algoritmisk behandling av nodene i en slags orden. En "forhåndsbestilling" 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.

Bruksanvisning

1 Lag en enkel binært søketre klasse som har en grunnleggende konstruktør som initialiserer noden verdi. Også inkludert bør være et innstikk metode for å traversere et tre og opprette en ny node på riktig sted.
""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;

public BinaryTree(int v) {
value = v;
}

// Insert a value into the tree
public void insert(int v) {
if(v < value) {
if(left == null)
left = new BinaryTree(v);
else
left.insert(v);
}

else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}
}""

2 Konstruer rotnoden av binære treet, tilordne den en verdi som er nær gjennomsnittet for de objektene du skal lagre. Dette vil sikre effektivitet, siden binærtreet må være ganske godt balansert. Hvis du lagrer en fordeling av tallene fra 1 til 100, for eksempel, 50 er en god verdi for rotnoden. ""BinaryTree b = new BinaryTree(50);""

3 Sett noder i treet i en bestemt rekkefølge. Den binære tre er ikke automatisk utbalanserende, så setter inn noder i en bestemt rekkefølge bidrar til å opprettholde balansen. Her nodene er stedet å gjøre 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);"" ""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 Gjør en forhåndsbestilling traversering av traversering rotnoden først, deretter venstre treet og endelig den rette treet. Det er lett å gjøre dette rekursivt med en liten binært tre, som det ikke renne over stabelen. Hvis binærtreet er svært store, bør traversering funksjon gjennomføres iterativt.

5 Legg til en ny metode, forhåndsbestilling, til BinærTre klassen. Her metoden skriver bare verdien av hver node som besøkes. ""public void preorder() {
System.out.println(value);
if(left != null) left.preorder();
if(right != null) right.preorder();
}"" ""public void preorder() {
System.out.println(value);
if(left != null) left.preorder();
if(right != null) right.preorder();
}""

6 Ring den nye metoden etter dine innstikk til å skrive ut nodene i forhåndsbestilling. ""b.preorder();"

Hint

• I standardbiblioteker, betyr Java ikke gir et binært tre klasse, men som vist, er det enkelt nok til å skape en grunnleggende binærtreet klasse.