Java ikke har et binært træ klasse, selvom det er nemt at præsentere en version af datastruktur til at gøre en inorder traversal . A " traversal " af et binært træ er en stereotyp procedure for at besøge hver node på binært træ én gang. En sigte traversal vil gøre dette i sorteret orden . Traversal er ofte implementeret som en slags iterator (ligesom en liste iterator ) eller ved en metode, der vil kalde en callback metode til hver node . Du kan dog gøre det uden at bruge tilbagekald eller iteratorer , i stedet at udskrive til konsollen hver node besøgt. Instruktioner
1
Opret en grundlæggende binær søgning træ klasse. På dette tidspunkt , vil du kun brug for en grundlæggende constructor metode, der initialiserer node værdi og et indstik metode. Indsatsen metode vil krydse et træ og lave 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 instans ( node ) i binært træ , der vil være roden node som enhver anden node , har brug for roden node til at have en værdi, det er normalt bedst at vælge en værdi tæt på medianen af de objekter , du opbevarer , som binære træer skal være så afbalanceret som muligt "" BinaryTree b = new BinaryTree (50) , " . "
3 < . . p > Indsæt knuder i træet i bestemt rækkefølge at bevare balancen , da denne binære træ ikke er auto -balancering dette eksempel oprettes den mindste træet muligt for at opretholde effektivitet "" 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
Move over træet ved hjælp af en sigte traversal den venstre træet gennemskæres først, efterfulgt af roden node , og derefter den rigtige træet er. overkørt. Brug rekursion , koden er blot tre linjer. Men da rekursion tager stakplads , bør det bruges med omhu. Med en lille og afbalanceret binært træ , vil rekursion ikke overflow stakken.
5 < p> Tilføj en ny metode til Java BinaryTree klasse kaldet sigte "" public void sigte () {if (venstre = null !) left.inorder (); . System.out.println ( værdi) ! hvis (højre = null ) right.inorder ( );} ""
6
Ring til sigte metode, efter dine indsatser for at udskrive knuder i sorteret orden . "" b.inorder (); "