Koka datu struktūras apmācība iesācējiem

Ievads

Koks programmatūrā ir kā bioloģisks koks, bet ar šādām atšķirībām:

• Tas ir uzzīmēts otrādi.
• Tam ir tikai viena sakne un bez kāta.
• Zari parādās no saknes.
• Punktu, kurā filiāle paceļas no citas filiāles vai saknes, sauc par mezglu.
• Katram mezglam ir vērtība.

Programmatūras koka zarus attēlo taisnas līnijas. Labs programmatūras koka piemērs, kuru, iespējams, esat izmantojis, ir datora cietā diska direktoriju koks.

Ir dažādi koku veidi. Ir vispārējais koks, no kura iegūti citi koki. Citus kokus iegūst, ieviešot ierobežojumus vispārējā kokā. Piemēram, jūs varētu vēlēties koku, kurā no mezgla rodas ne vairāk kā divi zari; šādu koku sauktu par bināro koku.  Šajā rakstā ir aprakstīts vispārīgais koks un kā piekļūt visiem tā mezgliem.

Hipersaite koda lejupielādei ir norādīta šī raksta beigās.

Lai saprastu šī raksta kodu paraugus, jums ir jābūt pamata zināšanām JavaScript (ECMAScript). Ja jums nav šo zināšanu, varat tās iegūt vietnē http: // www.plaša tīkla.com / ChrysanthusForcha-1 / ECMAScript-2015-Course.htm

Vispārīgā koku diagramma

'A' ir saknes mezgls; tas ir pirmā līmeņa mezgls. B, C, D atrodas otrajā līnijā; tie ir otrā līmeņa mezgli. E, F, G, H, I, J, K atrodas trešajā līnijā, un tie ir trešā līmeņa mezgli. Ceturtā līnija būtu radījusi ceturtā līmeņa mezglus utt.

Koka īpašības

- Visiem visu mezglu līmeņu zariem ir viens avots, kas ir saknes mezgls.

- Kokam ir N - 1 zars, kur N ir kopējais mezglu skaits. Iepriekšminētajā vispārējā koka diagrammā ir 11 mezgli un 10 zari.

- Atšķirībā no cilvēkiem, kur katram bērnam ir divi vecāki, ar programmatūras koku katram bērnam ir tikai viens no vecākiem. Saknes mezgls ir lielākais priekšteču vecāks. Vecākiem var būt vairāki bērni. Katrs mezgls, izņemot saknes mezglu, ir bērns.

Koku vārdnīca

• Saknes mezgls: Šis ir koka augstākais mezgls, un tam nav vecāku. Katram otrajam mezglam ir vecāks.
• Lapu mezgli: Lapu mezgls ir mezgls, kuram nav bērna. Parasti tie atrodas koka apakšā un dažreiz atrodas koka kreisajā un / vai labajā pusē.
• Atslēga: Tā ir koka vērtība. Tas var būt skaitlis; tā var būt virkne; tas var būt pat tāds operators kā + vai - vai x.
• Līmeņi: Saknes mezgls atrodas pirmajā līmenī. Tās bērni ir otrajā līmenī; Otrā līmeņa mezglu bērni ir trešajā līmenī utt.
• Vecāku mezgls: Katrā mezglā, izņemot saknes mezglu, vecāku mezgls ir savienots ar zaru. Jebkurš mezgls, izņemot saknes mezglu, ir pakārtots mezgls.
• Māsu brāļi: Brāļi vai māsas ir mezgli, kuriem ir viens un tas pats vecāks.
• Ceļš: Zari (taisnas līnijas), kas savieno vienu mezglu ar citu, caur citiem mezgliem veido ceļu. Zari var būt vai nav bultiņas.
• Senču mezgls: Visi augstākie mezgli, kas saistīti ar bērnu, ieskaitot vecāku un saknes mezglu, ir priekšteču mezgli.
• Pēcnācēju mezgls: Visi apakšējie mezgli, kas savienoti ar mezglu, tieši pie savienotajām lapām, ir pēctecīgie mezgli. Attiecīgais mezgls nav daļa no pēctecības mezgliem. Attiecīgajam mezglam nav jābūt saknes mezglam.
• Apakškoks: Mezgls un visi tā pēcteči līdz pat saistītajām lapām veido apakškoku. Sākuma mezgls ir iekļauts, un tam nav jābūt saknei; pretējā gadījumā tas būtu viss koks.
• Grāds: Bērnu skaitu, kuram ir mezgls, sauc par mezgla pakāpi.

