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

Teljes bináris fa vagy teljes bináris fa

A bináris fa olyan fa, ahol minden csomópontnak egy vagy két gyermeke van. Egy bináris fában a csomópontnak nem lehet kétnél több gyermeke. Egy bináris fában a gyermekeket „bal” és „jobb” gyermekeknek nevezik. A gyermek csomópontjai utalnak szüleikre. A teljes bináris fa olyan bináris fa, amelyben a bináris fa minden szintje az utolsó szint kivételével teljesen meg van töltve. Töltetlen szinten a csomópontok a bal legszélső helyzetből indulnak. A teljes bináris fa olyan fa, amelyben a fa minden csomópontja két gyermeket tartalmaz, kivéve a fa leveleit.

Mi a teljes bináris fa??

A teljes bináris fa olyan bináris fa, amelyben a fa minden csomópontja pontosan nulla vagy két gyermek. Más szavakkal, a fa minden csomópontján, kivéve a leveleket, 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 rétegek száma (l) és a belső csomópontok száma (i) speciálisan kapcsolódik egymáshoz, úgy hogy bármelyikük ismerete meg tudja határozni a másik kettőt értékek a következők:

1. Ha egy teljes bináris fa belső i csomóponttal rendelkezik:

- Levelek száma l = i + 1

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

2. Ha egy teljes bináris fa n csomópontot tartalmaz:

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

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

3. Ha egy teljes bináris fa levelei vannak:

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

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

Mi a teljes bináris fa??

Amint a 2. ábrán látható, a teljes bináris fa olyan bináris fa, amelyben a fa minden szintje teljesen kitöltésre kerül, kivéve az utolsó szintet. Ezenkívül az utolsó szintnél a csomópontokat a bal legszélső helyzetből ki kell kapcsolni. A teljes h magasságú bináris fa megfelel a következő feltételeknek:

- A gyökércsomóponttól az utolsó szint feletti szint a h-1 magasságú teljes bináris fát képviseli

- Az utolsó szint egy vagy több csomópontja 0 vagy 1 gyermek lehet

- Ha a, b két csomópont az utolsó szint feletti szinten, akkor a több gyermekkel rendelkezik, mint b, akkor és csak akkor, ha a a bal oldalán található

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ák és a teljes bináris fák egyértelmű különbséget mutatnak. Míg a teljes bináris fa olyan bináris fa, amelyben minden csomópont nulla vagy két gyerek, addig a teljes bináris fa olyan bináris fa, amelyben a bináris fa minden szintje teljesen meg van töltve, kivéve az utolsó szintet. Néhány speciális adatszerkezetnek, például a halomnak teljes bináris fának kell lennie, miközben nem kell teljes bináris fának lennie. Ha egy teljes bináris fában ismeri az összes csomópont számát, a rétegek számát vagy a belső csomópontok számát, akkor a másik kettőt nagyon könnyen megtalálhatja. A teljes bináris fa azonban nem rendelkezik különleges tulajdonsággal, amely a három attribútumhoz kapcsolódik.