7. fejezet 3. rész
A lineáris struktúrák mellett vannak olyan nemlineáris struktúrák is, amelyeken hierarchikus adatkapcsolatok vannak definiálva. Ehhez grafikonokat használnak, köztük hálózati és fa szerkezetek. Vegyünk egy fajta fát - bináris fa.
A bináris (bináris) fa - egy véges elem készlettel, amely vagy üres, vagy tartalmaz egy elemet az úgynevezett gyökér a fa, és a maradék elemek sokaságának vannak osztva két diszjunkt részhalmazait, amelyek mindegyike önmagában egy bináris fa. Ezeket a részhalmazokat a forrásfa bal és jobb oldali részének nevezik.
Ábra. 8 bináris fa
Az 1. ábrán. A 8. ábra a bináris fa ábrázolásának legáltalánosabb módját mutatja. Kilenc csomópontból áll. A gyökér a fa az a csomópont A. A bal oldali részfa van gyökere B, a jobb oldali részfa - a gyökér a C. Ezek kapcsolódnak olyan ága áradó ága A. hiánya azt jelenti, üres részfa. Például a C gyökérhez tartozó alrész nem tartalmaz baloldalt, üres. Üres és jobb részfa gyökerezik E. bináris részfa gyökerezik D. G. H és I üres bal és a jobb részfa. Egy csomópont, amely üres, jobb és bal alsó részeket tartalmaz, levélnek nevezik. Ha mind a bináris fa csomópont, amely nem levél, egy nem üres bal és a jobb részfa, akkor a fa az úgynevezett szigorúan bináris
szintű csomópont a bináris fa definíciója a következő: root szinten mindig nulla, majd a szint számát, amikor mozog a fa gyökér nőtt 1 tekintetében a közvetlen őse. A mélység egy bináris fa - ez a legmagasabb szint a fa levelei, más szóval, a hossza a leghosszabb útvonal a gyökér a levél. A fa csomópontjai a következő séma szerint számozhatók (lásd a 9. ábrát)
Ábra. 9 A bináris fa csomópont számozási sémája
gyökér mindig 1., bal gyermek megkapja a 2. számú Jobb - bal Szoba 3. leszármazottja 2 csomópont kell kapnia a 4-es számú, a jobb - 5 bal leszármazottja 3 csomópont megkapja a 6-os szám, a jobb - 7, stb A nem létező csomópontok nincsenek számozva, ami azonban nem sérti a megjelölt rendet, mivel számuk nem kerül felhasználásra. A fa számozási rendszerével minden csomópont egyedi számot kap.
Az n szint egy teljes bináris fája olyan fa, amelyben az n szint minden egyes csomója levél, és minden n-nél kisebb szinten levő csomópont a jobb és a bal oldali részfürtöket tartalmazza.
Egy majdnem teljes bináris fa definíciója bináris fa, amelyhez egy nem negatív egész szám tartozik, így:
1) a fa minden levele k vagy k +1 szinttel rendelkezik;
2) ha a fa csomópontja a k + 1 szinttel egyenrangú leszármazott, akkor minden bal leszármazottja, amelyik a lap, szintén k +1 szinttel rendelkezik.
Figyelembe véve a fákkal kapcsolatos cselekményeket, azt mondhatjuk, hogy egy fa létrehozásához csomópontokat kell létrehozni, és a befogadás helyét előre meghatározva be kell őket venni a fába. A csomópontok számát az igény határozza meg. A befogási algoritmusnak ismernie kell és állandónak kell lennie. A fa csomópontjai bármilyen információt tárolhatnak.
Felmerülhet a probléma és a fa megsemmisülése egy olyan időben, amikor szükség van rá (az elemeiben rögzített információkban) eltűnik. Bizonyos esetekben szükség lehet a részalap elpusztítására.
Annak érdekében, hogy a csomópontok egy fát alkossanak, szükséges, hogy valahogy kialakítsák és használják a csomópontok kapcsolatait őseikkel és leszármazottaikkal. Mindez nagyon hasonlít a listán szereplő elemekre.
Tekintsünk egy példát egy bináris fa létrehozására. Tegyük fel, hogy szükség van, hogy egy bináris fa, a csomópontok (elemek), amelyek a következő jellemző értékek: 20, 10, 35, 15, 17, 27, 24, 8, 30. azonos módon akkor jön tartalmazza egy bináris fa. A fa első csomópontja egy 20 értékű csomópont. Megjegyzés: a következő elem helyének keresése mindig a gyökérből indul. Állva a bal csatlakozik 10 elem a gyökerekhez a megfelelő csatlakozó elem 35. Ezt követően a 15 elem van kötve a jobb oldalon a 10, majd az utat: a gyökér 20 - balra - 10. pont - a jobb - a kapcsolatot, mivel nincs módja tovább. A folyamat addig folytatódik, amíg az elemek kimerültek. Az eredmény az 1. ábrán látható. 10.
Ábra. 10 Egy bináris fa építése.
A faelemek értékei: 20, 10, 35, 15, 17, 27, 24, 8, 30
Bináris fa létrehozásakor a kérdést külön kell megoldani, azzal a lehetőséggel, hogy olyan elemeket is beilleszthet, amelyekben duplikáló attribútumok vannak. A bináris keresési algoritmus lehetővé teszi a csomópontok helyes elhelyezését a fában, amikor engedélyezi azt, azonban a már beérkezett elemek keresésekor nehézségek merülnek fel, mivel a standard keresési beállítással csak az egyik példányt választja ki. Az összes másolat felismeréséhez egy algoritmust kell alkalmazni a fának ilyen keresztben, amelyben egyszer a fa minden egyes csomópontja kerül kiválasztásra.
Íme egy példa a fa készítéséhez szükséges mezők és elemek leírására.
Ha bináris fával dolgozik, a következő alapvető feladatok lehetségesek:
1) létrehoz egy elemet, egy fa csomópontot,
2) a bináris keresési algoritmust használva egy faba,
3) a csomópont fáiba a kulcsjellemző adott értékével,
4) a fa maximális mélységének meghatározása,
5) a fa csomópontjainak meghatározása,
6) a fa leveleinek számának meghatározása,
7) számos egyéb probléma.
Íme néhány példa azokra a folyamatokra, amelyek végrehajtják a bináris fa használatának alapvető feladatait.
MEGJEGYZÉS: egy elem, amelyen duplikáló kulcs attribútum van, nem szerepel a fában.
Ez a mozgás algoritmus fa lehet az alapja meghatározásának problémáját a maximális szint (mélység) a bináris fa, meghatározzuk, hogy van egy elem a fa egy adott érték a legfontosabb tulajdonság, stb azaz azok a feladatok, amelyek megoldása a fa bináris keresési algoritmusán alapul.
Azonban nem minden feladat bináris kereséssel oldható meg, például a fa csomópontjainak számát. Ehhez egy algoritmusra van szükség, amely lehetővé teszi, hogy egyszer egyszer felkeresse a fa egyes csomópontjait.
Bármely webhely látogatása során az alábbi három művelet lehetséges:
1) feldolgozza a csomópontot (egy adott műveletcsoport egy időben nem fontos). Ezt a műveletet O (feldolgozás) jelöli;
2) menj a bal oldali linkre (L-vel jelölve);
3) menj a jobb oldali linkre (a - P jelöli).
A bináris fa csomópontok megkerülését megszervezheti, ha ezt a műveletsort egyszer végrehajtja minden egyes csomóponton. Az akciók bármely sorrendben kombinálhatók, de állandóan a fa átvezetésének konkrét feladatai között kell lennie.
A 3. ábrán egy fa példáját használva. A 10. ábra bemutatja a fa áthaladásának lehetőségeit.
1) Az OLP típusának megkerülése. Az ilyen kitérőt "közvetlen rend", "mélységben" nevezik. A következő sorrendet adja meg a csomópontok meglátogatásában:
20, 10, 8, 15, 17, 35, 27, 24, 30
2) A LOP típus áthidalása. Ezt "szimmetrikusnak" nevezzük, és az alábbi sorrendet adjuk meg a látogató csomópontoknak:
8, 10, 15, 17, 20, 24, 27, 30, 35
3) Az LPO típusának megkerülése. Ezt "fordított sorrendben" nevezzük, és az alábbi sorrendet adjuk meg a látogató csomópontoknak:
8, 17, 15, 10, 24, 30, 27, 35, 20
Ha figyelembe vesszük a feladat, amely folyamatos bejárás a fa, néhány közülük rendelni bejárás, általában nem kritikus, például megszámlálásából a fa csúcsainak a száma, levél / nem levél elemek, amelyeknek előre meghatározott információk stb Azonban egy ilyen feladat, mint egy bináris fa megsemmisítése a memória kibocsátásával, csak egy "fordított sorrendű" feltérképezést igényel.
Tekintsük azt az eszközt, amellyel lehetőség nyílik a fa áthaladására.
Amikor egy bináris fával dolgozik a programozás szempontjából, a program létrehozásának legjobb módja a rekurzió használata. A bináris fa áthelyezésének rekurzív eljárásának alapváltozata nagyon egyszerű.
A rekurzió mechanizmusának gyakorlati tanulmányozásához, amikor egy fa áthaladásának lehetőségeit alkalmazzuk, használhatjuk a 10. ábrán a már megépített fát.
Példa egy rekurzív eljárás használatára a bináris fa levelek számlálásának problémájának megoldására.
Összefoglalva, azt kell mondani, hogy a rekurzív fa alkalmazható a legtöbb feladatot, de akkor is kell különböztetni változatai hatékony alkalmazása a bináris keresés, és a folyamatos csúszás.