Selvom Java giver ikke et binært træ klasse i standard biblioteker , en grundlæggende binært træ klasse er enkle nok til at blive præsenteret. A " traversering " af en datastruktur er en algoritme , der besøger hver node gang . Dette er ofte implementeret som en slags iterator (meget gerne en liste iterator ), eller metode, der vil kalde en callback metode til hver node . I Java , til at gøre en " Postorder " traversal , som vil besøge rodnoden sidste ingen tilbagekald eller iteratorer er nødvendige. Gennemkrydsningen Funktionen vil simpelthen udskrive hver node det besøger til konsollen. Instruktioner
1
Skriv en grundlæggende binær søgning træ klasse. Der er kun to metoder, der har brug for at blive støttet i denne fase : en grundlæggende constructor , der initialiserer node værdi, og et indstik metode. Indsatsen metode vil krydse et træ og oprette en ny node på det rigtige sted . "" public class BinaryTree { BinaryTree til venstre; BinaryTree højre , int værdi offentligt BinaryTree ( int v) {value = v ;} //Indsæt en værdi ind i træet public void insert ( int v) {if (v if ( venstre = = null) venstre = new BinaryTree ( v) , ellers left.insert (v );} else if ( v> værdi) {if (højre == null) ret = new BinaryTree ( v) , ellers right.insert ( v) ; . }} ""
2
Opret en instans af binært træ , som vil være roden node Hver node , selv roden node , skal have en værdi
< br . > 3
Vælg en værdi for roden node, der er et sted i midten af de objekter, du vil være opbevaring . for eksempel, hvis du gemmer en jævn fordeling af tal fra 1 til 100 50 er et godt valg for roden node Binary træer skal være så afbalanceret som muligt, da ubalancerede træer vokser ekstremt høj og er ikke særlig effektive "" BinaryTree b = new BinaryTree (50) , " . ".
4
Insert nogle knuder ind i træet. Da dette træ ikke er auto- balancing , at bevare balancen , bør knuder indsættes i en bestemt rækkefølge . den rækkefølge dette eksempel kode er udformet til at gøre den korteste og mest effektive tree muligt. "" b . indsats ( 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 træet , gennemkører venstre træet først, efterfulgt af den rigtige træet , og derefter endelig rodnoden . Hvis rekursion anvendes til at gøre det Postorder traversering metoden er kun tre linjer lang . i dette tilfælde vil kun stakken vokse til højden af træet . Da træet er afbalanceret og små , rekursion vil ikke overløb stakken.
6
Tilføj ny metode til BinaryTree klasse kaldet Postorder . Her er det kun udskriver værdien af hver node , det besøger . "" public void Postorder () {if (venstre ! = null ) left.postorder ( ), og hvis (højre = null) right.postorder (); ! System.out.println ( værdi) ;} ""
7
Print knuder i Postorder ved at ringe til b.postorder metode, efter dine indstik "" b.postorder (); " .