Treedatastrukturopplæring for nybegynnere

Introduksjon

Et tre i programvare er som et biologisk tre, men med følgende forskjeller:

• Det er trukket opp ned.
• Den har bare en rot og ingen stilk.
• Grenene dukker opp fra roten.
• Et punkt der en gren tar av fra en annen gren eller roten kalles noden.
• Hver node har en verdi.

Grenene til programvaretreet er representert med rette linjer. Et godt eksempel på et programvaretre du kanskje har brukt er katalogtreet til harddisken på datamaskinen din.

Det er forskjellige typer trær. Det er det generelle treet som andre trær er avledet. Andre trær er avledet ved å introdusere begrensninger i det generelle treet. For eksempel kan det være lurt å ha et tre der ikke mer enn to grener stammer fra en node; Et slikt tre vil bli kalt et binært tre. Denne artikkelen beskriver det generelle treet og hvordan du får tilgang til alle nodene.

Hyperkoblingen for å laste ned koden er gitt nederst i denne artikkelen.

For å forstå kodeprøvene i denne artikkelen, må du ha grunnleggende kunnskap i JavaScript (ECMASCRIPT). Hvis du ikke har den kunnskapen, kan du få den fra http: // www.bredt nettverk.com/chrysanthusforcha-1/ecmascript-2015-kurs.htm

Det generelle trediagrammet

'A' er rotnoden; det er førstegangsnoden. B, C, D er på den andre linjen; Dette er noder på andre nivå. E, F, G, H, I, J, K er på tredje linje, og de er noder på tredje nivå. En fjerde linje ville ha produsert noder på fjerde nivå, og så videre.

Treegenskaper

- Alle grener for alle nivåer av noder, har en kilde, som er rotnoden.

- Et tre har n - 1 grener, der n er det totale antallet noder. Ovennevnte diagram for det generelle treet har 11 noder og 10 grener.

- I motsetning til med mennesker, der hvert barn har to foreldre, med programvaretreet, har hvert barn bare en av foreldrene. Rotnoden er den største forfedreforelderen. En forelder kan ha mer enn ett barn. Hver node, bortsett fra rotnoden, er et barn.

Treordforråd

• Rotnode: Dette er den høyeste noden i treet, og den har ingen foreldre. Hver annen node har en forelder.
• Bladknuter: En bladknute er en node som ikke har noe barn. De er vanligvis på bunnen av treet og er noen ganger til venstre og/eller høyre side av treet.
• Nøkkel: Dette er verdien av et tre. Det kan være et tall; Det kan være en streng; Det kan til og med være en operatør som + eller - eller x.
• Nivåer: Rotnoden er på første nivå. Barna er på andre nivå; Barna på andre nivå noder er på tredje nivå, og så videre.
• Overordnet node: Hver node, bortsett fra rotnoden, har en overordnet node koblet til den av en gren. Enhver node, bortsett fra rotnoden, er en barneknute.
• Søskenknuter: Søskenknuter er noder som har samme foreldre.
• Sti: Grenene (rette linjer) som kobler en node til en annen, gjennom andre noder, danner en sti. Grenene kan være eller ikke være piler.
• Stamfarnode: Alle de høyere nodene som er koblet til et barn, inkludert foreldre og rotnoden, er forfedre -noder.
• Etterkommerknute: Alle nedre noder koblet til en node, helt ned til tilkoblede blader, er etterkommernoder. Noden det gjelder, er ikke en del av etterkommerne. Noden det gjelder, trenger ikke å være rotnoden.
• Undertree: En node pluss alle etterkommere helt ned til de relaterte bladene, danner en undertrekk. Startnoden er inkludert, og den trenger ikke å være roten; Ellers ville det være hele treet.
• Grad: Antall barn en node har kalles graden av noden.

Krysser alle noder av et tre

Alle nodene til et tre kan nås for å lese eller endre en hvilken som helst verdi av noden. Dette gjøres imidlertid ikke vilkårlig. Det er tre måter å gjøre dette på, som alle innebærer dybde-første gjennomganger som følger:

1) I orden: Enkelt sagt, i denne ordningen, blir venstre undertree krysset først; Deretter er rotnoden tilgjengelig; Deretter blir den rette undertreen krysset. Denne ordningen symboliseres som venstre-> rot-> høyre. Fig 1 er på nytt avspilt her for enkel referanse:

