Gyakorlati alapok III.
Az adatszerkezetek - Fa
A fa egy olyan hierarchikus adatszerkezet, amelyben egy elemnek akárhány rákövetkezője, de minden elemnek csak egyetlen megelőzője létezik:
Forrás - Source: Gábor Dénes Főiskola
Az összes könyvtárszerkezet logikai felépítése ezt az adattárolási elvet követi. Amint megtanulhattuk Az osztályok közötti kapcsolatok című fejezetben, ez rendkívül erős tartalmazási viszonyt eredményez az elemek között. Például: ha a fenti képet egy könyvtárszerkezetre vonatkoztatjuk, akkor C könyvtár törlése esetén törlődik D-E-F-G is.
Legfontosabb tulajdonságai:
-
a fa csomópontokból és élekből áll, amely utóbbi a csomópontok közti kapcsolatot reprezentálja,
-
a csomópontok közti kapcsolat egyirányú, ebből következően mindig van 1 kezdő-, és 1 végpont,
-
a fa gyökere a hierarchiában legfelül lévő csomópont, ez nem lehet végpont,
-
az összes többi csomópont pontosan egyszer végpont,
-
a fa minden csomópontjára (csúcsára) igaz:
-
balra a nála kisebb elemek helyezkednek el,
-
jobbra a nagyobb elemek helyezkednek el.
-
A fával kapcsolatos algoritmusok legtöbbször rekurzívak, hiszen a részfák lényegében azonos tulajdonságokkal rendelkeznek, mint a teljes fa.
A fa bejárása 2 irányból lehetséges: vagy a gyökértől, vagy valamelyik részfától kezdjük el (a fenti kép alapján):
-
gyökérkezdő (preorder) - a b c d g e f
-
gyökérvégző (postorder) - attól függően, hogy melyik szintű részfától indulunk el:
-
b c a
-
b d e f c a
-
b g d e f c a
-
Fajtái:
-
bináris fa - minden elemének legfeljebb 2 rákövetkező eleme van: bal és jobboldali részfa,
-
nem bináris fa - elemeiből 2-nél több leágazás is lehetséges,
-
kiegyensúlyozott fa - minden szintjén az egyes részfák magassága nem ingadozik többet 1 szintnél,
-
kereső fa - definiálható benne egy konkrét rendezési sorrend.
Pénzes László