A

Binārs koks

policijas komisāra asistents

Ir dažādi bināro koku veidi bet šeit mēs runāsim par atšķirību Pilnīgs binārais koks un Pilns binārais koks .

Pilns binārais koks:

Pilns binārais koks ir binārs koks, kurā visiem mezgliem ir 0 vai 2 pēcnācēji . Citiem vārdiem sakot, pilns binārais koks ir binārs koks, kurā visiem mezgliem, izņemot lapu mezglus, ir divi pēcnācēji.

Pilns binārais koks

Ļaujiet, i ir iekšējo mezglu skaits
n ir kopējais mezglu skaits
l būt lapu skaitam
l jābūt līmeņu skaitam

Tad

Lapu skaits ir (i + 1) .
Kopējais mezglu skaits ir (2i + 1) .
Iekšējo mezglu skaits ir (n – 1) / 2 .
Lapu skaits ir (n + 1) / 2 .
Kopējais mezglu skaits ir (2l - 1) .
Iekšējo mezglu skaits ir (l-1) .
Lapu skaits ir ne vairāk kā (2^l- 1) .

Pilnīgs binārais koks:

Tiek uzskatīts, ka binārais koks ir a pilnīgs binārais koks ja visos tā līmeņos, izņemot, iespējams, pēdējo līmeni, ir maksimālais iespējamo mezglu skaits un visi mezgli pēdējais līmenis parādās pēc iespējas pa kreisi .

Pilnīgs binārais koks

Šeit jūs varat atpazīt divus punktus,

1. Lapas mezgla galējā kreisā puse vienmēr ir jāaizpilda vispirms.
2. Nav obligāti, lai pēdējās lapas mezglam būtu pareizais brālis.

Pārbaudiet tālāk sniegtos piemērus, lai labāk izprastu pilno un pilnīgu bināro koku.

1. piemērs:

Ne pilnīgs, ne pilns

• Mezgls C tāpēc ir tikai viens bērns, tas nav pilnīgs binārais koks.
• Mezgls C ir arī labais bērns, bet nav kreisā bērna, tāpēc tas arī nav pilnīgs binārais koks.

Tādējādi iepriekš parādītais binārais koks ir ne pilnīgs, ne pilns binārais koks.

2. piemērs:

Pilnīga, bet ne pilnīga

• Visiem mezgliem ir kāds no tiem 0 vai 2 tāpēc pēcnācēji, tas ir pilns binārs koks .
Tas nav pilnīgs binārais koks, jo mezgls B nav bērnu, savukārt mezglam C ir bērni, un saskaņā ar pilnīgu bināro koku mezgli ir jāaizpilda no kreisā puse .

Tādējādi iepriekš parādītais binārais koks ir a Pilns binārais koks un tā ir nav pilnīgs binārais koks.

3. piemērs:

Pilnīga, bet ne pilna

Tas ir pilnīgs binārais koks, jo visi mezgli ir atstāti aizpildīti.
• Mezglā B ir tikai viens bērns, tāpēc tas nav pilnīgs binārs koks.

Tādējādi iepriekš parādītais binārais koks ir a Pilnīgs binārais koks un tā ir nav pilnīgs binārais koks.

4. piemērs:

Pilnīga un pilna

• Tas ir Pilnīgs binārs koks, jo visi mezgli ir pa kreisi aizpildīta .
• Visiem mezgliem ir kāds no tiem 0 vai 2 pēcnācēji, tāpēc tas ir a pilns binārais koks .

Tādējādi iepriekš parādītais binārais koks ir gan pilnīgs, gan pilns binārais koks.