Puuandmete struktuuri õpetus algajatele

Sissejuhatus

Puu tarkvaras on nagu bioloogiline puu, kuid järgmiste erinevustega:

• See on tõmmatud tagurpidi.
• Sellel on ainult üks juur ja varre.
• Oksad väljuvad juurest.
• Punkti, kus haru eemaldub teisest harust või juurest, nimetatakse sõlmeks.
• Igal sõlmel on väärtus.

Tarkvarapuu harusid esindavad sirgjooned. Hea näide teie kasutatavast tarkvarapuust on teie arvuti kõvaketta kataloogipuu.

Puid on erinevat tüüpi. Seal on üldine puu, millest teised puud on tuletatud. Teised puud saadakse piirangute sisseviimisega üldisse puusse. Näiteks võiksite soovida puud, kus sõlmest ei pärine rohkem kui kaks haru; sellist puud nimetataks kahendpuuks.  Selles artiklis kirjeldatakse üldist puud ja kuidas pääseda juurde kõigile selle sõlmedele.

Hüperlink koodi allalaadimiseks on toodud selle artikli lõpus.

Selle artikli koodinäidiste mõistmiseks peavad teil olema JavaScripti (ECMAScript) põhiteadmised. Kui teil neid teadmisi pole, saate need aadressilt http: // www.laia võrguga.com / ChrysanthusForcha-1 / ECMAScript-2015-kursus.htm

Üldine puude skeem

'A' on juursõlm; see on esimese taseme sõlm. B, C, D asuvad teisel real; need on teise taseme sõlmed. E, F, G, H, I, J, K asuvad kolmandal real ja nad on kolmanda taseme sõlmed. Neljas rida oleks tootnud neljanda taseme sõlmed jne.

Puu omadused

- Kõigi sõlmede kõigi harude harudel on üks allikas, see on juursõlm.

- Puus on N - 1 haru, kus N on sõlmede koguarv. Ülaltoodud üldpuu diagrammil on 11 sõlme ja 10 haru.

- Erinevalt inimestest, kus igal lapsel on kaks vanemat, on tarkvarapuu puhul igal lapsel ainult üks vanem. Juuresõlm on suurim esivanem. Vanemal võib olla mitu last. Iga sõlm, välja arvatud juursõlm, on laps.

Puu sõnavara

• Juuresõlm: See on puu kõrgeim sõlm ja sellel pole vanemat. Igal teisel sõlmel on vanem.
• Lehesõlmed: Lehesõlm on sõlm, millel pole last. Need asuvad tavaliselt puu põhjas ja mõnikord puu vasakul ja / või paremal küljel.
• Võti: See on puu väärtus. See võib olla number; see võib olla string; see võib olla isegi operaator nagu + või - või x.
• Tasemed: Juuresõlm on esimesel tasandil. Selle lapsed on teisel tasemel; Teise astme sõlmede lapsed on kolmandal tasandil jne.
• Vanem sõlm: Igal sõlmel, välja arvatud juursõlmel, on haru abil ühendatud vanemsõlm. Iga sõlm, välja arvatud juursõlm, on alamsõlm.
• Vennasõlmed: Vennasõlmed on sõlmed, millel on sama vanem.
• Tee: Harud (sirgjooned), mis ühendavad ühte sõlme teisega, moodustavad tee teiste sõlmede kaudu. Filiaalid võivad olla nooled või mitte.
• Esivanemate sõlm: Kõik lapsega ühendatud kõrgemad sõlmed, sealhulgas vanem ja juursõlm, on esivanemate sõlmed.
• Järeltulija sõlm: Kõik sõlmega ühendatud madalamad sõlmed, otse ühendatud lehtedeni, on järeltulijad. Kõnealune sõlm ei kuulu järeltulevate sõlmede hulka. Kõnealune sõlm ei pea olema juursõlm.
• Alampuu: Sõlm koos kõigi järeltulijatega kuni seotud lehtedeni moodustavad alampuu. Algussõlm on kaasatud ja see ei pea olema juur; muidu oleks see terve puu.
• Kraad: Sõlmel olevate laste arvu nimetatakse sõlme astmeks.

