Fa (adatszerkezet)

A Wikipédiából, a szabad enciklopédiából
Bináris fa 9 (belső) csúccsal (a külső csúcsok nincsenek feltüntetve). A fa gyökere a 2-es csúcs. (Ábrákon általában felülre kerül a gyökér, és lefele vannak a a gyermekek.)

Fa alatt egy olyan rekurzív adatszerkezetet értünk számítástechnikában, amely belső és külső csúcsok hierarchikus (szülő-gyermek) elrendezéséből áll. Formálisan, egy fa az vagy (1) egy külső csúcs, vagy pedig egy belső csúcs (szülő), amelyhez bizonyos számú fa kapcsolódik (gyermekek). Matematikailag, az adatszerkezet megfelel egy irányított (gyökeres) fának, amelyben egy kitüntetett csúcsból (a gyökérből) pontosan egy út vezet minden más csúcshoz.

Gyakran (de nem mindig), minden belső csúcsnak ugyanannyi gyereke van, azaz ugyanaz a fokszáma, és a gyerekek sorrendje számít. Így egy bináris fában minden csúcsnak pontosan két gyereke van: bal és jobb gyermek. Különféle implementációkban általában csak a belső csúcsok hordoznak információt, és a külső csúcsokat csak egy null mutató jelöli. Az alábbi Java program egy bináris fa definícióját tartalmazza: ebben a példában minden csúcsnál eltároljuk a szülőt és a gyerekeket is.

class Csucs // bináris fa egy belső csúcsa
{
    Csucs szülő; // mutató a szülőre, null ha gyökér
    Csucs bal; // mutató a bal gyerekre, null ha külső gyerek
    Csucs jobb; // mutató a jobb gyerekre, null ha külső gyerek
    Object adat; 
}