A bináris fa azt jelenti, hogy a csomópontnak legfeljebb két gyermeke lehet. Itt maga a bináris név azt sugallja, hogy „kettő”; ezért minden csomópontnak 0, 1 vagy 2 gyermeke lehet.

Értsük meg a bináris fát egy példán keresztül.

A fenti fa egy bináris fa, mivel minden csomópont a legnagyobb két gyermeket tartalmazza. A fenti fa logikai ábrázolása az alábbiakban látható:

A fenti fában az 1. csomópont két mutatót tartalmaz, azaz egy bal és egy jobb oldali mutatót, amelyek rendre a bal és a jobb csomópontra mutatnak. A 2. csomópont mindkét csomópontot tartalmazza (bal és jobb oldali csomópont); ezért két mutatója van (balra és jobbra). A 3-as, 5-ös és 6-os csomópontok a levél csomópontjai, tehát ezek a csomópontok mind tartalmaznak NULLA mutató a bal és a jobb oldalon egyaránt.

A bináris fa tulajdonságai

• Az i minden szintjén a csomópontok maximális száma 2^én.
• A fa magassága a gyökércsomóponttól a levélcsomópontig vezető leghosszabb út. A fent látható fa magassága 3. Ezért a 3. magasságban a csomópontok maximális száma egyenlő (1+2+4+8) = 15. Általában a h magasságban lehetséges csomópontok maximális száma van (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• A h magasságban lehetséges csomópontok minimális száma egyenlő h+1 .
• Ha a csomópontok száma minimális, akkor a fa magassága maximális. Ezzel szemben, ha a csomópontok száma maximális, akkor a fa magassága minimális lenne.

Ha 'n' számú csomópont van a bináris fában.

A minimális magasság a következőképpen számítható ki:

Mint tudjuk,

n = 2^h+1-1

n+1 = 2^h+1

Rönköt szedve mindkét oldalról,

log₂(n+1) = log2(2^h+1)

log₂(n+1) = h+1

h = log₂(n+1) - 1

A maximális magasság a következőképpen számítható ki:

Mint tudjuk,

n = h+1

h=n-1

A bináris fa típusai

A bináris fának négy típusa van:

Teljes/ megfelelő/ szigorú bináris fa Komplett bináris fa Tökéletes bináris fa Degenerált bináris fa Kiegyensúlyozott bináris fa

1. Teljes/ megfelelő/ szigorú bináris fa

A teljes bináris fa szigorú bináris faként is ismert. A fa csak akkor tekinthető teljes bináris fának, ha minden csomópontnak 0 vagy 2 gyermeket kell tartalmaznia. A teljes bináris fa úgy is meghatározható, mint az a fa, amelyben minden csomópontnak 2 gyermeknek kell lennie, kivéve a levél csomópontjait.

Nézzük a teljes bináris fa egyszerű példáját.

A fenti fában megfigyelhetjük, hogy minden csomópont nullát vagy két gyermeket tartalmaz; ezért ez egy teljes bináris fa.

A teljes bináris fa tulajdonságai

• A levél csomópontjainak száma megegyezik a belső csomópontok számával plusz 1-gyel. A fenti példában a belső csomópontok száma 5; ezért a levél csomópontjainak száma 6.
• A csomópontok maximális száma megegyezik a bináris fa csomópontjainak számával, azaz 2^h+1-1.
• A csomópontok minimális száma a teljes bináris fában 2*h-1.
• A teljes bináris fa minimális magassága log₂(n+1) - 1.
• A teljes bináris fa maximális magassága a következőképpen számítható ki:

n = 2*ó - 1

n+1 = 2*ó

h = n+1/2

Teljes bináris fa

A teljes bináris fa olyan fa, amelyben az utolsó szint kivételével az összes csomópont teljesen ki van töltve. Az utolsó szinten az összes csomópontnak a lehető legtávolabbnak kell lennie. Egy teljes bináris fában a csomópontokat balról kell hozzáadni.

Hozzunk létre egy teljes bináris fát.

A fenti fa egy teljes bináris fa, mivel az összes csomópont teljesen ki van töltve, és az utolsó szint összes csomópontja a bal oldalon van először hozzáadva.

A teljes bináris fa tulajdonságai

kaki

• A teljes bináris fában a csomópontok maximális száma 2^h+1- 1.
• A teljes bináris fában a csomópontok minimális száma 2^h.
• A teljes bináris fa minimális magassága log₂(n+1) - 1.
• A teljes bináris fa maximális magassága

Tökéletes bináris fa

Egy fa tökéletes bináris fa, ha az összes belső csomópontnak 2 gyermeke van, és az összes levél csomópontja azonos szinten van.

Nézzünk egy egyszerű példát a tökéletes bináris fára.

Az alábbi fa nem tökéletes bináris fa, mert az összes levél csomópontja nem azonos szinten van.

Megjegyzés: Minden tökéletes bináris fa a teljes bináris fa, valamint a teljes bináris fa, de fordítva nem igaz, azaz minden teljes bináris fa és teljes bináris fa tökéletes bináris fa.

Degenerált bináris fa

A degenerált bináris fa olyan fa, amelyben az összes belső csomópontnak csak egy gyermeke van.

Ismerjük meg a degenerált bináris fát példákon keresztül.

A fenti fa egy degenerált bináris fa, mivel az összes csomópontnak csak egy gyermeke van. Jobbra ferde faként is ismert, mivel minden csomópontnak csak jobb gyermeke van.

A fenti fa is egy degenerált bináris fa, mert az összes csomópontnak csak egy gyermeke van. Balra ferde faként is ismert, mivel minden csomópontnak csak bal oldali gyermeke van.

Kiegyensúlyozott bináris fa

A kiegyensúlyozott bináris fa olyan fa, amelyben a bal és a jobb oldali fa legfeljebb 1-gyel tér el egymástól. AVL és Piros-fekete fák kiegyensúlyozott bináris fa.

Ismerjük meg a kiegyensúlyozott bináris fát példákon keresztül.

A fenti fa egy kiegyensúlyozott bináris fa, mivel a bal oldali részfa és a jobb oldali részfa közötti különbség nulla.

A fenti fa nem kiegyensúlyozott bináris fa, mert a bal oldali részfa és a jobb oldali részfa közötti különbség nagyobb, mint 1.

Bináris fa megvalósítása

A bináris fa mutatók segítségével valósul meg. A fa első csomópontját a gyökérmutató jelöli. A fa minden csomópontja három részből áll, azaz adatokból, bal mutatóból és jobb oldali mutatóból. Bináris fa létrehozásához először létre kell hoznunk a csomópontot. Létrehozzuk a felhasználó által definiált csomópontot az alábbiak szerint:

 struct node { int data, struct node *left, *right; } 

A fenti szerkezetben adat az érték, bal mutató tartalmazza a bal oldali csomópont címét, és jobb mutató tartalmazza a megfelelő csomópont címét.

Bináris fa program C nyelven

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

A fenti kód rekurzívan hívja meg a create() függvényt, és minden rekurzív híváskor új csomópontot hoz létre. Amikor az összes csomópont létrejön, akkor bináris fastruktúrát alkot. A csomópontok látogatásának folyamatát fa bejárásnak nevezik. Háromféle bejárás létezik egy csomópont meglátogatásához:

• Rendbejárás
• Előrendelés bejárás
• Postai utalvány bejárás