Vadnica za strukturo drevesnih podatkov za začetnike

Uvod

Drevo v programski opremi je kot biološko drevo, vendar z naslednjimi razlikami:

• Narisano je na glavo.
• Ima samo eno korenino in brez stebla.
• Veje se pojavijo iz korena.
• Točka, ko veja vzleti z druge veje ali koren, se imenuje vozlišče.
• Vsako vozlišče ima vrednost.

Podružnice drevesa programske opreme so predstavljene z ravnimi črtami. Dober primer drevesa programske opreme, ki ste ga morda uporabili, je drevo imenikov trdega diska vašega računalnika.

Obstajajo različne vrste dreves. Obstaja splošno drevo, iz katerega izhajajo druga drevesa. Druga drevesa so pridobljena z uvedbo omejitev v splošno drevo. Na primer, morda boste želeli drevo, kjer iz vozlišča ne izhajata več kot dve veji; takemu drevesu bi rekli Binarno drevo.  Ta članek opisuje splošno drevo in kako dostopati do vseh njegovih vozlišč.

Hiperpovezava za prenos kode je navedena na dnu tega članka.

Če želite razumeti vzorce kode v tem članku, morate imeti osnovno znanje JavaScript (ECMAScript). Če tega znanja nimate, ga lahko dobite na http: // www.široko omrežje.com / ChrysanthusForcha-1 / ECMAScript-2015-Course.htm

Diagram splošnega drevesa

'A' je korensko vozlišče; je vozlišče prve stopnje. B, C, D so v drugi vrstici; to so vozlišča druge stopnje. E, F, G, H, I, J, K so v tretji vrstici in so vozlišča tretje stopnje. Četrta vrstica bi ustvarila vozlišča četrte ravni itd.

Lastnosti dreves

- Vse veje za vse ravni vozlišč imajo en vir, to je korensko vozlišče.

- Drevo ima N - 1 vej, kjer je N skupno število vozlišč. Zgornji diagram za splošno drevo ima 11 vozlišč in 10 vej.

- Za razliko od ljudi, kjer ima vsak otrok dva starša, ima pri drevesu programske opreme vsak otrok samo enega starša. Koreninsko vozlišče je največji nadrejeni roditelj. Starš ima lahko več kot enega otroka. Vsako vozlišče, razen korenskega, je podrejeno.

Drevesni besednjak

• Root vozlišče: To je najvišje vozlišče v drevesu in nima nadrejenega. Vsako drugo vozlišče ima nadrejenega.
• Listna vozlišča: Listno vozlišče je vozlišče, ki nima otroka. Običajno so na dnu drevesa, včasih pa na levi in ​​/ ali desni strani drevesa.
• Ključ: To je vrednost drevesa. Lahko je številka; lahko je niz; lahko je celo operator, kot je + ali - ali x.
• Ravni: Koreninsko vozlišče je na prvi ravni. Njeni otroci so na drugi stopnji; Otroci vozlišč druge stopnje so na tretji ravni itd.
• Nadrejeno vozlišče: Vsako vozlišče, razen korenskega, ima nadrejeno vozlišče, povezano z vejo. Vsako vozlišče, razen korenskega, je podrejeno vozlišče.
• Vozlišča sorojencev: Vozlišča sorodnikov so vozlišča z istim nadrejenim.
• Pot: Veje (ravne črte), ki povezujejo eno vozlišče z drugim, skozi druga vozlišča tvorijo pot. Veje so lahko puščice ali ne.
• Vozlišče prednikov: Vsa višja vozlišča, povezana z otrokom, vključno s starševskim in korenskim vozliščem, so vozlišča prednikov.
• Potomatsko vozlišče: Vsa spodnja vozlišča, povezana z vozliščem, vse do povezanih listov, so naslednja vozlišča. Zadevno vozlišče ni del potomskih vozlišč. Zadevno vozlišče ni nujno korensko vozlišče.
• Poddrevo: Vozlišče in vsi njegovi potomci do povezanih listov tvorijo poddrevo. Začetno vozlišče je vključeno in ni nujno, da je koren; v nasprotnem primeru bi bilo celo drevo.
• Stopnja: Število podrejenih vozlišč se imenuje stopnja vozlišča.