Forutsatt at det er to søsken per node; Så venstre-> root-> høyre midler, du får tilgang til den laveste og venstre noden først, deretter overordnet til noden, og deretter høyre søsken. Når det er mer enn to søsken, ta den første som venstre og resten av høyre noder, som høyre. For det generelle treet over får den nederste venstre undertreet å ha, [EBF]. Dette er en undertree. Forelderen til denne undertreen er en; Så a er deretter tilgjengelig for å ha [ebf] a. Deretter får du tilgang til subtree [GCHI] for å ha en større subtree, [[EBF] A [GCHI]]. Du kan se venstre-> root-> høyre profil som skildrer seg selv. Denne store venstre undertreet vil ha undertreet, [JDK] til sin rett til å fullføre krysset for å oppnå, [[EBF] A [GCHI]] [JDK].

2) Forhåndsbestilling: Enkelt sagt, i denne ordningen får rotnoden først tilgang til, så blir venstre undertree krysset neste. Denne ordningen symboliseres som rot-> venstre-> høyre. Fig 1 er på nytt avspilt her for enkel referanse.

Forutsatt at det er to søsken per node; deretter root-> venstre-> høyre midler, du får tilgang til roten først, deretter det venstre umiddelbare barnet, og deretter det høyre umiddelbare barnet. Når det er mer enn to søsken, ta den første som venstre og resten av høyre noder, som høyre. Det venstre barnet til det venstre barnet er det neste som får tilgang til. For det generelle treet over er rotundertreet [ABCD]. Til venstre for denne undertræren har du undertreet, [EF], og gir tilgangssekvensen, [ABCD] [EF]. Til høyre for denne større undertræren har du to undertrær, [GHI] og [JK], og gir den komplette sekvensen, [ABCD] [EF] [GHI] [JK]. Du kan se root-> venstre-> høyre profil som skildrer seg selv.

3) Post-ordre: Enkelt sagt, i denne ordningen, blir venstre undertree krysset først, så blir høyre undertrekk krysset, og så får roten tilgjengelig. Denne ordningen symboliseres som venstre-> høyre-> rot. Fig 1 er på nytt avspilt her for enkel referanse.

For dette treet er undertrærne, [EFB], [Ghic], [JKD] og [A] som danner sekvensen, [EFB], [Ghic], [JKD] [A]. Du kan se venstre-> høyre-> rotprofil som skildrer seg selv.

Skape treet

Treet ovenfor vil bli opprettet ved hjelp av Ecmascript, som er som den nyeste versjonen av JavaScript. Hver node er en matrise. Det første elementet i hver node -matrise er overordnet til noden, en annen matrise. Resten av elementene i noden er barna i noden, som begynner fra det venstre barnet. Det er et ECMASCRIPT -kart som relaterer hver matrise til den tilsvarende strengen (bokstav). Det første kodesegmentet er:

O = ny matrise ();
A = ny matrise ();
B = ny matrise ();
C = ny matrise ();
D = ny matrise ();
// blader
E = ny matrise (b); F = ny matrise (b); G = ny matrise (c); H = ny matrise (c);
I = ny matrise (c); J = ny matrise (d); K = ny matrise (d);
// legge til innholdet
O [0] = udefinert; O [1] = a;
A [0] = o; A [1] = b; A [2] = C; A [3] = d;
B [0] = a; B [1] = e; B [2] = f;
C [0] = a; C [1] = g; C [2] = H; C [3] = i;
D [0] = a; D [1] = j; D [2] = k;
// Kartlegging av objekter til bokstaver
par = [[a, 'a'], [b, 'b'], [c, 'c'], [d, 'd'], [e, 'e'], [f, 'f'] , [G, 'g'],
[H, 'h'], [i, 'i'], [j, 'j'], [k, 'k']];
mapobj = nytt kart (par);

I ECMASCRIPT kan du få tilgang til en funksjon som er definert nede i programmet. Imidlertid, med variabler, kan du ikke gjøre det. Du har ikke tilgang til en variabel som er definert nede i programmet. Dette er grunnen til at variablene ovenfor er utviklet som vist.

Legg også merke til at over rotnoden A er det en annen node O (ikke null). Det første elementet i denne matrisen (noden) er udefinert, noe som betyr at sin egen forelder er udefinert. Den ekstra noden O er lagt til for å gjøre den kryssende koden enkel.

