Binær tre forhåndsbestill gjennomgang i java
Dette er faktisk et binært tre. Et binært tre er et tre der hver node har høyst to barneknuter. Hvis en node bare har en barneknute, bør den noden gjøres til venstre node. Hvis den har begge barna, er det en venstre node og en høyre node.
Treordforråd
Forklaring av trekryssing gjøres ved hjelp av tre -ordforråd.
Rotnode: Hver node i et tre har en forelder bortsett fra rotnoden.
Bladknuter: Sluttknutene er bladnoder. En bladknute har ikke noe barn.
Nøkkel: Dette er verdien av en node. Det kan være en primitiv datatype eller et tegn. Det kan også være en operatør, e.g., + OT - .
Nivåer: Et tre er organisert i nivåer, med rotnoden på første nivå. Nodene kan tenkes i horisontale nivåer. Treet ovenfor har fire nivåer.
Overordnet node: Rotnoden er den eneste noden som ikke har foreldre. Enhver annen node har en overordnet node.
Søskenknuter: Barna til en bestemt node er søskenknuter.
Sti: En sti er en streng med noder og deres enkeltgrener.
Stamfarnode: Alle de høyere nodene som er koblet til et barn, inkludert overordnede og rotnoden, er forfedre -noder.
Etterkommerknute: Alle nedre noder, koblet til en bestemt node, helt ned til tilkoblede blader, er etterkommernoder. Den aktuelle noden er ikke en del av etterkommerne. Den aktuelle noden trenger ikke å være rotnoden.
Undertree: En node pluss alle dens etterkommere, helt ned til de relaterte bladene, danner en undertree. Startnoden er inkludert, og den trenger ikke å være roten; Ellers ville det være hele treet.
Grad: Noden til et binært tre kan ha ett eller to barn. Hvis en node har ett barn, sies graden å være en. Hvis den har to barn, sies graden å være to.
Denne artikkelen forklarer hvordan du kan krysse et binært tre på en forhåndsbestillingsmote, ved hjelp av Java-språket.
Artikkelinnhold
- Traversal Model
- Traversal -tilnærmingen illustrert
- Java -klasser
- Main () -metoden
- Konklusjon
Traversal Model
Bestillinger
Det minste typiske undertræren til et binært tre består av en foreldrode og to barneknuter. Barneknuter er søsken som består av venstre barneknute og høyre barneknute. En riktig barneknute kan være fraværende.
Forhåndsbestille
Foreldreknuten blir besøkt først med denne bestillingen, deretter venstre node, og deretter den høyre noden. Hvis den venstre noden har sin egen undertree, vil alle undertre -nodene bli besøkt først før høyre node blir besøkt. Hvis den rette noden har sin egen undertrekk, vil all undertree bli besøkt til slutt. Når du besøker en undertree, følges forhåndsbestillingsskjemaet for foreldre-venstre-høyre-høyre for hver trekant på tre noder. Hvis en node bare har ett barn, noe som betyr at det ikke er noen ekte trekant, bør det eneste barnet betraktes som venstre node mens den høyre noden er fraværende.
Postordre
Den venstre noden besøkes først med denne bestillingen, deretter den høyre noden, og deretter overordnede noden. Hvis den venstre noden har sin egen undertree, vil alle undertre -nodene bli besøkt først før høyre node blir besøkt. Hvis den rette noden har sin egen undertree, vil all undertree bli besøkt for det andre før foreldrene blir besøkt. Når du besøker en undertree, følges etterordrenes ordning med venstre-høyre-foreldre for hver trekant på tre noder.
I rekkefølge
Den venstre noden besøkes først med denne bestillingen, deretter overordnede noden, og deretter den høyre noden. Hvis den venstre noden har sin egen undertree, vil alle undertree noder bli besøkt først før foreldroden blir besøkt. Hvis den rette noden har sin egen undertrekk, vil all undertree bli besøkt til slutt. Når du besøker en undertree, følges etterordningen med venstre-foreldre-høyre for hver trekant på tre noder.
I denne artikkelen er bare forhåndsbestillingsskjemaet illustrert.
Rekursjon eller iterasjon
Forhåndsbestillingsordningen kan implementeres enten ved hjelp av rekursjon eller iterasjon. I denne artikkelen er den eneste rekursjonen illustrert.
Traversal -tilnærmingen illustrert
I denne artikkelen brukes forhåndsbestillingsordningen og rekursjonen. Ovennevnte diagram vil bli brukt. Diagrammet er blitt spilt ut her for enkel referanse:
I dette avsnittet brukes dette diagrammet til å vise sekvensen av verdier (bokstaver) som vises (tilgjengelig), ved hjelp av forhåndsbestillingsskjemaet og rekursjonen. Bokstavene a, b, c, etc., er verdiene (nøklene) til de forskjellige nodene.
Forhåndsbestill tilgang til treet begynner fra roten. Så A er tilgang først. A har to barn: B (venstre) og C (høyre). Forhåndsbestilling er foreldre til venstre. Så B er tilgjengelig neste. Hvis B aldri hadde barn, ville C fått tilgang til neste. Siden B har barn: D (venstre) og E (høyre), må det venstre barnet nås neste gang. Husk at forhåndsbestilling er foreldre-venstre-høyre. Etter at B, er forelderen fått tilgang til, må det venstre barnet, d, nås neste gang, i samsvar med foreldre-venstre-høyre-høyrebarnet.
Trekanten for overordnede noden, B, er BDE. I denne trekanten har foreldroden, etterfulgt av venstre-barn-noden, nettopp fått tilgang til. Å få tilgang til alle noder av trekanten må fullføres først. Så den neste noden som skal nås er det rette barnet til node B, som er e.
Nå er Triangle BDE en undertrekk, som ledes av node B. På dette tidspunktet har node B og trekanten blitt åpnet helt. Node B er det venstre barnet til Node A. Tilgangen til node B og dens undertrekk er nettopp fullført. Etter at foreldre-venstre-høyre, etter venstre barn, er det tilgjengelig node B, må det høyre barnet til foreldre A, C, nås neste.
Trekanten som C fører er CFG. C er forelderen, F er venstre barn, og G er det høyre barnet. Så så snart C har fått tilgang til, må F nå tilgang. F har også et barn, h. Så så snart F har fått tilgang til, må det venstre barnet, H, nås av foreldrenes venstre-høyre-regelen.
Etter det ville F og dens undertrekk blitt åpnet fullstendig. På det tidspunktet ville det ikke være noe spørsmål om å få tilgang til F igjen. F er venstre barn av C, som har et riktig barn, g. Etter at det venstre barnet har fått tilgang til det, må det nå tilgang.
Og slik er tilgangssekvensen: ABDECFHG.
Java -klasser
Treet er på nytt her for enkel referanse:
Node
brev) av noden. Det skal også ha to andre egenskaper som heter venstre og høyre. Venstre eiendom vil bli tildelt en barneknute hvis noden har et venstre barn. Den rette eiendommen vil bli tildelt “A” barneknuten hvis noden har “A” riktig barn.
Nodeklassen trenger en konstruktør som vil lage nodeobjektet og tilordne en verdi til nøkkelen. Koden for klassen er:
Klasseknute
Char Key;
Node venstre, høyre;
offentlig node (char verdi)
nøkkel = verdi;
venstre = høyre = null;
Når en node nettopp er opprettet, har den ikke noe barn. Det er grunnen til at venstre og høyre egenskaper blir tildelt null. I hovedmetoden (), hvis en bestemt node har et venstre barn, vil barnet bli opprettet og tildelt venstre egenskap til den aktuelle noden. Hvis en bestemt node har et riktig barn, vil barnet bli opprettet og tildelt riktig egenskap til den aktuelle noden.
Treklassen
Koden for treklassen er:
klasse BinaryTree
Nodrot;
BinaryTree ()
root = null;
Treklassen indikerer roten. Den har en eiendom som heter rot, som er for rotnoden. Den har en konstruktør uten noen parametere. Denne konstruktøren tildeler null til roten. Når et tre nettopp er opprettet, har det ingen node, og det er grunnen til at eiendomsroten er null. Den første noden som er opprettet vil være rotnoden, og den vil bli tildelt denne egenskapen, root. Derfra vil treet vokse i Main () -metoden (se nedenfor).
BinaryTree -klassen har metodene, forhåndsbestill () og main () se nedenfor.
Forhåndsbestillingsmetoden
Dette er kjernen i programmet, selv om Main () -metoden også er viktig. Forhåndsbestillingsmetoden implementerer foreldre-venstrebarnets-right-regelen. Dette er en rekursiv funksjon, hvis kode er:
void forhåndsbestilling (node node)
if (node == null)
komme tilbake;
// Få tilgang til overordnede noden
System.ute.trykk (node.tast + "->");
// Få tilgang til venstre barn
Forhåndsbestilling (node.venstre);
// Få tilgang til det rette barnet
Forhåndsbestilling (node.Ikke sant);
På slutten av treet Traversal vil ingen node krysse, så verdien av en hvilken som helst node vil være null. Dette står for den første uttalelsen i forhåndsbestillingsfunksjonen. Den andre uttalelsen skriver ut nøkkelen til den gjeldende noden. Den tredje uttalelsen minner om den samme forhåndsbestillingsfunksjonen med venstre barneknute. Neste og siste uttalelse minner om forhåndsbestillingsfunksjonen med riktig barneknute. På denne måten blir hele treet krysset.
Når du viser sekvensen, A-> B-> D, etter at B er åpnet, “Forhåndsbestilling (node.til høyre) ”kreves til node C, men reservert. Etter at D er tilgjengelig, “Forhåndsbestilling (node.høyre) ”kreves til node e. Oppfordringen til node C, som ble reservert, utføres etter det. Denne forklaringen gjelder riktig gren av hele treet.
Og slik skal utgangssekvensen være: a-> b-> d-> e-> c-> f-> h-> g .
Main () -metoden
Hovedmetoden bygger treet ved å tilordne nye noder med nøklene til en foreldrodes venstre eller høyre eiendom. For det første opprettes et tomt tre. På slutten av Main () -metoden kalles forhåndsbestillingsmetoden en gang. Siden det er en rekursiv funksjon, vil den fortsette å ringe seg til hele treet har blitt krysset. Koden er:
public static void main (String [] args)
// Lag treobjekt uten noen node
BinaryTree Tree = New BinaryTree ();
// Lag noder for treet
tre.root = ny node ('a');
tre.rot.venstre = ny node ('B');
tre.rot.høyre = ny node ('C');
tre.rot.venstre.venstre = ny node ('d');
tre.rot.venstre.høyre = ny node ('e');
tre.rot.Ikke sant.venstre = ny node ('f');
tre.rot.Ikke sant.høyre = ny node ('g');
tre.rot.Ikke sant.venstre.venstre = ny node ('h');
// Forhåndsbestill traversal
System.ute.println ("forhåndsbestill krysset");
tre.forhåndsbestilling (tre.rot);
System.ute.println ();
Alle ovennevnte koder kan settes sammen i ett program for testing.
Utgangen er:
A-> b-> d-> e-> c-> f-> h-> g->
Den siste -> kan ignoreres.
Konklusjon
Det binære treet forhåndsbestill krysset i Java, som bruker rekursjon, har to klasser. Den har nodeklassen og binærtree -klassen. Nodeklassen har en eiendom for nøkkelen. Den har også to nodeegenskaper for venstre barneknute og høyre barneknute. BinaryTree -klassen har to metoder: metoden forhåndsbestilling () og hovedmetoden (). Forhåndsbestilling () -metoden implementerer foreldre-venstrebarnets-rightchild-ordningen rekursivt. Hovedmetoden () metoden bygger treet ved å tilordne nye noder med nøklene som venstre og høyre barn til overordnet noder.
Problemet med den rekursive algoritmen for forhåndsbestilling er at hvis treet er for stort, kan minnet bli kort. For å løse dette problemet, bruk den iterative algoritmen - se senere.