Atšķirība starp pilnu bināro koku un pilnu bināro koku

Pilnīgs binārais koks salīdzinājumā ar pilnu bināro koku

Binārais koks ir koks, kurā katram mezglam ir viens vai divi bērni. Binārā kokā mezglā nedrīkst būt vairāk par diviem bērniem. Binārā kokā bērni tiek nosaukti par “kreiso” un “labo” bērnu. Bērnu mezglos ir atsauce uz viņu vecāku. Pilnīgs binārais koks ir binārs koks, kurā katrs binārā koka līmenis ir pilnībā piepildīts, izņemot pēdējo līmeni. Neizpildītā līmenī mezgli tiek piestiprināti, sākot no kreisās malas pozīcijas. Pilns binārais koks ir koks, kurā katram koka mezglam ir divi bērni, izņemot koka lapas.

Kas ir pilns binārais koks?

Pilns binārais koks ir binārs koks, kurā katram koka mezglam ir precīzi nulle vai divi bērni. Citiem vārdiem sakot, katram mezglam kokā, izņemot lapas, ir tieši divi bērni. Zemāk redzamajā 1. attēlā ir parādīts pilns binārais koks. Pilna binārā kokā mezglu skaits (n), joslu skaits (l) un iekšējo mezglu skaits (i) ir saistīti īpašā veidā tā, ka, ja jūs zināt kādu no tiem, varat noteikt pārējos divus vērtības ir šādas:

1. Ja pilnam bināram kokam ir i iekšējie mezgli:

- Lapu skaits l = i + 1

- Kopējais mezglu skaits n = 2 * i + 1

2. Ja pilnam bināram kokam ir n mezgla:

- Iekšējo mezglu skaits i = (n-1) / 2

- Lapu skaits l = (n + 1) / 2

3. Ja pilnam bināram kokam ir l lapas:

- Kopējais mezglu skaits n = 2 * l-1

- Iekšējo mezglu skaits i = l-1

Kas ir pilnīgs binārais koks?

Kā parādīts 2. attēlā, pilnīgs binārais koks ir binārs koks, kurā katrs koka līmenis ir pilnībā piepildīts, izņemot pēdējo līmeni. Arī pēdējā līmenī mezgli jāpiestiprina, sākot no kreisās malas pozīcijas. Pilns h binārs koks atbilst šādiem nosacījumiem:

- Sākot no saknes mezgla, līmenis virs pēdējā līmeņa apzīmē pilnu bināro koku ar augstumu h-1

- Vienā vai vairākos pēdējā līmeņa mezglos var būt 0 vai 1 bērns

- Ja a, b ir divi mezgli līmenī virs pēdējā līmeņa, tad a ir vairāk bērnu nekā b, ja un tikai tad, ja a atrodas pa kreisi no b

Kāda ir atšķirība starp pilnīgu bināro koku un pilnu bināro koku?

Pilnīgiem bināriem kokiem un pilniem bināriem kokiem ir skaidra atšķirība. Kamēr pilns binārais koks ir binārs koks, kurā katram mezglam ir nulle vai divi bērni, pilnīgs binārais koks ir binārs koks, kurā katrs binārā koka līmenis ir pilnībā piepildīts, izņemot pēdējo līmeni. Dažām īpašām datu struktūrām, piemēram, kaudzēm, jābūt pilnīgiem bināriem kokiem, kamēr tām nav jābūt pilnām binārām koku grupām. Pilna binārā kokā, ja jūs zināt kopējo mezglu skaitu, joslu skaitu vai iekšējo mezglu skaitu, pārējos divus varat atrast ļoti viegli. Bet pilnīgi bināram kokam nav īpašas īpašības, kas attiecas uz šiem trim atribūtiem.