Különbség a teljes bináris fa és a teljes bináris fa között

Bináris fa teljes vagy teljes bináris fa

A bináris fa olyan fa, amelyben minden csomópontnak egy vagy két gyermeke van. Egy bináris fa esetében a csomópontnak nem lehet több, mint két gyermeke. Egy bináris fa esetében a gyermekeket "bal" és "jobb" gyermekeknek nevezik. A gyermekcsomópontok tartalmaznak egy hivatkozást a szülőjükre. Egy teljes bináris fa egy bináris fa, amelyben a bináris fa minden szintje teljesen kitöltött, kivéve az utolsó szintet. A kitöltetlen szinten a csomópontok a bal oldali pozíciótól indulnak. Egy teljes bináris fa egy olyan fa, amelyben minden fa csomópontján két gyermek van, kivéve a fa levelét.

Mi a teljes bináris fa?

A teljes bináris fa egy bináris fa, amelyben a fa minden csomópontja pontosan nulla vagy két gyermek. Más szavakkal, a leveleken kívül minden fa csomópontja pontosan két gyermek. Az alábbi 1. ábrán egy teljes bináris fa látható. Egy teljes bináris fa esetén a csomópontok száma (n), a lárványok száma (l) és a belső csomópontok (i) száma különös módon kapcsolódik össze, úgyhogy ha bármelyiket ismeri, meghatározhatja a másik két értékeket az alábbiak szerint:

1. Ha a teljes bináris fa belső bontópontja:

- A levelek száma l = i + 1

- A csomópontok száma összesen n = 2 * i + 1

2. Ha egy teljes bináris fa n csomópontokkal rendelkezik:

- A belső csomópontok száma i = (n-1) / 2

- A levelek száma l = (n + 1) / 2

3. Ha egy teljes bináris fa l levelekkel rendelkezik:

- Összes csomópont száma n = 2 * l-1

- A belső csomópontok száma i = l-1

Mi a teljes bináris fa?

Amint a 2. ábrán látható, egy teljes bináris fa egy bináris fa, amelyben a fa minden szintje teljesen kitöltött, kivéve az utolsó szintet. Az utolsó szinten is a csomópontokat a bal oldali pozíciótól kezdve kell csatolni. A h magasságú teljes bináris fa megfelel a következő feltételeknek:

- A gyökércsomópontból az előző szint fölötti szint egy teljes bináris fát jelent a h-1

magasságban. - Az utolsó szint egy vagy több csomópontja 0 vagy 1 gyermek

- Ha a, b két csomópont van az utolsó szint felett, akkor a-nak több gyermeke van, mint b Ha és csak akkor, ha a a b

-tól balra található. Mi a különbség a teljes bináris fa és a teljes bináris fa?

A teljes bináris fák és a teljes bináris fák egyértelmű különbséggel rendelkeznek. Míg egy teljes bináris fa egy bináris fa, amelyben minden csomópontnak nulla vagy két gyermeke van, egy teljes bináris fa egy bináris fa, amelyben a bináris fa minden szintje teljesen kitöltött, kivéve az utolsó szintet. Néhány speciális adatszerkezet, mint a tömb, teljes bináris fáknak kell lennie, miközben nem kell teljes bináris fákkal rendelkeznie. Egy teljes bináris fa esetén, ha ismeri a teljes csomópontok számát, vagy a mélyhullámok számát vagy a belső csomópontok számát, a másik kettőt könnyen megtalálhatja.A teljes bináris fa azonban nem rendelkezik olyan tulajdonsággal, amely a három tulajdonságra vonatkozik.