Kõigi puu sõlmede läbimine

Kõigile puu sõlmedele pääseb juurde, et lugeda või muuta sõlme mis tahes väärtust. Kuid seda ei tehta meelevaldselt. Seda saab teha kolmel viisil, mis kõik hõlmavad esimest läbisõitu järgmiselt:

1) tellimus: Lihtsamalt öeldes läbitakse selles skeemis kõigepealt vasak alampuu; siis pöördutakse juursõlme juurde; siis läbitakse õige alampuu. Seda skeemi sümboliseeritakse vasak-> juur-> parem. Joonis 1 kuvatakse siin hõlpsalt viitamiseks uuesti:

Eeldades, et sõlme kohta on kaks õde-venda; siis vasak-> juur-> parem tähendab, et pääsete kõigepealt kõige madalamale ja vasakpoolsemale sõlmele, seejärel sõlme vanemale ja seejärel paremale vennale. Kui õdesid-vendi on rohkem kui kaks, võtke esimene vasakpoolsena ja ülejäänud paremad sõlmed parempoolsena. Ülaltoodud üldise puu jaoks pääsete vasakusse alumisse alampuule, et olla,. See on alampuu. Selle alampuu vanem on A; niisiis, järgmisena pöördutakse A poole, et saada [EBF] A. Järgmisena pöördutakse alampuu [GCHI] poole, et olla suurem alampuu [[EBF] A [GCHI]]. Näete, kuidas vasak-> juur-> parem profiil ennast kujutab. Sellel suurel vasakpoolsel alampuul on alampuu, [JDK] paremal, et läbimine läbida, saamaks.

2) Ettetellimine: Lihtsamalt öeldes, selles skeemis pöördutakse kõigepealt juursõlme poole, seejärel läbitakse vasakpoolne alampuu ja seejärel parempoolne alampuu. Seda skeemi sümboliseeritakse kui juur-> vasak-> parem. Joonis 1 kuvatakse siin hõlpsalt viitamiseks uuesti.

Eeldades, et sõlme kohta on kaks õde-venda; siis juur-> vasak-> parem tähendab, et pääsete kõigepealt juurde juurele, seejärel vasakule ja seejärel paremale lapsele. Kui õdesid-vendi on rohkem kui kaks, võtke esimene vasakuks ja ülejäänud paremad sõlmed paremaks. Järgmisena pöördutakse vasaku lapse vasakpoolseima lapse poole. Ülaltoodud üldise puu puhul on juure alampuu [ABCD]. Sellest alampuust vasakul on alampuu [EF], mis annab juurdepääsu jada, [ABCD] [EF]. Sellest suuremast alampuust paremal on teil kaks alampuud [GHI] ja [JK], mis annavad täieliku järjestuse [ABCD] [EF] [GHI] [JK]. Näete, kuidas juur-> vasak-> parem profiil ennast kujutab.

3) Järeltellimus: Lihtsamalt öeldes läbitakse selles skeemis kõigepealt vasak alampuu, seejärel parempoolne alampuu ja seejärel juur. Seda skeemi sümboliseeritakse vasak-> parem-> juur. Joonis 1 kuvatakse siin hõlpsalt viitamiseks uuesti.

Selle puu alampuud on [EFB], [GHIC], [JKD] ja [A], mis moodustavad järjestuse [EFB], [GHIC], [JKD] [A]. Näete ennast vasakpoolset-> paremat-> juurprofiili.

Puu loomine

Ülaltoodud puu luuakse ECMAScriptiga, mis on nagu JavaScripti uusim versioon. Iga sõlm on massiiv. Iga sõlme massiivi esimene element on sõlme vanem, teine ​​massiiv. Ülejäänud sõlme elemendid on sõlme lapsed, alustades kõige vasakpoolsest lapsest. Seal on ECMAScripti kaart, mis seob iga massiivi vastava stringiga (tähega). Esimene koodisegment on: