Fa adatszerkezet oktató kezdőknek

Bevezetés

Egy fa a szoftverben olyan, mint egy biológiai fa, de a következő különbségekkel rendelkezik:

• Fejjel lefelé van húzva.
• Csak egy gyökere van, és nincs szára.
• Az ágak a gyökérből kerülnek elő.
• Azt a pontot, ahol egy elágazás leválik egy másik ágról vagy a gyökér, csomópontnak hívjuk.
• Minden csomópontnak van értéke.

A szoftverfa ágait egyenes vonalak ábrázolják. Jó példa egy esetleg használt szoftverfára a számítógép merevlemezének könyvtárfája.

Különböző fafajták léteznek. Van az az általános fa, amelyből más fák származnak. Más fákat úgy hoznak létre, hogy korlátokat vezetnek be az általános fába. Például érdemes lehet egy olyan fa, ahol egy csomópontból legfeljebb kettő ág származik; egy ilyen fát bináris fának hívnának.  Ez a cikk ismerteti az általános fát és az összes csomópont elérését.

A kód letöltésére szolgáló hiperhivatkozás a cikk alján található.

A cikk kódmintáinak megértéséhez alapismeretekkel kell rendelkeznie a JavaScript-ben (ECMAScript). Ha nincs ilyen ismerete, akkor a http: // www webhelyről szerezheti be.széles hálózat.com / ChrysanthusForcha-1 / ECMAScript-2015-Course.htm

Az Általános fa diagram

'A' a gyökércsomópont; ez az első szintű csomópont. B, C, D a második vonalon vannak; ezek második szintű csomópontok. E, F, G, H, I, J, K a harmadik vonalon vannak, és harmadik szintű csomópontok. Egy negyedik vonal negyedik szintű csomópontokat produkált volna, és így tovább.

Fa tulajdonságai

- A csomópontok minden szintjének minden ágának van egy forrása, amely a gyökércsomópont.

- Egy fa N - 1 ággal rendelkezik, ahol N a csomópontok teljes száma. Az általános fa fenti diagramja 11 csomópontot és 10 elágazást tartalmaz.

- Ellentétben az emberekkel, ahol minden gyermeknek két szülője van, a szoftverfával, minden gyermeknek csak egy szülője van. A gyökércsomópont a legnagyobb ősszülő. Egy szülőnek több gyermeke lehet. A csomópont kivételével minden csomópont gyermek.

Fa szókincs

• Gyökércsomópont: Ez a fa legmagasabb csomópontja, és nincs szülője. Minden más csomópontnak van szülője.
• Levél csomópontok: A levélcsomópont olyan csomópont, amelynek nincs gyermeke. Általában a fa alján vannak, és néha a fa bal és / vagy jobb oldalán találhatók.
• Kulcs: Ez egy fa értéke. Lehet szám; lehet egy húr; akár operátor is lehet, például + vagy - vagy x.
• Szintek: A gyökércsomópont az első szinten van. Gyermekei a második szinten vannak; A második szintű csomópontok gyermekei a harmadik szinten vannak, és így tovább.
• Szülőcsomópont: A gyökércsomópont kivételével minden csomóponthoz tartozik egy szülőcsomópont, amelyet egy elágazás köt össze. A gyökércsomópont kivételével bármely csomópont gyermekcsomópont.
• Testvércsomópontok: A testvércsomópontok ugyanazon szülővel rendelkező csomópontok.
• Pálya: Az ágak (egyenesek), amelyek összekötik az egyik csomópontot a másikkal, más csomópontokon keresztül, utat képeznek. Az ágak lehetnek nyilak vagy nem.
• Ős csomópont: A gyermekhez kapcsolódó összes magasabb csomópont, beleértve a szülőt és a gyökércsomópontot is, őscsomópont.
• Leszármazási csomópont: Az összes csomóponthoz csatlakoztatott alsó csomópont, közvetlenül a csatlakoztatott levelekig, leszármazott csomópont. A szóban forgó csomópont nem része a leszármazott csomópontoknak. A szóban forgó csomópontnak nem feltétlenül a gyökércsomópontnak kell lennie.
• Részfa: Egy csomópont és az összes leszármazottja egészen a kapcsolódó levelekig részfát alkot. A kezdő csomópont benne van, és nem feltétlenül a gyökérnek kell lennie; különben az egész fa lenne.
• Fokozat: A csomópontban lévő gyermekek számát a csomópont fokozatának nevezzük.

Egy fa minden csomópontjának áthaladása

Egy fa összes csomópontja elérhető a csomópont bármely értékének elolvasásához vagy megváltoztatásához. Ez azonban nem önkényesen történik. Ennek három módja van, amelyek mindegyike magában foglalja az első mélységbeli átjárást az alábbiak szerint:

1) Rendelés: Egyszerűen fogalmazva: ebben a sémában először a bal részfát járjuk be; akkor a gyökércsomóponthoz férünk hozzá; akkor a jobb részfát bejárják. Ezt a sémát bal-> gyökér-> jobb szimbólumként jelképezik. Az 1. ábra itt jelenik meg újra a könnyebb áttekinthetőség érdekében:

Feltéve, hogy csomópontonként két testvér van; akkor a bal-> gyökér-> jobb azt jelenti, hogy először a legalacsonyabb és a bal szélső csomópontot, majd a csomópont szülőjét, majd a jobb testvért éred el. Ha kettőnél több testvér van, vegye az elsőt balra, a többi jobb oldali csomópontot pedig jobbra. A fenti általános fa esetében a bal alsó részfához férhet hozzá, hogy [EBF]. Ez egy alfa. Ennek az alfának a szülője A; így A-hoz legközelebb hozzáfér, hogy [EBF] A legyen. Ezután hozzáférhetünk a [GCHI] alfához, hogy nagyobb részfájuk legyen, [[EBF] A [GCHI]]. Láthatja a bal-> gyökér-> jobb oldali profilt. Ennek a nagy bal alfának az alfa, [JDK] jobbra lesz, hogy befejezze a bejárást, hogy [[EBF] A [GCHI]] [JDK].

2) Előrendelés: Egyszerűen fogalmazva: ebben a sémában először a gyökércsomóponthoz jutunk el, majd a bal részfához, majd a jobb alfához. Ezt a sémát gyökér-> bal-> jobb szimbolizálja. Az 1. ábra itt jelenik meg újra a könnyebb hivatkozás céljából.

Feltéve, hogy csomópontonként két testvér van; akkor a gyökér-> bal-> jobb azt jelenti, hogy először a gyökérhez, majd a bal közvetlen gyermekhez, majd a jobb közvetlen gyermekhez jutsz hozzá. Ha kettőnél több testvér van, vegye az elsőt balra, a többi jobb oldali csomópontot pedig jobbra. A bal gyermek bal szélső gyermekéhez lehet a következő hozzáférni. A fenti általános fa esetében a gyökér alfa [ABCD]. Az alfa bal oldalán található az [EF] részfa, amely megadja a hozzáférési sorrendet: [ABCD] [EF]. A nagyobb részfától jobbra két részfa van, [GHI] és [JK], amelyek megadják a teljes szekvenciát: [ABCD] [EF] [GHI] [JK]. Láthatja a root-> bal-> jobb profilt, amely önmagát ábrázolja.

3) utólagos megrendelés: Egyszerűen fogalmazva: ebben a sémában először a bal alfát, majd a jobb alfát, majd a gyökért érjük el. Ezt a sémát bal-> jobb-> gyökérként szimbolizálják. Az 1. ábra itt jelenik meg újra a könnyebb hivatkozás céljából.

Ennek a fának az alfái: [EFB], [GHIC], [JKD] és [A], amelyek az [EFB], [GHIC], [JKD] [A] szekvenciát alkotják. Láthatja a bal-> jobb-> gyökérprofilt, amely önmagát ábrázolja.

A fa létrehozása

A fenti fa az ECMAScript segítségével jön létre, amely olyan, mint a JavaScript legújabb verziója. Minden csomópont egy tömb. Minden csomóponttömb első eleme a csomópont szülője, egy másik tömb. A csomópont többi eleme a csomópont gyermekei, a bal szélső gyermektől kezdve. Van egy ECMAScript térkép, amely minden tömböt a megfelelő karakterlánccal (betűvel) kapcsol össze. Az első kódszegmens: