Sådan Gør Postorder Traversal i et binært træ i Java

Selvom Java giver ikke et binært træ klasse i standardindstillingerne biblioteker, en grundlæggende binært træ klasse er enkel nok til at blive præsenteret.A "traversal" af en datastruktur er en algoritme, der besøger hvert knudepunkt gang.Dette er ofte implementeret som en slags iterator (meget ligesom en liste iterator) eller metode, der vil kalde en callback metode til hvert knudepunkt.I Java, til at gøre en "Postorder" traversal, som vil besøge rodnoden sidst, er det ikke nødvendigt tilbagekald eller iteratorer.Den traversal Funktionen vil simpelthen udskrive hver node det besøg til konsollen.

Instruktioner

  1. Skriv en grundlæggende binær søgning træ klasse.Der er kun to metoder, der skal støttes på dette stadium: en grundlæggende constructor, der initialiserer node værdi, og en indsats fremgangsmåde.Indsatsen metode vil krydse et træ og oprette en ny knude i det korrekte sted."" public class BinaryTree {
    BinaryTree venstre;
    BinaryTree højre;
    int værdi;

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

    // Indsæt en værdi ind i træet
    public void indsats (int v) {
    hvis (v & lt; værdi) {
    hvis (venstre == null)
    venstre = ny BinaryTree (v);
    andet
    left.insert (v);
    }

    ellers hvis (v & gt; værdi) {
    hvis (højre == null)
    højre = nyt BinaryTree (v);
    ellers
    right.insert (v);
    }
    } ""

  2. Opret en forekomst af binært træ, som vil være roden node.Hver node, selv rodnoden, skal have en værdi.

  3. Vælg en værdi for rodknuden der er et sted i midten af ​​de objekter, du vil blive lagring.For eksempel, hvis du opbevare en jævn fordeling af tal fra 1 til 100, 50 er et godt valg for roden node.Binære træer skal være så afbalanceret som muligt, da ubalancerede træer vokser ekstremt høje og ikke er meget effektive "" BinaryTree b = ny BinaryTree (50), "."

  4. indsætte nogle knuder i træet.Da dette træ er ikke auto-balancing, for at bevare balancen, knuder bør indsættes i en bestemt rækkefølge.Rækkefølgen i dette eksempel kode er udformet til at gøre den korteste og mest effektive træ muligt "" 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 træet, gennemkører venstre træet først, efterfulgt af den rigtige træet, og så endelig roden node.Hvis rekursion bruges til at gøre det Postorder traversering fremgangsmåden er kun tre linjer lang.I dette tilfælde vil kun stakken vokser til højden af ​​træet.Da træet er afbalanceret og små, vil rekursion ikke flyde 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 () {
    hvis (venstre = null!) Left.postorder (.);
    hvis (= null rigtige!) Right.postorder ();
    System.out.println (værdi);
    } ""

  7. Udskriv knuder i Postorder ved at kalde b.postorder metoden efter dine skær.

    "" b.postorder (); "

Tips & amp; Advarsler

  • Siden rekursion tager stak plads, bør det bruges omhyggeligt If.din binært træ er meget store, traversal funktionen bør gennemføres iterativt.
  • Jo mere kompliceret "slet node" metoden er ikke understøttet af dette eksempel klasse.
953
0
1
Java Programmering