Mi az a teljes bináris fa?
A teljes bináris fa úgy definiálható, mint a bináris fa amelyben az összes csomópontnak 0 vagy két gyermeke van. Más szavakkal, a teljes bináris fa olyan bináris faként definiálható, amelyben az összes csomópontnak két gyermeke van, kivéve a levél csomópontjait.
Az alábbi fa egy teljes bináris fa:
A fenti fa egy teljes bináris fa, mivel a levélcsomópontok kivételével minden csomópontnak két gyermeke van.
Teljes bináris fa tétel:
Tekintsük a T bináris fát nem üres fának, akkor:
- Legyen I belső csomópont egy fában, L pedig levélcsomópont egy fában, akkor a levélcsomópontok száma egyenlő lenne:
L = I + 1 - Ha T-nek van I számú belső csomópontja, és N a csomópontok teljes száma, akkor a csomópontok teljes száma egyenlő:
N = 2I + 1 - Ha T tartalmazza a csomópontok teljes számát 'N', és az 'I' a belső csomópontok számát jelenti, akkor a belső csomópontok száma egyenlő:
I = (N-1)/2 - Ha a 'T'-nek 'N' a csomópontjainak teljes száma, és az 'L' a levélcsomópontok számát jelenti, akkor a levélcsomópontok száma a következővel egyenlő:
L = (N+1)/2 - Ha a „T” „L” számú levélcsomópontot tartalmaz, akkor a csomópontok teljes száma a következővel egyenlő:
N = 2L-1 - Ha „T”-nek „L” számú levélcsomópontja van, az „I”-nek pedig a belső csomópontok száma, akkor a belső csomópontok száma egyenlő:
I = L-1
Mi az a teljes bináris fa?
A bináris fát teljes bináris fának nevezik, ha az összes szint teljesen kitöltött, kivéve az utolsó szintet, amely balról van kitöltve.
Az alábbi fa egy teljes bináris fa:
A teljes bináris fa hasonló a teljes bináris fához, kivéve az alábbiakban megadott két különbséget:
- A levélcsomópont kitöltését a bal szélről kell kezdeni.
- Nem kötelező, hogy az utolsó levél csomópontjának megfelelő testvére legyen.
Értsük meg a fenti pontokat egy példán keresztül:
Tekintsük az alábbi fát:
A fenti fa egy teljes bináris fa, de nem teljes bináris fa, mivel a 6. csomópontnak nincs megfelelő testvére.
Teljes bináris fa létrehozása
Tegyük fel, hogy van egy 6 elemből álló tömbünk az alábbiak szerint:
A fenti tömb 6 elemet tartalmaz, azaz 1, 2, 3, 4, 5, 6. A következő lépéseket kell használni egy teljes bináris fa létrehozásához:
1. lépés: Először kijelöljük a tömb első elemét, azaz az 1-et, és létrehozzuk a fa gyökércsomópontját. Az első szinten elérhető elemek száma 1.
2. lépés: Most kiválasztjuk a tömb második és harmadik elemét. Tartsa meg a tömb második és harmadik elemét a gyökércsomópont bal és jobb oldali gyermekeként, az alábbiak szerint:
Mint fentebb láthattuk, a második szinten elérhető elemek száma 2.
3. lépés: Most a következő két elemet választjuk ki a tömbből, azaz a 4-et és az 5-öt. Tartsa ezt a két elemet a 2. csomópont bal és jobb oldalán az alábbiak szerint:
Mint fentebb láthattuk, a 4. és 5. csomópont a 2. csomópont bal és jobb oldali gyermeke.
4. lépés: Most kiválasztjuk a tömb utolsó elemét, azaz a 6-ot, és megtartjuk a 3. csomópont bal gyermekeként, mivel tudjuk, hogy egy teljes bináris fában a csomópontok a bal oldalról vannak kitöltve, az alábbiak szerint:
Mint láthatjuk, a második szint 3 elemet tartalmaz.
Értsük meg a teljes és a teljes bináris fa közötti különbségeket a képeken keresztül.
- Az alább látható bináris fa sem nem teljes, sem nem teljes bináris fa. Ez nem egy teljes bináris fa, mert a 3. csomópontnak csak egy gyermeke van. Ez sem egy teljes bináris fa, mivel a csomópontokat a bal oldalról kell kitölteni, de a 3. csomópontnak van jobb gyermeke, és nincs bal gyermeke.
- Az alább látható bináris fa egy teljes bináris fa, de nem teljes bináris fa. Ez egy teljes bináris fa, mert minden csomópontnak 0 vagy 2 gyermeke van. Ez nem egy teljes bináris fa, mert a 3. csomópontnak nincsenek gyermekei, míg a 2. csomópontnak vannak gyermekei, és tudjuk, hogy a csomópontokat bal oldalról kell kitölteni egy teljes bináris fában.
- Az alább látható bináris fa egy teljes bináris fa, de nem teljes bináris fa. Ez egy teljes bináris fa, mivel az összes csomópont kitöltve marad. Ez nem egy teljes bináris fa, mivel a 2. csomópontnak csak egy gyermeke van.
- Az alább látható bináris fa egy teljes és egy teljes bináris fa is. Ez egy teljes bináris fa, mivel az összes csomópont kitöltve marad. Ez egy teljes bináris fa, mivel minden csomópontnak 0 vagy 2 gyermeke van.
