Výukový program pre stromovú dátovú štruktúru pre začiatočníkov

Úvod

Strom v softvéri je ako biologický strom, má však nasledujúce rozdiely:

• Je nakreslený hore nohami.
• Má iba jeden koreň a nemá stonku.
• Vetvy vychádzajú z koreňa.
• Bod, v ktorom vetva vzlietne z inej vetvy alebo koreň, sa nazýva uzol.
• Každý uzol má hodnotu.

Vetvy softvérového stromu sú znázornené priamymi čiarami. Dobrým príkladom softvérového stromu, ktorý ste mohli použiť, je adresárový strom na pevnom disku vášho počítača.

Existujú rôzne druhy stromov. Existuje všeobecný strom, z ktorého sú odvodené ďalšie stromy. Ostatné stromy sa odvodzujú zavedením obmedzení do všeobecného stromu. Napríklad môžete chcieť strom, z ktorého z uzla nevychádzajú viac ako dve vetvy; taký strom by sa volal Binárny strom.  Tento článok popisuje všeobecný strom a spôsob prístupu ku všetkým jeho uzlom.

Hypertextový odkaz na stiahnutie kódu je uvedený v dolnej časti tohto článku.

Aby ste pochopili ukážky kódu v tomto článku, musíte mať základné znalosti jazyka JavaScript (ECMAScript). Ak tieto vedomosti nemáte, môžete ich získať na stránke http: // www.široká sieť.com / ChrysanthusForcha-1 / kurz ECMAScript-2015.htm

Všeobecný stromový diagram

„A“ je koreňový uzol; je to uzol prvej úrovne. B, C, D sú v druhom riadku; sú to uzly druhej úrovne. E, F, G, H, I, J, K sú na treťom riadku a sú to uzly tretej úrovne. Štvrtý riadok by vytvoril uzly štvrtej úrovne atď.

Vlastnosti stromu

- Všetky vetvy pre všetky úrovne uzlov majú jeden zdroj, ktorým je koreňový uzol.

- Strom má N - 1 vetiev, kde N je celkový počet uzlov. Vyššie uvedený diagram pre všeobecný strom má 11 uzlov a 10 vetví.

- Na rozdiel od ľudí, kde každé dieťa má dvoch rodičov, so softvérovým stromom má každé dieťa iba jedného rodiča. Koreňový uzol je najväčší rodič predka. Rodič môže mať viac ako jedno dieťa. Každý uzol, okrem koreňového, je dieťa.

Slovná zásoba stromov

• Koreňový uzol: Toto je najvyšší uzol v strome a nemá žiadneho rodiča. Každý ďalší uzol má rodiča.
• Uzly listov: Listový uzol je uzol, ktorý nemá žiadne dieťa. Spravidla sú na spodku stromu a niekedy sú na ľavej a / alebo pravej strane stromu.
• Kľúč: Toto je hodnota stromu. Môže to byť číslo; môže to byť reťazec; môže to byť dokonca operátor ako + alebo - alebo x.
• Úrovne: Koreňový uzol je na prvej úrovni. Jeho deti sú na druhej úrovni; Deti uzlov druhej úrovne sú na tretej úrovni atď.
• Rodičovský uzol: Každý uzol, okrem koreňového, má nadradený uzol spojený s vetvou. Akýkoľvek uzol, okrem koreňového uzla, je podradený uzol.
• Súrodenecké uzly: Súrodenecké uzly sú uzly, ktoré majú rovnakého rodiča.
• Cesta: Vetvy (priame čiary), ktoré spájajú jeden uzol s druhým, cez ďalšie uzly tvoria cestu. Vetvy môžu, ale nemusia byť šípky.
• Uzol predka: Všetky vyššie uzly spojené s dieťaťom, vrátane nadradeného a koreňového uzla, sú uzlami predkov.
• Potomok Uzol: Všetky spodné uzly spojené s uzlom, úplne dole k spojeným listom, sú potomkami. Dotknutý uzol nie je súčasťou následných uzlov. Príslušný uzol nemusí byť koreňový uzol.
• Podstrom: Uzol a všetci jeho potomkovia až po príslušné listy tvoria podstrom. Počiatočný uzol je zahrnutý a nemusí to byť koreň; inak by to bol celý strom.
• Stupeň: Počet detí, ktoré uzol má, sa nazýva stupeň uzla.

Traverzovanie všetkých uzlov stromu

Všetky uzly stromu sú prístupné na čítanie alebo zmenu akejkoľvek hodnoty uzla. To sa však nedeje svojvoľne. Existujú tri spôsoby, ako to urobiť, pričom všetky zahŕňajú priechod hĺbky po prvom, a to nasledovne:

1) V objednávke: Jednoducho povedané, v tejto schéme sa najskôr prechádza ľavým podstromom; potom sa pristúpi ku koreňovému uzlu; potom sa prejde pravý podstrom. Táto schéma je symbolizovaná ako ľavá -> koreňová -> pravá. Obrázok 1 sa tu znova zobrazuje pre ľahšiu orientáciu:

Za predpokladu, že v jednom uzle sú dvaja súrodenci; potom left-> root-> right means, you access first the lower and left node first, then the parent of the node, and then the right sibling. Ak sú súrodenci viac ako dvaja, prvého z nich vezmite ako ľavý a zvyšok pravých uzlov ako pravý. Pre všeobecný strom vyššie je prístupný podstrom vľavo dole, ktorý má, [EBF]. Toto je podstrom. Rodičom tohto podstromu je A; takže sa ďalej pristupuje k [EBF] A. Ďalej sa pristupuje k podstromu [GCHI], ktorý má väčší podstrom, [[EBF] A [GCHI]]. Vidíte ľavý-> koreňový-> pravý profil, ktorý sa vykresľuje. Tento veľký ľavý podstrom bude mať podstrom, [JDK] napravo na dokončenie prechodu k získaniu, [[EBF] A [GCHI]] [JDK].

2) Predobjednávka: Jednoducho povedané, v tejto schéme sa najskôr získa prístup k koreňovému uzlu, potom sa prechádza ďalším ľavým podstromom a potom pravým podstromom. Táto schéma je symbolizovaná ako root-> left-> right. Obrázok 1 je tu znova zobrazený pre ľahšiu orientáciu.

Za predpokladu, že v jednom uzle sú dvaja súrodenci; potom root-> doľava-> doprava znamená, že najskôr vstúpite do koreňa, potom do ľavého bezprostredného dieťaťa a potom do pravého bezprostredného dieťaťa. Ak sú súrodenci viac ako dvaja, prvého z nich vezmite ako ľavý a zvyšok pravých uzlov ako pravý. Dieťa úplne vľavo od ľavého dieťaťa je ďalšie, ku ktorému sa bude pristupovať. Pre všeobecný strom vyššie je koreňový podstrom [ABCD]. Naľavo od tohto podstromu sa nachádza podstrom [EF], ktorý poskytuje prístupovú sekvenciu [ABCD] [EF]. Napravo od tohto väčšieho podstromu máte dva podstromy [GHI] a [JK], ktoré poskytujú úplnú sekvenciu [ABCD] [EF] [GHI] [JK]. Môžete vidieť koreňový-> ľavý-> pravý profil, ktorý sa vykresľuje.

3) Objednávka: Jednoducho povedané, v tejto schéme sa najskôr prechádza ľavým podstromom, potom sa prechádza pravým podstromom a potom sa pristupuje ku koreňu. Táto schéma je symbolizovaná ako left-> right-> root. Obrázok 1 je tu znova zobrazený pre ľahšiu orientáciu.

Pre tento strom sú podstrommi [EFB], [GHIC], [JKD] a [A], ktoré tvoria sekvenciu, [EFB], [GHIC], [JKD] [A]. Môžete vidieť ľavý-> pravý-> koreňový profil, ktorý sa vykresľuje.

Vytvorenie stromu

Vyššie uvedený strom bude vytvorený pomocou ECMAScript, ktorý je ako najnovšia verzia JavaScriptu. Každý uzol je pole. Prvým prvkom každého uzlového poľa je nadradený uzol, ďalšie pole. Zvyšok prvkov uzla sú potomkami uzla, začínajúc od dieťaťa najviac vľavo. Existuje mapa ECMAScript, ktorá spája každé pole s príslušným reťazcom (písmenom). Prvý segment kódu je: