Különbség A Teljes Bináris Fa és A Teljes Bináris Fa Között

2024 Szerző: Mildred Bawerman | [email protected]. Utoljára módosítva: 2023-12-16 08:39

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.