Pārvietošanās pa visiem koka mezgliem

Visiem koka mezgliem var piekļūt, lai nolasītu vai mainītu jebkuru mezgla vērtību. Tomēr tas netiek darīts patvaļīgi. Ir trīs veidi, kā to izdarīt, un tas viss ir saistīts ar pirmo dziļuma pārvietošanos šādi:

1) pasūtījums: Vienkārši sakot, šajā shēmā vispirms šķērso kreiso apakškoku; pēc tam piekļūst saknes mezglam; pēc tam tiek šķērsots pareizais apakškoks. Šī shēma ir simbolizēta kā kreisā-> sakne-> labā. Šeit ir atkārtoti parādīts 1. attēls, lai to varētu viegli atrast:

Pieņemot, ka vienā mezglā ir divi brāļi un māsas; tad kreisais-> sakne-> labais nozīmē, vispirms piekļūstat zemākajam un kreisākajam mezglam, pēc tam mezgla vecākam un pēc tam labajam brālim. Kad ir vairāk nekā divi brāļi un māsas, ņemiet pirmo kā kreiso un pārējos labos mezglus kā labos. Vispārīgajam kokam augšpusē kreisajā apakšējā kokā var piekļūt, lai [EBF]. Šī ir apakškopa. Šīs apakšgrupas vecāks ir A; tātad, A nākamreiz piekļūst, lai būtu [EBF] A. Pēc tam tiek piekļūta apakškokam [GCHI], lai iegūtu lielāku apakškoku [[EBF] A [GCHI]]. Jūs varat redzēt kreiso -> saknes -> labo profilu, kas attēlo sevi. Šim lielajam kreisajam apakškokam būs apakškoks [JDK] pa labi, lai pabeigtu šķērsošanu, lai iegūtu [[EBF] A [GCHI]] [JDK].

2) Iepriekš pasūtīt: Vienkārši sakot, šajā shēmā vispirms piekļūst saknes mezglam, pēc tam pāri kreisajam apakškokam un pēc tam labajam apakškokam. Šī shēma tiek simbolizēta kā sakne-> pa kreisi-> pa labi. Šeit ir atkārtoti parādīts 1. attēls, lai to varētu viegli atrast.

Pieņemot, ka vienā mezglā ir divi brāļi un māsas; tad sakne-> pa kreisi-> pa labi nozīmē, ka vispirms piekļūstat saknei, tad kreisajam tūlītējam bērnam un pēc tam labajam tūlītējam bērnam. Kad ir vairāk nekā divi brāļi un māsas, ņemiet pirmo kā kreiso un pārējos labos mezglus kā labos. Nākamais ir kreisā bērna kreisais bērns. Vispārīgajam kokam iepriekš saknes apakškoks ir [ABCD]. Pa kreisi no šīs apakšas jums ir apakškoks [EF], piešķirot piekļuves secību, [ABCD] [EF]. Pa labi no šīs lielākās apakšas jums ir divi apakkoki, [GHI] un [JK], norādot pilnu secību, [ABCD] [EF] [GHI] [JK]. Jūs varat redzēt saknes-> pa kreisi-> labo profilu, kas attēlo sevi.

3) Pēc pasūtījuma: Vienkārši sakot, šajā shēmā vispirms šķērso kreiso apakškoku, tad šķērso labo apakškoku un pēc tam piekļūst saknei. Šo shēmu simbolizē kā kreiso-> labo-> saknes. 1. attēls šeit tiek atkārtoti parādīts, lai to varētu viegli atrast.

Šim kokam apakškoki ir [EFB], [GHIC], [JKD] un [A], kas veido secību, [EFB], [GHIC], [JKD] [A]. Jūs varat redzēt kreiso -> labo -> saknes profilu, kas attēlo sevi.

Koka izveidošana

Iepriekš minētais koks tiks izveidots, izmantojot ECMAScript, kas ir kā jaunākā JavaScript versija. Katrs mezgls ir masīvs. Katra mezgla masīva pirmais elements ir mezgla vecāks, cits masīvs. Pārējie mezgla elementi ir mezgla bērni, sākot ar kreiso bērnu. Ir ECMAScript karte, kas katru masīvu saista ar atbilstošo virkni (burtu). Pirmais koda segments ir: