Što je potpuno binarno stablo?

Potpuno binarno stablo može se definirati kao a binarno stablo u kojem svi čvorovi imaju 0 ili dva djeteta. Drugim riječima, puno binarno stablo može se definirati kao binarno stablo u kojem svi čvorovi imaju dva djeteta osim lisnatih čvorova.

Donje stablo je potpuno binarno stablo:

Gornje stablo je potpuno binarno stablo budući da svi čvorovi osim lisnih čvorova imaju dvoje djece.

Potpuni teorem o binarnom stablu:

Smatrajte da je binarno stablo T neprazno stablo:

• Neka sam I unutarnji čvorovi u stablu, a L je čvor lista u stablu, tada bi broj čvorova lista bio jednak:
  L = I + 1
• Ako T ima, I broj unutarnjih čvorova i N je ukupan broj čvorova, tada bi ukupni broj čvorova bio jednak:
  N = 2I + 1
• Ako T sadrži 'N' ukupan broj čvorova i 'I' je broj unutarnjih čvorova, tada bi broj unutarnjih čvorova bio jednak:
  I = (N-1)/2
• Ako 'T' ima 'N' ukupni broj čvorova, a 'L' je broj lisnih čvorova, tada bi broj lisnih čvorova bio jednak:
  L = (N+1)/2
• Ako 'T' sadrži 'L' broj listova čvorova, tada bi ukupni broj čvorova bio jednak:
  N = 2L - 1
• Ako 'T' ima 'L' broj listova čvorova, a 'I' je broj unutarnjih čvorova, tada bi broj unutarnjih čvorova bio jednak:
  I = L - 1

Što je potpuno binarno stablo?

Kaže se da je binarno stablo potpuno binarno stablo kada su sve razine potpuno popunjene osim posljednje razine, koja se popunjava slijeva.

korištenje interneta

Donje stablo je potpuno binarno stablo:

Kompletno binarno stablo slično je punom binarnom stablu osim dvije razlike koje su navedene u nastavku:

• Popunjavanje lisnog čvora mora započeti s krajnje lijeve strane.
• Nije obavezno da zadnji listni čvor mora imati pravog brata.

Razumimo gornje točke kroz primjer:

Razmotrite donje stablo:

Gornje stablo je potpuno binarno stablo, ali ne i potpuno binarno stablo jer čvor 6 nema svog pravog brata.

Stvaranje potpunog binarnog stabla

Pretpostavimo da imamo niz od 6 elemenata prikazanih u nastavku:

Gornji niz sadrži 6 elemenata, tj. 1, 2, 3, 4, 5, 6. Sljedeći su koraci koje treba koristiti za stvaranje potpunog binarnog stabla:

Korak 1: Prvo ćemo odabrati prvi element niza, tj. 1, i napraviti korijenski čvor stabla. Broj dostupnih elemenata u prvoj razini je 1.

Korak 2: Sada ćemo odabrati drugi i treći element niza. Zadržite drugi element i treći element niza kao lijevo i desno dijete korijenskog čvora prikazano u nastavku:

Kao što možemo vidjeti gore, broj elemenata dostupnih na drugoj razini je 2.

Korak 3: Sada ćemo odabrati sljedeća dva elementa iz niza, tj. 4 i 5. Zadržite ova dva elementa lijevo i desno od čvora 2 prikazanog u nastavku:

Kao što možemo vidjeti gore, čvorovi 4 i 5 su lijevo i desno dijete čvora 2.

Korak 4: Sada ćemo odabrati posljednji element niza, tj. 6, i zadržati ga kao lijevo dijete čvora 3 jer znamo da se u potpunom binarnom stablu čvorovi popunjavaju s lijeve strane prikazane u nastavku:

Kao što možemo primijetiti da druga razina sadrži 3 elementa.

Razmotrimo razlike između potpunog i punog binarnog stabla kroz slike.

parafraziram ako po Rudyardu Kiplingu

1. Binarno stablo koje je prikazano u nastavku nije niti potpuno niti potpuno binarno stablo. To nije potpuno binarno stablo jer čvor 3 ima samo jedno dijete. To također nije potpuno binarno stablo jer se čvorovi trebaju popunjavati s lijeve strane, ali čvor 3 ima desno dijete, a nema lijevo dijete.
   
2. Binarno stablo, koje je prikazano u nastavku, potpuno je binarno stablo, ali ne i potpuno binarno stablo. To je potpuno binarno stablo jer svi čvorovi imaju ili 0 ili 2 djece. To nije potpuno binarno stablo jer čvor 3 nema djecu dok čvor 2 ima svoju djecu i znamo da bi čvorove trebalo popuniti s lijeve strane u potpunom binarnom stablu.
   
3. Binarno stablo koje je prikazano u nastavku je potpuno binarno stablo, ali ne potpuno binarno stablo. To je potpuno binarno stablo jer su svi čvorovi ostali popunjeni. To nije potpuno binarno stablo jer čvor 2 ima samo jedno dijete.
   
4. Binarno stablo koje je prikazano u nastavku je potpuno kao i potpuno binarno stablo. To je potpuno binarno stablo jer su svi čvorovi ostali popunjeni. To je potpuno binarno stablo budući da svi čvorovi imaju ili 0 ili 2 djece.