at gøre en " traversal " af et binært træ i Java betyder at gøre en algoritmisk behandling af knuder i en slags orden. En " preorder " traversal betyder at rodnoden behandles først , og derefter resten af træets knuder behandles rekursivt . Gennemkrydsningen Funktionen vil simpelthen udskrive hver node det besøger til konsollen. Instruktioner
1
Opret en simpel binær søgning træ klasse, der har en grundlæggende konstruktør , der initialiserer node værdi. Også inkluderet bør være en insert metode til at 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
Construct roden node i binært træ , tildele den en værdi, der er tæt på gennemsnittet for de objekter , du vil være opbevaring Dette vil sikre effektivitet, da Deres binært træ har brug for at være temmelig velafbalanceret Hvis du gemmer en fordeling af tal fra 1 til 100 , for eksempel, er 50 en god værdi for root node "" BinaryTree b = new BinaryTree (50) , " . ".
3
Indsæt noder til træet i en bestemt rækkefølge . den binære træ er ikke auto- balancing , så indsætte noder i en bestemt rækkefølge med til at bevare balancen . Her knudepunkter er plads at gøre en kort og effektivt balanceret træ " " 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
Har en preorder traversal ved gennemkører rodknuden først, derefter den venstre træet og endelig den rigtige træet . det er nemt at gøre dette rekursivt med en lille binært træ , da det ikke løber stakken . Hvis binære træ er meget store, bør gennemkrydsningen funktionen implementeres iterativt .
5.
Tilføj en ny metode , preorder , at BinaryTree klassen. Her metoden kun udskriver værdien af hver node , det besøger . "" public void preorder () { System.out.println (værdi ), hvis (venstre = null !) left.preorder ( ), og hvis (højre = null !) right.preorder ( );} ""
6
Ring den nye metode, efter dine indstik at udskrive noder i preorder "" b.preorder (); " .