Hvordan gjøre Postorder Traversal i en Binary treet i Java

Selv om Java ikke gir et binært tre klasse i standardbibliotekene, er en grunnleggende binærtreet klasse enkle nok til å bli presentert. En "traversering" av en datastruktur som er en algoritme som besøker hver node en gang. Dette er ofte implementert som en slags iterator (mye som en liste iterator) eller metode som vil kalle en tilbakeringing metode for hver node. I Java, for å gjøre en "Postorder" traversering som vil besøke rotnoden siste, ingen tilbakeanrop eller iteratorer er nødvendig. Den traversering funksjonen vil bare skrive ut hver node det besøk til konsollen.

Bruksanvisning

1 Skriv en grunnleggende binært søketre klasse. Det er bare to metoder som trenger å bli understøttet på dette trinn: en grunnleggende konstruktør som initialiserer nodens verdi, og en innsats metode. Innsatsen metoden vil 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);
}
}"" ""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 Opprett en forekomst av binærtreet som vil være rotnoden. Hver node, selv rotnoden, må ha en verdi.

3 Velg en verdi for rotnoden som er et sted i midten av objektene du skal lagre. For eksempel, hvis du lagrer en jevn fordeling av tallene fra 1 til 100, 50 er et godt valg for rotnoden. Binære trær bør være så balansert som mulig, siden ubalansert trær vokser ekstremt høy og er ikke veldig effektivt. ""BinaryTree b = new BinaryTree(50);""

4 Sett noen noder i treet. Siden dette treet er ikke automatisk balansering, for å beholde balansen, noder skal settes inn i en bestemt rekkefølge. Rekkefølgen i dette eksempelet kode er laget for å gjøre den korteste og mest effektive treet mulig. ""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);""

5 Traverse treet, krysser venstre treet først, deretter den høyre treet, og så til slutt rotnoden. Hvis rekursjon brukes til å gjøre Postorder traversering, er metoden bare tre linjer lange. I dette tilfellet vil stabelen bare vokse til høyden av treet. Siden treet er balansert og liten, vil rekursjon ikke renne over stabelen.

6 Legg til ny metode til BinærTre klasse kalt Postorder. Her skrives det bare verdien av hver node som besøkes. ""public void postorder() {
if(left != null) left.postorder();
if(right != null) right.postorder();
System.out.println(value);
}"" ""public void postorder() {
if(left != null) left.postorder();
if(right != null) right.postorder();
System.out.println(value);
}""

7 Skriv ut nodene i Postorder ved å ringe b.postorder metode etter dine innsatser.

""b.postorder();"

Hint

• Siden rekursjon tar stack plass, bør det brukes med forsiktighet. Hvis binærtreet er svært store, bør traversering funksjon gjennomføres iterativt.
• Jo mer komplisert "delete node" -metoden støttes ikke av dette eksempelet klassen.