A fa struktúra adatok
1.1. Meghatározása a szerkezet: fa
Fa - egy véges T. esetleg üres, különben álló egy vagy több (csomópontok vagy csomópontok a fa) oly módon, hogy:
a) van egy külön kijelölt elem, az úgynevezett gyökér a fa;
b) a maradék elemek szereplő m> 0 diszjunkt halmazok T1. Tm. amelyek mindegyike viszont egy fa; fák T1. Tm nevezik részfákat gyökér (1.A.).
1. ábra. típusú fák
Ha az érték a relatív sorrendje részfák T1. Tm, akkor azt mondjuk, hogy a fa rendezett. A több részfák a csomópont neve, milyen mértékben a csomópontot. Csomópont nulla fok az úgynevezett végpont (levél vagy csomópont vagy terminál), az összes többi elem - a belső csomópontok (nem terminális). A legnagyobb mértékű, minden csúcsot nevezik mértéke a fa. gyökér fa azonos szinten 0. további csúcsok van egy szinten az egyik nagyobb, mint a szint közvetlen őse. A maximális egyetlen csúcs az úgynevezett mélység vagy a fa magasságát. A minimális magassága egy adott pontok számát érhető el, ha minden szinten, kivéve az utolsó, tedd a lehető legnagyobb csúcsok száma. A maximális csúcsok száma a fa magassága H, megvalósítható abban az esetben, minden egyes csomópont, azzal az eltéréssel, a szint H, folytassa d részfák, ahol d a mértéke fa: egy 0-edik szinten 1 csúcsa az 1. - d leszármazottai 2 th - d 2 leszármazottai a 3. szinten d 3 gyermek, stb
bináris (bináris) fák (ris.1.b) alkalmazzák a legszélesebb körben. A bináris fa egy véges elemekre, amelyek üres vagy egy gyökér és két nem átfedő bináris fák, az úgynevezett jobb és bal részfa a gyökér. Így minden egyes eleme a bináris fa értéke 0, 1 vagy 2 részfa. Bináris fa - rendezett fa, mert megkülönbözteti a bal és a jobb részfa.
Meghatározása fa struktúra a fenti rekurzív és tükrözi rekurzív természete maga a szerkezet.
Az adatok szerkezete - a fa is képviselteti magát a statikus és dinamikus memóriát.
A SRAM tömb leírható egy fa, amelynek meghatározott fogalmát egy üres elem:
2. ábra. bináris fa képviseli tömbként
A csúcsok vannak elrendezve egy bináris fa tömb a következők (lásd a 2. ábrát ..): Ha k - index csomópontja, annak leszármazottai vannak tömb elemek indexek 1 és 2k + 2 (k + 1); a gyökér a fa a 0 indexű elem (indexeléséhez a tömb 1-től N-kódok leszármazottai k-adik vertex: 2k és 2k + 1, a gyökér index 1).
A dinamikus memória a fa jelent hierarchikus listája. Állítsa elem lehet egy bináris fa lista elem három területen: a két referencia tartalmazó mezők mutatókat a tőle balra (L) és a jobb (R) részfák, és egy információs mező (E):
Meghatározó elem típusát dinamikus bináris fa:
B-fán alapuló * balra * jobbra;>
Itt típus - Type információs mezőt (ha az információs mezőben egy bonyolult szerkezet, a típus lehet a típus - mutatót az objektum, amely az elem értékét fa).
Annak megállapításához, a fa, mint egy egységes szerkezetű kell állítani a gyökér a fa pointer:
3. ábra. Bináris fa Dynamic
A 3. ábra egy bináris fa dinamikus d összhangban az adott elem típusú, a fenti. fa elemek fokú 0 és 1 egy vagy két referencia-félképétől értékű üres mutató (NULL).
Kezelése a fa, szükséges, hogy megtekinthesse elemében - ezt nevezik bejárás a fa (vagy tompított a fa).