Prečkanje vseh vozlišč drevesa

Do vseh vozlišč drevesa je mogoče dostopati, če želite prebrati ali spremeniti katero koli vrednost vozlišča. Vendar se to ne naredi samovoljno. To lahko storimo na tri načine, pri čemer gre za prehod globine-prve, kot sledi:

1) po naročilu: Preprosto povedano, v tej shemi se najprej prečka levo poddrevo; nato se dostopa do korenskega vozlišča; nato se prečka desno poddrevo. Ta shema je simbolizirana kot levo-> koren-> desno. Slika 1 je tukaj za lažjo uporabo ponovno prikazana:

Ob predpostavki, da gre za dva brata in sestre na vozlišče; nato levo-> koren-> desno pomeni, da najprej dostopate do najnižjega in skrajno levega vozlišča, nato do nadrejenega vozlišča in nato desnega brata. Ko je več kot dveh bratov in sester, vzamemo prvo kot levo, preostala desna vozlišča pa za desno. Za splošno drevo zgoraj je spodnje levo poddrevo dostopno tako, da ima [EBF]. To je poddrevo. Starš tega poddrevesa je A; torej je A naslednjič dostopen, da ima [EBF] A. Nato se dostopa do poddrevesa [GCHI], ki ima večje poddrevo, [[EBF] A [GCHI]]. Levi-> koren-> desni profil si lahko ogledate, kako se prikazuje. To veliko levo poddrevo bo imelo poddrevo [JDK] na desni strani, da zaključi prehod, da pridobi, [[EBF] A [GCHI]] [JDK].

2) Prednaročilo: Preprosto povedano, v tej shemi se najprej dostopa do korenskega vozlišča, nato se prečka levo poddrevo in nato še desno poddrevo. Ta shema je simbolizirana kot root-> left-> right. Slika 1 je tukaj ponovno prikazana za lažje sklicevanje.

Ob predpostavki, da gre za dva brata in sestre na vozlišče; potem root-> levo-> desno pomeni, da najprej dostopate do korena, nato levega neposrednega otroka in nato desnega neposrednega otroka. Ko je več kot dveh bratov in sester, vzamemo prvo kot levo, preostala desna vozlišča pa za desno. Naslednji, do katerega dostopate, je levi otrok levega otroka. Za splošno drevo zgoraj je korensko poddrevo [ABCD]. Na levi strani tega poddrevesa imate poddrevo [EF], ki daje zaporedje dostopa, [ABCD] [EF]. Desno od tega večjega poddrevesa imate dve poddrevesi, [GHI] in [JK], ki dajeta celotno zaporedje, [ABCD] [EF] [GHI] [JK]. Ogledate si lahko korenski-> levi-> desni profil, ki se prikazuje.

3) Naročilo po naročilu: Preprosto povedano, v tej shemi se najprej prečka levo poddrevo, nato desno, nato pa dostop do korena. Ta shema je simbolizirana kot levi-> desni-> koren. Slika 1 je tukaj ponovno prikazana za lažje sklicevanje.

Za to drevo so poddrevesa [EFB], [GHIC], [JKD] in [A], ki tvorijo zaporedje, [EFB], [GHIC], [JKD] [A]. Levi-> desni-> korenski profil si lahko ogledate, kako se prikazuje.

Ustvarjanje drevesa

Zgornje drevo bo ustvarjeno z uporabo ECMAScripta, ki je kot najnovejša različica JavaScripta. Vsako vozlišče je matrika. Prvi element vsakega polja vozlišča je nadrejeni vozlišča, drugo polje. Preostali elementi vozlišča so otroci vozlišča, začenši od skrajno levega otroka. Obstaja zemljevid ECMAScript, ki vsako matriko poveže z ustreznim nizom (črko). Prvi segment kode je: