Teljes bináris fa vs teljes bináris fa
A bináris fa olyan fa, amelyben minden csomópontnak egy vagy két gyermeke van. Egy bináris fában egy csomópontnak nem lehet kettőnél több gyermeke. Egy bináris fában a gyerekeket „baloldali” és „jobboldali” gyerekeknek nevezik. A gyermek csomópontok hivatkozást tartalmaznak a szülőjükre. A teljes bináris fa olyan bináris fa, amelyben a bináris fa minden szintje teljesen ki van töltve, kivéve az utolsó szintet. A kitöltetlen szinten a csomópontok a bal szélső pozíciótól kezdve vannak rögzítve. 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 szóval, a fa minden csomópontjához, kivéve a leveleket, pontosan két gyermeke 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 láve-ek száma (l) és a belső csomópontok száma (i) olyan speciális módon kapcsolódik, hogy ha valamelyiket ismeri, meghatározhatja a másik kettőt. értékek a következők:
1. Ha egy teljes bináris fának i belső csomópontjai vannak:
– Levelek száma l=i+1
– Csomópontok teljes száma n=2i+1
2. Ha egy teljes bináris fának n csomópontja van:
– Belső csomópontok száma i=(n-1)/2
– Levelek száma l=(n+1)/2
3. Ha egy teljes bináris fának l levele van:
– Csomópontok teljes száma n=2l-1
– 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 olyan bináris fa, amelyben a fa minden szintje teljesen ki van töltve, kivéve az utolsó szintet. Ezenkívül az utolsó szinten a csomópontokat a bal szélső pozíciótól kezdve kell rögzíteni. Egy h magasságú teljes bináris fa kielégíti a következő feltételeket:
– A gyökércsomópontból az utolsó szint feletti szint egy h-1 magasságú teljes bináris fát jelent.
– Az utolsó szinten egy vagy több csomópontnak lehet 0 vagy 1 gyermeke
– Ha a, b két csomópont az utolsó szint feletti szinten, akkor a-nak több gyermeke van, mint b-nek, akkor és csak akkor, ha a a b-tól 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ák és a teljes bináris fák között egyértelmű különbség 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 ki van töltve, kivéve az utolsó szintet. Egyes speciális adatstruktúráknak, például a kupacoknak teljes bináris fáknak kell lenniük, miközben nem kell teljes bináris fáknak lenniük. Egy teljes bináris fában, ha ismeri az összes csomópontok számát, vagy a lave-ok számát, vagy a belső csomópontok számát, nagyon könnyen megtalálhatja a másik kettőt. De egy teljes bináris fának nincs speciális tulajdonsága a három attribútumhoz kapcsolódóan.
