Hoe om te doen Postorder Traversal in een Binary Tree in Java

Hoewel Java biedt geen binaire boom klasse standaard libraries, een eenvoudige binaire boom categorie is eenvoudig genoeg om te worden gepresenteerd.Een "traversal" van een datastructuur is een algoritme dat elk knooppunt keer bezoekt.Dit wordt vaak uitgevoerd als een soort van iterator (net als een lijst iterator) of methode die een callback methode voor elk knooppunt zullen noemen.In Java, om een ​​"postorder" traversal die de root node laatste bezoek doen, geen callbacks of iterators nodig.De traversal functie zal eenvoudig afdrukken elk knooppunt te bezoeken aan de console.

instructies

  1. Schrijf een eenvoudige binaire zoekboom klasse.Er zijn twee methoden die moeten worden ondersteund in deze fase: een basis constructor die waarde van het knooppunt initialiseert en een insert methode.De insert methode zal een boom doorkruisen en maak een nieuw knooppunt in de juiste plaats."" public class BinaryTree {
    BinaryTree verlaten;
    BinaryTree recht;
    int waarde;

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

    // Breng een waarde in de boom
    public void insert (int v) {
    if (v & lt; value) {
    if (links == null)
    links = new BinaryTree (v);
    anders
    left.insert (v);
    }

    anders als (v & gt; value) {
    if (rechts == null)
    rechts = new BinaryTree (v);
    anders
    right.insert (v);

    }} ""

  2. Maak een instantie van de binaire boom, die de root node zal zijn.Elk knooppunt zelfs het hoofdknooppunt, moet een waarde hebben.

  3. Kies een waarde voor de root-knooppunt dat is ergens in het midden van de objecten die je zult opslaan.Bijvoorbeeld, als u het opslaan van een gelijkmatige verdeling van de getallen van 1 tot 100, 50 is een goede keuze voor de root-node.Binaire bomen moeten zo evenwichtig mogelijk zijn, omdat onevenwichtige bomen groeien extreem lang en zijn niet erg effectief "" BinaryTree b = new BinaryTree (50); "."

  4. Steek enkele knooppunten in de boom.Aangezien deze boom niet automatisch in evenwicht brengen, om het evenwicht te behouden knooppunten moet worden opgenomen in een bepaalde volgorde.De volgorde in dit voorbeeld code wordt gemaakt om de kortste en meest efficiënte structuur mogelijk te maken "" 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 de boom, eerst de linker boom doorkruisen, gevolgd door de juiste boom, en dan eindelijk de root node.Als recursie wordt gebruikt om de postorder traversal doen is de werkwijze drie regels lang.In dit geval wordt de stapel alleen groeien op de hoogte van de boom.Omdat de boom is evenwichtig en klein is, zal recursie niet overstromen de stapel.

  6. Voeg een nieuwe methode om de BinaryTree klasse met de naam postorder.Hier, drukt het alleen de waarde van elk knooppunt te bezoeken "" public void postorder () {
    if (links = null!) Left.postorder ().;
    if (rechts = null!) Right.postorder ();
    System.out.println (waarde);
    } ""

  7. Druk de knooppunten in postorder door te bellen met de b.postorder methode na de inserts.

    "" b.postorder (); "

Tips & amp; waarschuwingen

  • Sinds recursie neemt stack ruimte, moet zorgvuldig worden gebruikt Indien.uw binaire boom is erg groot, de traversal functie moet worden iteratief uitgevoerd.
  • De ingewikkelder "delete knooppunt" methode wordt niet ondersteund door dit voorbeeld klasse.
466
0
1
Programmeren In Java