Az összekapcsolt listákkal, egydimenziós tömbökkel és más lineáris adatszerkezetekkel ellentétben, amelyeken lineáris sorrendben haladunk végig, a fák többféleképpen is átszelhetők. Lehet őket mélység-elsőként vagy szélesség-elsőként végigjárni. A mélység szerinti sorrendben történő átjárásuknak három gyakori módja van: sorrendben, elősorrendben és utósorrendben. Ezeken az alapvető átjárási módokon túlmenően különböző összetettebb vagy hibrid sémák is lehetségesek, például a mélységkorlátozott keresés, például az iteratív mélyülő mélység-első keresés. Ez utóbbi, akárcsak a szélesség-első keresés, végtelen fák átjárására is használható, lásd alább.
Adatszerkezetek a fák átjárásáhozSzerkesztés
A fa átjárása magában foglalja az összes csomóponton való iterációt valamilyen módon. Mivel egy adott csomópontból egynél több lehetséges következő csomópont van (nem lineáris adatszerkezetről van szó), ezért – szekvenciális (nem párhuzamos) számítást feltételezve – néhány csomópontot valamilyen módon el kell halasztani-tárolni a későbbi látogatáshoz. Ez gyakran egy verem (LIFO) vagy egy sor (FIFO) segítségével történik. Mivel a fa egy önreferenciális (rekurzívan definiált) adatszerkezet, az átjárás nagyon természetes és egyértelmű módon definiálható rekurzióval vagy – finomabban fogalmazva – magkurzióval; ezekben az esetekben a halasztott csomópontokat implicit módon a hívási veremben tároljuk.
A mélység-első keresés könnyen megvalósítható vermen keresztül, beleértve a rekurzív (a hívási vermen keresztül), míg a szélesség-első keresés könnyen megvalósítható soron keresztül, beleértve a magkurzív keresést is.:45-61
Bináris fa mélység-első kereséseSzerkesztés
- Előrendezés (csomóponthoz való hozzáférés a piros ● pozícióban):
F, B, A, D, C, E, G, I, H;
- In-order (node access at position green ●):
A, B, C, D, E, F, G, H, I;
- Post-order (node access at position blue ●):
A, C, E, D, B, H, I, G, F.
Ezeket a kereséseket mélységi keresésnek (DFS) nevezzük, mivel a keresési fát minden egyes gyermeken a lehető legmélyebbre mélyítjük, mielőtt a következő testvérre lépnénk. Egy bináris fa esetében ezek minden egyes csomóponton az aktuális csomóponttal kezdődő hozzáférési műveletekként vannak definiálva, amelyek algoritmusa a következő:
A bináris fa bejárásának általános rekurzív mintája a következő:
- Megyünk egy szinttel lejjebb az N rekurzív argumentumig. Ha N létezik (nem üres), akkor a következő három műveletet hajtjuk végre egy bizonyos sorrendben: L: rekurzívan végigmegy N bal oldali részfáján. R: N jobb oldali részfájának rekurzív végigjárása. N: Hozzáférés (látogatás) magához az aktuális N csomóponthoz.
- Visszatérés egy szinttel feljebb lépve és az N szülő csomópontjához érkezve.
Három módszer (minta) van arra, hogy a parcours (traverzálódás) melyik pozíciójában a csomóponthoz képest (az ábrán: piros, zöld vagy kék) a csomópont látogatása (elérése) történjen. Pontosan egy szín kiválasztása a csomópont pontosan egy látogatását határozza meg az alábbiakban leírtak szerint. A hozzáférés mindhárom színnél ugyanannak a csomópontnak a háromszori látogatását eredményezi, ami az “all-order” szekvencializációt eredményezi:
F-B-A-A-A-A-B-D-C-C-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F
Pre-order, NLREdit
- Az aktuális csomópont adatrészének elérése (az ábrán: piros pozíció).
- A bal oldali részfa bejárása a pre-order függvény rekurzív hívásával.
- A jobb oldali részfa bejárása a pre-order függvény rekurzív hívásával.
A pre-order átjárás topológiailag rendezett, mivel egy szülő csomópontot előbb dolgozunk fel, mint bármelyik gyermekcsomópontját.
In-order, LNREdit
- A bal oldali részfát az in-order függvény rekurzív hívásával járjuk át.
- Elérjük az aktuális csomópont adatrészét (az ábrán: zöld pozíció).
- A jobb oldali részfa bejárása az in-order függvény rekurzív hívásával.
Egy bináris keresőfában, amely úgy van rendezve, hogy minden csomópontban a kulcs nagyobb, mint a bal oldali részfa összes kulcsa, és kisebb, mint a jobb oldali részfa összes kulcsa, a sorrendben történő bejárás a kulcsokat növekvő rendezett sorrendben keresi.
Reverse in-order, RNLEdit
- A jobb oldali részfa bejárása a reverse in-order függvény rekurzív hívásával.
- Az aktuális csomópont adatrészének elérése.
- A bal oldali részfa bejárása a reverse in-order függvény rekurzív hívásával.
Bináris keresőfában a fordított sorrendben történő átjárás a kulcsokat csökkenő rendezett sorrendben keresi.
Post-order, LRNEdit
- A bal oldali részfát a post-order függvény rekurzív hívásával járja át.
- A jobb oldali részfát a post-order függvény rekurzív hívásával járjuk be.
- Az aktuális csomópont adatrészéhez (az ábrán: kék pozíció) férünk hozzá.
A traverzálás nyomvonalát a fa szekvencializációjának nevezzük. A traverzális nyomvonal az egyes meglátogatott csomópontok listája. Nincs olyan szekvencializáció, amely a pre-, in- vagy post-order szerint egyedileg írja le a mögöttes fát. Egy különálló elemekkel rendelkező fa esetén akár a pre-order, akár a post-order és a in-order párosítása elegendő a fa egyértelmű leírásához. A pre-order és a post-order azonban némi kétértelműséget hagy a fa szerkezetében.
Generic treeEdit
Hogy bármely fán mélységi kereséssel haladjunk végig, minden egyes csomóponton végezzük el a következő műveleteket:
- Ha nincs csomópont, return.
- Access (= visit) node (pre-order position).
- For each i from 1 to number_of_children – 1 do:
- Recursively traverse i-th child.
- Elérjük a csomópontot (sorrendbeli pozíció).
- Rekurzívan végigjárjuk az utolsó gyermeket.
- Elérjük a csomópontot (sorrend utáni pozíció).
Az adott problémától függően a pre-order, post-order, és különösen a (number_of_children – 1) in-order műveletek közül az egyik lehet üres, vagy csak egy adott gyermekhez akarunk hozzáférni, így ezek a műveletek opcionálisak. A gyakorlatban a pre-order, in-order és post-order műveletek közül egynél többre is szükség lehet. Például egy terner fába való beszúráskor az elemek összehasonlításával egy előrendelési műveletet hajtunk végre. Ezt követően szükség lehet egy post-order műveletre a fa újbóli kiegyensúlyozásához.
Breadth-first search, or level orderEdit
A fákat szint-sorrendben is bejárhatjuk, amikor egy szint minden csomópontját meglátogatjuk, mielőtt egy alacsonyabb szintre lépnénk. Ezt a keresést nevezzük szélesség-első keresésnek (BFS), mivel a keresési fát minden egyes mélységen a lehető legnagyobb mértékben kiszélesítjük, mielőtt a következő mélységre lépnénk.
Egyéb típusokSzerkesztés
Léteznek olyan faátjárási algoritmusok is, amelyek nem sorolhatók sem a mélység-első kereséshez, sem a szélesség-első kereséshez. Az egyik ilyen algoritmus a Monte Carlo fakeresés, amely a legígéretesebb lépések elemzésére koncentrál, a keresési fa bővítését a keresési tér véletlenszerű mintavételezésére alapozva.