TechCodeview

Binarno drevo pomeni, da ima lahko vozlišče največ dva otroka. Tukaj že samo binarno ime nakazuje, da je 'dva'; zato ima lahko vsako vozlišče 0, 1 ali 2 otroka.

Razumejmo binarno drevo na primeru.

Zgornje drevo je binarno drevo, ker vsako vozlišče vsebuje največ dva otroka. Logična predstavitev zgornjega drevesa je podana spodaj:

do in while zanka v Javi

V zgornjem drevesu vsebuje vozlišče 1 dva kazalca, tj. levi in ​​desni kazalec, ki kažeta na levo oziroma desno vozlišče. Vozlišče 2 vsebuje obe vozlišči (levo in desno vozlišče); zato ima dva kazalca (levega in desnega). Vozlišča 3, 5 in 6 so listna vozlišča, tako da vsa ta vozlišča vsebujejo NIČ kazalec na levi in ​​desni strani.

Lastnosti binarnega drevesa

• Na vsaki ravni i je največje število vozlišč 2^jaz.
• Višina drevesa je opredeljena kot najdaljša pot od korenskega vozlišča do listnega vozlišča. Drevo, ki je prikazano zgoraj, ima višino enako 3. Zato je največje število vozlišč na višini 3 enako (1+2+4+8) = 15. Na splošno je največje možno število vozlišč na višini h je (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Najmanjše možno število vozlišč na višini h je enako h+1 .
• Če je število vozlišč minimalno, bi bila višina drevesa največja. Nasprotno, če je število vozlišč največje, potem bi bila višina drevesa najmanjša.

Če je v binarnem drevesu 'n' število vozlišč.

Najmanjšo višino je mogoče izračunati kot:

Kot vemo,

n = 2^h+1-1

n+1 = 2^h+1

Jemanje hloda na obeh straneh,

dnevnik₂(n+1) = log2(2^h+1)

dnevnik₂(n+1) = h+1

h = dnevnik₂(n+1) - 1

Največjo višino je mogoče izračunati kot:

Kot vemo,

n = h+1

h= n-1

Vrste binarnega drevesa

Obstajajo štiri vrste binarnega drevesa:

Polno/pravilno/strogo binarno drevo Popolno binarno drevo Popolno binarno drevo Degenerirano binarno drevo Uravnoteženo binarno drevo

1. Polno/ pravilno/ strogo binarno drevo

Polno binarno drevo je znano tudi kot strogo binarno drevo. Drevo se lahko obravnava kot polno binarno drevo le, če mora vsako vozlišče vsebovati 0 ali 2 otroka. Polno binarno drevo je mogoče definirati tudi kot drevo, v katerem mora vsako vozlišče vsebovati 2 otroka razen listnih vozlišč.

Poglejmo si preprost primer polnega binarnega drevesa.

V zgornjem drevesu lahko opazimo, da vsako vozlišče vsebuje nič ali dva otroka; zato je polno binarno drevo.

Lastnosti polnega binarnega drevesa

• Število listnih vozlišč je enako številu notranjih vozlišč plus 1. V zgornjem primeru je število notranjih vozlišč 5; zato je število listnih vozlov enako 6.
• Največje število vozlišč je enako številu vozlišč v binarnem drevesu, tj. 2^h+1-1.
• Najmanjše število vozlišč v celotnem binarnem drevesu je 2*h-1.
• Najmanjša višina polnega binarnega drevesa je dnevnik₂(n+1) - 1.
• Največjo višino celotnega binarnega drevesa je mogoče izračunati kot:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Popolno binarno drevo

Popolno binarno drevo je drevo, v katerem so vsa vozlišča popolnoma zapolnjena, razen zadnje ravni. V zadnjem nivoju morajo biti vsa vozlišča čim bolj levo. V celotnem binarnem drevesu je treba vozlišča dodati z leve.

Ustvarimo popolno binarno drevo.

Zgornje drevo je popolno binarno drevo, ker so vsa vozlišča popolnoma zapolnjena, vsa vozlišča na zadnji ravni pa so najprej dodana na levi.

Lastnosti popolnega binarnega drevesa

seznam na Javi

• Največje število vozlišč v celotnem binarnem drevesu je 2^h+1- 1.
• Najmanjše število vozlišč v celotnem binarnem drevesu je 2^h.
• Najmanjša višina popolnega binarnega drevesa je dnevnik₂(n+1) - 1.
• Največja višina celotnega binarnega drevesa je

Popolno binarno drevo

Drevo je popolno binarno drevo, če imajo vsa notranja vozlišča 2 otroka in so vsa listna vozlišča na isti ravni.

Poglejmo si preprost primer popolnega binarnega drevesa.

Spodnje drevo ni popolno binarno drevo, ker vsa listna vozlišča niso na isti ravni.

Opomba: Vsa popolna binarna drevesa so tako popolna binarna drevesa kot tudi polna binarna drevesa, vendar obratno ne velja, tj. vsa popolna binarna drevesa in polna binarna drevesa so popolna binarna drevesa.

Degenerirano binarno drevo

Degenerirano binarno drevo je drevo, v katerem imajo vsa notranja vozlišča samo enega otroka.

Razumejmo degenerirano binarno drevo skozi primere.

Zgornje drevo je degenerirano binarno drevo, ker imajo vsa vozlišča samo enega otroka. Znano je tudi kot desno poševno drevo, saj imajo vsa vozlišča samo desnega otroka.

Zgornje drevo je tudi degenerirano binarno drevo, ker imajo vsa vozlišča samo enega otroka. Znano je tudi kot levo poševno drevo, saj imajo vsa vozlišča samo levega otroka.

Uravnoteženo binarno drevo

kakšna je razlika med megabajtom in gigabajtom

Uravnoteženo binarno drevo je drevo, v katerem se levo in desno drevo razlikujeta največ za 1. Na primer, AVL in Rdeče-črna drevesa so uravnoteženo binarno drevo.

Razumejmo uravnoteženo binarno drevo skozi primere.

Zgornje drevo je uravnoteženo binarno drevo, ker je razlika med levim in desnim poddrevesom nič.

Zgornje drevo ni uravnoteženo binarno drevo, ker je razlika med levim in desnim poddrevesom večja od 1.

Implementacija binarnega drevesa

Binarno drevo je implementirano s pomočjo kazalcev. Prvo vozlišče v drevesu predstavlja korenski kazalec. Vsako vozlišče v drevesu je sestavljeno iz treh delov, to so podatki, levi in ​​desni kazalec. Če želite ustvariti binarno drevo, moramo najprej ustvariti vozlišče. Ustvarili bomo uporabniško definirano vozlišče, kot je prikazano spodaj:

 struct node { int data, struct node *left, *right; } 

V zgornji strukturi je podatke je vrednost, levi kazalec vsebuje naslov levega vozlišča in desni kazalec vsebuje naslov desnega vozlišča.

Program Binary Tree v C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Zgornja koda rekurzivno kliče funkcijo create() in ob vsakem rekurzivnem klicu ustvarja novo vozlišče. Ko so ustvarjena vsa vozlišča, tvori binarno drevesno strukturo. Postopek obiskovanja vozlišč je znan kot prečkanje drevesa. Obstajajo tri vrste prehodov, ki se uporabljajo za obisk vozlišča:

• Prehod po vrstnem redu
• Prehod po prednaročilu
• Prehod poštnega naloga