Det er også et kart. Kartet relaterer hvert utvalg av ett bokstavnavn, til det tilsvarende strengnavnet på en bokstav.

Rekursiv funksjon

For å få tilgang til alle elementene i et tre, trenger du en rekursiv funksjon. En rekursiv funksjon er en funksjon som fortsetter å ringe seg selv til en tilstand er oppfylt.

Å besøke en node betyr ikke nødvendigvis tilgang til noden. Å få tilgang til en node betyr at verdien enten blir lest eller endret. I kodeprøvene til denne artikkelen betyr tilgang til en node å lese og vise verdien (tasten) til noden. I kodeprøvene kan en node besøkes mer enn en gang, men verdien er bare tilgjengelig en gang.

Algoritme og programmering

Det er ett program for hver av de tre kryssende teknikkene.

I orden algoritme og programmering

Her besøkes den laveste og venstre noden først. [EBF], [[EBF] A [GCHI]] og [JDK] undertrær er utviklet for å gi den komplette sekvensen, [[EBF] A [GCHI]] [JDK].

Det er to rekursive funksjoner for dette programmet, der hver ringer den andre. Den viktigste heter FN (Node). Programmet (koden) er kort. Last ned den kombinerte filen nedenfor for detaljkoding.

De tre programmene har samme array -tre (node) oppsett.

Forhåndsbestill algoritme og programmering

Her er det bare en rekursiv funksjon. Det kalles, FN (Node). Her er [ABCD], [EF], [GHI] og [JK] undertrær utviklet for å gi den komplette sekvensen, [ABCD] [EF] [GHI] [JK]. Programmet for dette er også kort.

De tre programmene har samme array -tre (node) oppsett.

Etter ordre algoritme og programmering

Her besøkes den laveste og venstre noden først. [EFB], [Ghic], [JKD] og [A] undertrær er utviklet for å gi den komplette sekvensen, [EFB], [Ghic], [JKD] [A] .

Det er to rekursive funksjoner for dette programmet, der hver ringer den andre. Den viktigste heter FN (Node). Programmet for dette er også kort. Last ned den kombinerte filen nedenfor for detaljert koding.

De tre programmene har samme array -tre (node) oppsett.

Typer trær

Dataprogrammeringstrær er faktisk ikke-lineære datastrukturer. Lineære datastrukturer er lister, matriser, stabler, køer, stabler osv. Et tre med N-noder har N-1-grener. Når antallet grener er lik eller større enn antall noder, oppnås en graf. En graf er egentlig ikke et tre.

Det er programvaretrær, som beskriver oppsett, for eksempel katalogtreet på harddisken til en datamaskin. Mange trær beskriver ikke eksisterende oppsett i det hele tatt. De beskriver faktisk algoritmer. For eksempel er den matematiske algoritmen (x + y) x (x -y) beskrevet av et tre der x er rotnoden, da + og - er umiddelbare barneknuter av roten. x og y er barneknuter av +. x og y er igjen barneknuter av -. Et slikt tre er kjent som et uttrykks tre.

Mange forskjellige typer trær kan kategoriseres i forskjellige overskrifter; slik som binært tre, B-tre, ekspresjons tre osv. Alle av dem er avledet fra det generelle treet.

Noen av trekategoriene er delt inn i ytterligere kategorier. Det binære treet har for eksempel minst det binære søketreet, AVL -treet og det kartesiske treet.

Last ned

Det er gitt tre programmer for denne artikkelen. Det er ett program for in-orden teknikk (algoritme), et annet for forhåndsbestillingsteknikken, og nok en for etterordre-teknikken. Alle av dem har blitt satt i en zip -fil, kalt Traversing. ZIP -filen kan lastes ned på: GitHub.

Konklusjon

Et programvare er som et normalt tre i parken eller skogen. Imidlertid er dataprogrammeringstreet opp ned. Det er forskjellige typer trær. Andre trær er avledet ved å introdusere begrensninger i det generelle treet. Alle nodene til et tre kan nås ved hjelp av en ordre-, forhåndsbestillings- eller postordre-algoritme. Et programvaretre kan produseres av et hvilket som helst dataspråk. ECMASCRIPT er valgt her fordi det er det enkleste dataspråket. Den neste treet du bør studere er det binære treet siden det er den mest populære tredatastrukturen.