Kaj je polno binarno drevo?

Polno binarno drevo lahko definiramo kot a binarno drevo v kateri imajo vsa vozlišča 0 ali dva otroka. Z drugimi besedami, polno binarno drevo lahko definiramo kot binarno drevo, v katerem imajo vsa vozlišča dva otroka, razen listnih vozlišč.

Spodnje drevo je polno binarno drevo:

Zgornje drevo je polno binarno drevo, saj imajo vsa vozlišča, razen vozlišč listov, dva otroka.

Celoten izrek o binarnem drevesu:

Upoštevajte, da je binarno drevo T neprazno drevo, potem:

• Naj bom I notranja vozlišča v drevesu in L listno vozlišče v drevesu, potem bi bilo število listnih vozlišč enako:
  L = jaz + 1
• Če ima T I število notranjih vozlišč in je N skupno število vozlišč, potem bi bilo skupno število vozlišč enako:
  N = 2I + 1
• Če T vsebuje 'N' skupno število vozlišč in je 'I' število notranjih vozlišč, bi bilo število notranjih vozlišč enako:
  I = (N-1)/2
• Če ima 'T' skupno število vozlišč 'N' in je 'L' število listnih vozlišč, bi bilo število listnih vozlišč enako:
  L = (N+1)/2
• Če 'T' vsebuje 'L' število listnih vozlišč, bi bilo skupno število vozlišč enako:
  N = 2L - 1
• Če ima 'T' število listnih vozlišč 'L' in je 'I' število notranjih vozlišč, potem bi bilo število notranjih vozlišč enako:
  I = L - 1

Kaj je popolno binarno drevo?

Za binarno drevo pravimo, da je popolno binarno drevo, ko so vse ravni popolnoma zapolnjene, razen zadnje ravni, ki je zapolnjena z leve.

Spodnje drevo je popolno binarno drevo:

Celotno binarno drevo je podobno celotnemu binarnemu drevesu, razen dveh razlik, ki sta navedeni spodaj:

• Polnjenje listnega vozla se mora začeti na skrajni levi strani.
• Ni obvezno, da mora imeti zadnje listno vozlišče pravega brata.

Razumejmo zgornje točke na primeru:

runas v lupini powershell

Razmislite o spodnjem drevesu:

Zgornje drevo je popolno binarno drevo, vendar ni popolno binarno drevo, saj vozlišče 6 nima pravega brata.

Izdelava popolnega binarnega drevesa

Recimo, da imamo niz 6 elementov, prikazanih spodaj:

Zgornja matrika vsebuje 6 elementov, tj. 1, 2, 3, 4, 5, 6. Za ustvarjanje celotnega binarnega drevesa je treba uporabiti naslednje korake:

Korak 1: Najprej bomo izbrali prvi element matrike, tj. 1, in naredili korensko vozlišče drevesa. Število elementov, ki so na voljo v prvi stopnji, je 1.

2. korak: Sedaj bomo izbrali drugi in tretji element matrike. Ohranite drugi in tretji element matrike kot levega in desnega otroka korenskega vozlišča, kot je prikazano spodaj:

Kot lahko opazimo zgoraj, je število elementov, ki so na voljo na drugi ravni, 2.

3. korak: Sedaj bomo izbrali naslednja dva elementa iz matrike, tj. 4 in 5. Ta dva elementa hranite levo in desno od vozlišča 2, kot je prikazano spodaj:

Kot lahko opazimo zgoraj, sta vozlišči 4 in 5 levi oziroma desni otrok vozlišča 2.

4. korak: Zdaj bomo izbrali zadnji element matrike, tj. 6, in ga obdržali kot levega otroka vozlišča 3, saj vemo, da so v celotnem binarnem drevesu vozlišča zapolnjena z leve strani, kot je prikazano spodaj:

Kot lahko opazimo, druga raven vsebuje 3 elemente.

Razumejmo razlike med popolnim in polnim binarnim drevesom skozi slike.

mvc v spomladanskem okviru

1. Binarno drevo, ki je prikazano spodaj, ni ne popolno ne popolno binarno drevo. To ni polno binarno drevo, ker ima vozlišče 3 samo enega otroka. Prav tako ni popolno binarno drevo, saj je treba vozlišča zapolniti z leve strani, vendar ima vozlišče 3 desnega otroka in nima levega otroka.
   
2. Binarno drevo, ki je prikazano spodaj, je polno binarno drevo, vendar ne popolno binarno drevo. Je polno binarno drevo, ker imajo vsa vozlišča 0 ali 2 otroka. To ni popolno binarno drevo, ker vozlišče 3 nima otrok, medtem ko ima vozlišče 2 svoje otroke in vemo, da je treba vozlišča zapolniti z leve strani v popolnem binarnem drevesu.
   
3. Binarno drevo, ki je prikazano spodaj, je popolno binarno drevo, vendar ne popolno binarno drevo. Je popolno binarno drevo, saj so vsa vozlišča zapolnjena. To ni polno binarno drevo, saj ima vozlišče 2 samo enega otroka.
   
4. Binarno drevo, ki je prikazano spodaj, je popolno in polno binarno drevo. Je popolno binarno drevo, saj so vsa vozlišča zapolnjena. Je polno binarno drevo, saj imajo vsa vozlišča 0 ali 2 otroka.