Teljes bináris fa vs teljes bináris fa
A bináris fa egy fa, ahol minden csomópontnak egy vagy két gyermeke van. A bináris fában egy csomópontnak nem lehet kettőnél több gyermeke. A bináris fában a gyerekeket „bal” és „jobb” gyerekeknek nevezik. A gyermek csomópontok hivatkozást tartalmaznak a szüleikre. A teljes bináris fa olyan bináris fa, amelyben a bináris fa minden szintje teljesen kitöltődik, kivéve az utolsó szintet. A kitöltetlen szinten a csomópontok a bal oldali helyzetből indulnak ki. A teljes bináris fa olyan fa, amelyben a fa minden csomópontjának két gyermeke van, kivéve a fa leveleit.
Mi az a teljes bináris fa?
A teljes bináris fa olyan bináris fa, amelyben a fa minden csomópontjának pontosan nulla vagy két gyermeke van. Más szavakkal, a fa minden csomópontján a leveleken kívül pontosan két gyermek van. Az alábbi 1. ábra egy teljes bináris fát ábrázol. Egy teljes bináris fában a csomópontok száma (n), a lave-ok száma (l) és a belső csomópontok száma (i) különös módon kapcsolódik egymáshoz, így ha bármelyiket ismeri, meghatározhatja a másik kettőt értékek az alábbiak szerint:
1. Ha egy teljes bináris fának i belső csomópontja van:
- A levelek száma l = i + 1
- Az összes csomópont száma n = 2 * i + 1
2. Ha egy teljes bináris fának n csomópontja van:
- A belső csomópontok száma i = (n-1) / 2
- Levelek száma l = (n + 1) / 2
3. Ha egy teljes bináris fának van l levele:
- Az összes csomópont száma n = 2 * l-1
- A belső csomópontok száma i = l-1
Mi az a teljes bináris fa?
Amint a 2. ábrán látható, a teljes bináris fa egy bináris fa, amelyben a fa minden szintje teljesen kitöltődik, kivéve az utolsó szintet. Ezenkívül az utolsó szinten a csomópontokat a bal oldali helyzetből kiindulva kell csatlakoztatni. Egy teljes h magasságú bináris fa megfelel a következő feltételeknek:
- A gyökércsomópontból az utolsó szint feletti szint egy teljes h-1 magasságú bináris fát képvisel
- Az utolsó szint egy vagy több csomópontjában 0 vagy 1 gyermek lehet
- Ha a, b két csomópont az utolsó szint feletti szinten, akkor a-nak akkor van több gyermeke, mint b-nek, ha a balra helyezkedik el
Mi a különbség a teljes bináris fa és a teljes bináris fa között?
A teljes bináris fáknak és a teljes bináris fáknak egyértelmű különbségük van. Míg a teljes bináris fa olyan bináris fa, amelyben minden csomópontnak nulla vagy két gyermeke van, a teljes bináris fa olyan bináris fa, amelyben a bináris fa minden szintje teljesen kitöltve van, kivéve az utolsó szintet. Néhány speciális adatstruktúrának, például a kupacoknak, teljes bináris fáknak kell lenniük, míg nem kell teljes bináris fáknak lenniük. Egy teljes bináris fában, ha ismeri az összes csomópont számát, a laves számát vagy a belső csomópontok számát, akkor a másik kettőt nagyon könnyen megtalálja. De egy teljes bináris fának nincs külön tulajdonsága, amely a három attribútumhoz kapcsolódik.
